Playing Haskell

Richard Suchenwirth 2001-12-11 - 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)
• a non-strict programming language (i.e. it allows functions that are not strict, and hence allows lazy evaluation; it uses lazy evaluation a lot)
• purely functional, i.e. exclude destructive modifications (updates)

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

See also Functional composition where Haskell's "." turns into a Polish comma...

The first shot above still didn't satisfy me. Therefore I devised this: a proc whose name is the empty string, which is the shortest (and hence canonical) of infinitely many string reps of the empty list. You cannot write that name by itself, but have to quote "" or brace {} it. Called with no arguments, the proc returns an empty string (which is its own name); called with arguments, it returns 1 if the first argument is an empty list, or 0 otherwise. So it serves both as a constructor and tester for empty lists. And here is the code:

proc {} args {if [llength $args] {expr ![llength [lindex $args 0]]}}

With this, we can rewrite qsort to:

% proc qsort L {
    if [[] $L] []   else {
   : $L 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]
    }
}
% qsort {3 7 1 5 2 0 4}
0 1 2 3 4 5 7

See List Comprehension for another Tcl take on Haskell. Also, Tcl'ers might have a particular interest in reading "Haskell Community Reports" [L1 ] (20110127 -- fixed link, CliC).

SZ: I've implemented Algebraic types of Haskell. Right now you can rewrite all strings as pure List of Char:

# instead of "hi!" you should declare type
atype List {{Nil} {List head tail}}
# and write
set string [List h [List i [List ! Nil]]]

and do some symbolic optimization on your expression trees like that:

# optimize expressions.
proc optimize {expr} {
  match $expr {
     {Plus {Const 0} $x} { return $x }
     {Mul {Const 1} $x} { return $x }
     {Mul {Const 0} $x} { return [Const 0]}
     $etc
  }
}

this is somewhat wordy comparing to native Haskell, but more clear (in my taste) than lassign'ing and comparing by hand.

AM (25 august 2004) Here is a Tcl implementation of the Haskell function "foldn":

The function foldn is defined by the following equations:

foldn f c 0 := c
foldn f c n+1 := f (foldn f c n)

where f is a function, c is a constant and n is the one (integer) argument.

In Tcl this may become:

proc foldn {f c n} {
   if { $n < 0 } { 
     return -code error "Argument can not be negative"
   }

   if { $n == 0 } {
      return $c
   } else {
      return [$f [foldn $f $c [incr n -1]]]
   }
}

The advantage of foldn in Haskell is that you can concisely define all kinds of functions, such as a function to compute the Fibonacci numbers:

    fib := first . foldn g {0 1} n
     where g {m n} = {n m+n}

and first takes the first element of a pair (conveniently written as a Tcl list :))

Well, this ought to be elaborated a bit further ...