Version 8 of Playing Haskell

Richard Suchenwirth - Haskell (http://www.haskell.org , a Tcl binding at http://www.dcs.gla.ac.uk/~meurig/TclHaskell/ ) is a functional programming language (see Steps towards functional programming) that is characterized by

extreme brevity (well, maybe APL is still shorter;-)
"executable specifications" (declarative language)
some similarities to Prolog

Let's just start with an example from the Haskell site, quick sort:

 qsort []     = []
 qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
                 where
                   elts_lt_x   = [y | y <- xs, y < x]
                   elts_greq_x = [y | y <- xs, y >= x]

Prolog similarity: you can write multiple definitions for a function that are distinguished by the argument structure: the first line deals with empty list, the second with other lists whose head and tail are immediately parsed into two variables x and xs (another Prolog similarity). The second case results in a concatenation of:

the results of qsort on elts_lt_x
a list with x as single element
the result of qsort on elts_greq_x

where (am I explaining? I'm just repeating the program!) elts_lt_x is the list of all y's that are element of xs for which y < x holds, and elts_greq_x accordingly.

Whew. Seeing things like this, I always ask myself "Can we have that in Tcl too?" Well, Tcl is Polish (command/operator always comes first), while lots of Haskell's magic is done with infix operators. We would have to write a single qsort proc that does the case distinction; we would have to produce the two partial lists before concatenating them as result; but yes, in a certain way we can:

 proc qsort list {
     if {![llength $list]} {
        list
     } else {
           : $list x xs          ;# explicit head-tail parsing
           = elts_lt_x   [| y <- $xs {$y <  $x}]
           = elts_greq_x [| y <- $xs {$y >= $x}]
        ++ [qsort $elts_lt_x] [list $x] [qsort $elts_greq_x]
     }
 }
 #----- or, without the two intermediate variables, but less readable:
 proc qsort list {
     if {![llength $list]} {
        list
     } else {
           : $list x xs          ;# explicit head-tail parsing
        ++ [qsort [| y <- $xs {$y<$x}]] [list $x] [qsort [| y <- $xs {$y>=$x}]]
     }
 }

I have named the helper procedures like the Haskell operators (or aliased some to existing Tcl commands), so the parallels are better visible. But remember - even if they look the same, they are still prefix operators!

 proc : {list *h *t} {
     upvar 1 ${*h} h ${*t} t
     set h [lindex $list 0]
     set t [lrange $list 1 end]
 }
 proc | {*i "<-" list cond} {
     set res {}
     upvar ${*i} i
     foreach i $list {
         if {[uplevel expr $cond]} {lappend res $i}
     }
     set res
 }
 interp alias {} =  {} set
 interp alias {} ++ {} concat