Lambda the Ultimate

Not that you're necessarily wrong in general, but is this so terrible: [in scheme]

;; ^ is the string-joining operator

(define (concat lst)
  (if (null? lst) ""
      (^ (car lst)
         (fold-right (lambda (str rest) (^ ", " str rest) )
		     ""
		     (cdr lst))
	 ) ) )

or, if we can use 'cut' to curry ^,

(define (concat lst)
  (if (null? lst) ""
      (^ (car lst)
	 (fold-right (cut ^ ", " <...>) "" (cdr lst))
	 ) ) )

and there are other options using pattern-matching to handle the (null? lst) case & still using fold-right for the recursion.

(define (concat lst)
  (fold-right (lambda (str rest)
		(^ str (if (equal? rest "") "" ", ") rest) )
	      ""
	      lst)
  )

(concat '("" "")) should be ", ", not "".

well the fold version isn't really that complex. Actually i think it's shorter but I wouldn't claim it to be more elegant, just that then you get used to it there isn't much that can't be done with a fold. So if you excuse my Haskel:

concat []  = ""
concat h:t = fold h t (\acc el -> acc ++ "," ++ el)

Here's another way to solve this problem in Haskell:

import List

join joiner = concat . intersperse joiner
comma_join = join ", "

intersperse is written using recursion, but I can avoid both iteration and recursion in my code, and I like that.

On the original topic, the looping construct looks similar to Haskell's do. For example, Figure 1 could be expressed like this:

do x verbose code using x>
   guard $ q <verbose code using y>
   let z = <verbose expression>
   return <z expression>

I'm curious if the quicksort example can be expressed in Haskell in a similar way. Its destructive operations look tricky, but maybe it's possible for someone skilled with monads.

I wouldn't claim it to be more elegant,

But for someone who understands what fold does, it is elegant. If we have an associative operator * (which is really a function S->S->S for some type S such that (a*b)*c = a*(b*c)) then fold just simply places that operator between all the elements of the list. In this case our operator (function) puts a comma between two strings ("A"*"B"="A,B", this is what the lambda expression does) and since ("A"*"B")*"C" = "A,B"*"C" = "A,B,C" = "A"*"B,C" = "A"*("B"*"C") we know that our operator is associative. Thus when we apply a fold on a list with this operator, we get the desired result.

What I'm trying to say is, for somebody that understands what fold does, the function that uses fold in its definition seems elegant and simple. For somebody that doesn't understand what fold does, it seems mysterious and complicated. On the other hand, any sort of loop definition will be simple to understand for both people.

Oh, and I forgot to say. I think concatenating a list of strings with commas between each string isn't a very good example. I'm sure there are better examples of functions that are complicated for fold and friends but simple when defined in the "natural" ML (or whatever) solution. (I do have to admit the "natural" solution is more accessible, so I understand what Mr. Krishnaswami is trying to say.)

I think the reason for the advantage in "natural-ness" of the patterns+recursion style of definition becomes apparent when you try to prove the correctness of your functions: you'll find it easier to structure your program so that its structure parallels the structure of the proof.

This is because, when you write down a program proof, you want to structure it with two parts: a use of induction, and a case analysis with some specialized reasoning in each case. CH-style, use of an inductive argument corresponds to writing a recursive function, and case analysis corresponds to pattern matching. The correctness of the function depends on the patterns being exhaustive -- covering all the possibilities -- and for the recursion being well-founded.

Folds combine case analysis and recursion, which means that proofs of correctness for functions written using them are elegant if and only if both the recursion scheme and the case analysis of the proof match what the fold encodes.

Now, the advantage of folds over general recursion is that they are guaranteed to terminate. However, if you use a type system for checking termination, then I am not convinced that using elimination constants has any advantage at all.

Inductive proofs all structure the induction slightly differently each time (there's induction, course-of-values induction, structural induction, and so on), and your HOF encodes exactly one such induction scheme.

In "Recursion schemes from comonads", Tarmo Uustalu, Varmo Vene, and Alberto Pardo show how you can use a comonad-parameterized fold to recover most of recursion schemes you mentioned.

"Recursion schemes from comonads" on Google Scholar.

Let's say, as another simple example, that you want to output lines while cycling through a list of colours, something that comes up fairly often in HTML-generation, for example.

In Haskell, I would do something like zipWith coloredLine (concat $ repeat colors) lines, and either map or fold the result.

Of course, that doesn't work so well without lazy evaluation.

Of course, that doesn't work so well without lazy evaluation.

Even in a language like Python you can very easily build up an iterator algebra vocabulary using generators. It's a much less elegant approach than relying on lazy evaluation, but once you have built up that vocabulary it is very convenient to use.

I phrased that badly. It is not that the scope is non-lexical; it is that it doesn't correspond to standard lexical nesting. Although this is not a precise description, it is rather as though the scope works like this:

(loop
   (subloop (loop (for colour in-vector colours)    ⎫   ))
   (subloop (for line in lines)                     ⎭↴  )
 ↳(save (coloured-line line colour)))

That is, the lexical context splits between the subloops, but then rejoins and flows into the (non-contained) (save …). That mirrors the execution flow: the two subloops are iterated in parallel, and the remaining clauses are evaluated once both subiterations have come up with a binding, but it is not dynamic scoping: the scope is entirely static.

Oh! is there an implementation of this loop-parallel avaible anywhere (accesable) ?