As Lovely as a Tree

Well, I don’t think it is the point of the article, but we might as well list the most beautiful algorithms we can think of, right?

Mergesort is quite beautiful I think. There’s something beautiful in the simplicity of just merging the sorted lists. Stable. No pathological cases. Nice access patterns.

Haskell (and some other pure FP langs) produces a lot of code that is basically technical poetry, at the cost of performance.

just look at the fib example:

>> fib = 1 : 1 : [a + b | (a, b) <- zip fib (tail fib)]

I may be misremembering, but I saw a 'C' strcpy that looked concise and elegant, and seemed like a kind of poetry to me at the time.

    while(*s1++ = *s2++);

There's a universal algorithm

    (λ 1 1) (λ (λλλ 1 (λ 1 (λ 4 (λλλ 3 1 (2 (λ 2)))) (4 (λ 5 (λ 5 (2 1)))))) (1 1)) (λ 1)

(in de-Bruijn notation) which, given a list of input bits, parses the encoding of an arbitrary algorithm (as a combinator over the minimal single point basis λxλyλz.x z (y (λt.z))) from this bit stream, and runs that algorithm on the remaining input.

Here, have some Perl poetry: https://en.wikipedia.org/wiki/Black_Perl

Algorithms can certainly be elegant. A greedy algorithm with a lot of special cases added to force it to work feels yucky. A simple algorithm that does the minimal amount of work to get the job done and handles all the special cases without case-specific code feels good. Like a well-crafted, reliable tool. It might not be beauty yet, but it's close.

What makes it beautifull in my mind is the same thing that makes some poems beautifull - the fact that it seems simpler than the problem it solves, and yet it solves it well. If it evokes that surprising feeling of "That's it? That's enough?" - then it's beautifull, like a poem which expresses complex feeling in a few short verses.

For me Floyd-Warshall is one example.

Speaking of poems, algorithms, and trees: https://courses.cs.washington.edu/courses/cse461/14sp/lectur...

On trees - how could we neglect the Succinct trees?

Succinctness - expressing trees with as little bits as entropically possible. The representation is as simple as it could be - simply write down nested parentheses whose abstract syntax tree is your given tree. Practically all tree operations in logarithmic or constant time. How it works - recursively with range-min trees and range-max trees - simple and elegant number theory.

A primer - https://arxiv.org/pdf/0905.0768

Im a huge fan of iterative Quickselect and also iterative dfs.

I find especially all their slight variations to be quite poetic.

For me, tree traversal is beautiful.

    traverse(node):
      if node:
        [ 
          ...traverse(node.left), 
          ...traverse(node.right), 
          node.value,
        ]

The pseudo-code recursively produces a list of the node values in post-order.

The author even quoted Sussman but neglected to include Guy Steele’s version:

I think that I shall never see

A matrix lovely as a tree.

Trees are fifty times as fun

As structures a la PL/I

(Which Dijkstra claims are too baroque).

And SNOBOL's strings just can't compare

With all the leaves a tree may bear,

And COMIT strings are just a joke.

Vectors, tuples too, are nice,

But haven't the impressive Hair

Of trees to which a LISP is heir.

A LISPer's life is paradise!

Many people think that JOSS

And others, too, are strictly boss;

And there are many BASIC fans

Who think their favorite language spans

All that would a user please.

Compared to LISP they're all a loss,

For none of them gives all the ease

With which a LISP builds moby trees.

RPG is just a nurd

(As you no doubt have often heard);

The record layouts are absurd,

And numbers packed in decimal form

Will never fit a base-two word

Without a veritable storm

Of gross conversions fro and to

With them arithmetic to do.

And one must allocate the field

Correct arithmetic to yield

And decimal places represent

Truncation loss to circumvent:

Thus RPG is second-rate.

In LISP one needn't allocate

(That boon alone is heaven-sent!)

The scheme is sheer simplicity:

A number's just another tree.

When numbers threaten overflow

LISP makes the number tree to grow,

Extending its significance

With classic tree-like elegance.

A LISP can generate reports,

Create a file, do chains and sorts;

But one thing you will never see

Is moby trees in RPG.

One thing the average language lacks

Is programmed use of push-down stacks.

But LISP provides this feature free:

A stack — you guessed it — is a tree.

An empty stack is simply NIL.

In order, then, the stack to fill

A CONS will push things on the top;

To empty it, a CDR will

Behave exactly like a pop,

A simple CAR will get you back

The last thing you pushed on the stack;

An empty stack's detectable

By testing with the function NULL,

Thus even should a LISPer lose

With PROGs and GOs, RETURNs and DOs,

He need his mind not overtax

To implement recursive hacks:

He'll utilize this clever ruse

Of using trees as moby stacks.

Some claim this method is too slow

Because it uses CONS so much

And thus requires the GC touch;

It has one big advantage, though:

You needn't fear for overflow.

Since LISP allows its trees to grow,

Stacks can to any limits go.

COBOL input is a shame:

The implementors play a game

That no two versions are the same.

And rocky is the FORTRAN road

One's alpha input to decode:

The FORMAT statement is to blame,

But on the user falls the load.

And FOCAL input's just a farce-

But all LISP input comes pre-parsed!

(The input reader gets its fame

By getting storage for each node

From lists of free words scattered sparse.

Its parses all the input strings

With aid of mystic mutterings;

From dots and strange parentheses,

From zeros, sevens, A's and Z's,

Constructs, with magic reckonings,

The pointers needed for its trees.

It builds the trees with complex code

With rubout processing bestowed;

When typing errors do forebode

The rubout makes recovery tame,

And losers then will oft exclaim

Their sanity to LISP is owed —

To help these losers is LISP's aim.)

The flow-control of APL

And OS data sets as well

Are best described as tortured hell.

For LISPers everything's a breeze;

They neatly output all their trees

With format-free parentheses

And see their program logic best

By how their lovely parens nest.

While others are by GOs possessed,

And WHILE-DO, CASE, and all the rest,

The LISPing hackers will prefer

With COND their programs to invest

And let their functions all recur

When searching trees in maddened quest.

Expanding records of fixed size

Will quickly programs paralyze.

Though ISAM claims to be so wise

In allocating overflow,

Its data handling is too slow

And finding it takes many tries.

But any fool can plainly see

Inherent flexibility

In data structured as a tree.

Poetry involves a specific choice of words (perhaps with some thought to metre or rhyme), so if anything, we should expect programs to be as beautiful as poem.

(would there then be algorithms as beautiful as an argument, or functions as beautiful as an idea?)

Especially when you're coding poems using english-lang: https://github.com/theletterf/english-lang

The Fast Fourier Transform.

a moldy oldy (in the tradition of Dijkstra and Euclid):

  proc gcd(n,m): do n>m ⇒ n:=n-m ⫿ m>n ⇒ m:=m-n od; return max(n,m)

EDIT: note the different levels of abstraction: this is a program which implements a particular GCD algorithm, in a manner attempting to reflect the symmetry of the function which that algorithm calculates.

FFT

It depends, are you talking about W.B. Years here, or some bozo from a hip-hop outfit not going three words without saying b*ch?

Minimax search. Such a simple algorithm, but it perfectly solves chess and similar games.

http://archive.vector.org.uk/art10500390

...Roger Hui: In the year 2033 Earth was discovered by Survey Fleet MCXII of the Galactic Empire. The Emperor ordered Earth to send a representative to the court, with strict instructions to “bring something beautiful”.

Emperor

    What beautiful things does Earth have?

Earth Representative

    Your excellency, our...

λx.(λx.f(xx))(λx.f(xx))

Huffman encoding

Binary heap