Lucid for the Practical Haskell Programmer

Dirk van Deun, dirk at
April 2011

These are my original notes, slightly edited to make a coherent story out of them, from when I was learning the basics of Lucid, in which I try to map Lucid code as faithfully as possible onto Haskell.

I have recently spent some days learning Lucid, trying out examples, mostly from the pLucid manual, and then translating them into Haskell. I specifically did not want to write a Lucid interpreter in Haskell, but to explore the correspondences between the languages.

My first big revelation was when I tried this Lucid program:
    x = 0 fby x+1;
    y = 0 fby 0 fby 0 fby 0 fby 0 fby next x;
The output starts with five zeros, and then 1, 2, 3 etc. I had previously supposed that x and y would have been synchronized, so that y would start with five zeros, and then 5, 6, 7 etc. Which would have been harder to map onto Haskell, but actually next just means tail in Haskell.

next x = tail x
prev x = head x : x
I did read in an old paper that in older versions of Lucid one did not define:
ints = 0 fby ints+1
first ints = 0
next ints = ints+1
so in those days streams were actually guaranteed to be synchronous, because there could be no "extra firsts".

It is also easy to define fby in Haskell:
x `fby` y = head x : y
And single values in Lucid correspond to an endless list of that value in Haskell: e.g. 5 becomes repeat 5.

The next step is to write all operations as operations on lists, using zipWith. For the ints above this gives:
ints = (repeat 0) `fby` (zipWith (+) ints (repeat 1))
but a repeat followed by an fby is of course simply a cons, and a zipWith with a repeat in one of the arguments can be written more concisely as a map:
ints = 0 : map (+1) ints
So you will probably not use the fby very often in Haskell; unlike the more complex filters, like upon:
xss@(x:xs) `upon` ~(y:ys) = x : (if y then xs else xss) `upon` ys
(My first definition of upon contained a subtle bug: the next example did not work in Haskell before I had made the rightmost pattern in the definition irrefutable: a and b waited for merge and merge waited for a and b.)

This example comes from the pLucid manual, and it merges the lists of powers of 2 and 3:
    merge = if a<b then a else b fi;
    a = xx upon a eq merge;
    b = yy upon b eq merge;
    xx = 2**i;
    yy = 3**i;
    i = 1 fby i+1;
In Haskell this gives (with upon as defined above):
main = print merge
    merge = zipWith (\a b -> if a<b then a else b) a b
    a = xx `upon` zipWith (==) a merge
    b = yy `upon` zipWith (==) b merge
    xx = map (2^) i
    yy = map (3^) i
    i = 1 : map (+1) i
I would dare say that the structure of the original is kept intact very nicely.

There are of course practical problems in converting code, for instance because Haskell is statically typed and Lucid is not, and also because IO works automagically in Lucid but has to be done explicitly in Haskell. An example with IO, being a translation of this example from the pLucid manual:

[% "smallest", s , "largest", h %]
    s = x fby if next x < s then next x else s fi;
    h = x fby if next x > h then next x else h fi;
(Each time the user enters a number, the highest and the lowest number up till here are shown.)
import Data.List
import Data.Maybe

parse =
  unfoldr (listToMaybe . reads) :: String -> [Integer]
unparse =
  concatMap (\(s1, i1, s2, i2) -> s1 ++ show i1 ++ s2 ++ show i2 ++ "\n")

main = interact $ \str ->
    x = parse str
    s = head x : zipWith (\x s -> if x < s then x else s) (tail x) s
    h = head x : zipWith (\x h -> if x > h then x else h) (tail x) h
    unparse $ zipWith (\s h -> ("smallest ", s, " largest ", h)) s h
In main the structure of the original is kept intact, apart from where I have replaced the while by a let, because inside a while the argument str would not have been in scope. (The while of Haskell is rather specialized, the let is more general.) A parse and pretty print have been added, and everything is wrapped in an interact.

This is old-fashioned IO, as it was done before the IO Monad was introduced. The interact passes all input that the program receives as one long lazy string to a function, and the result of this function (also a lazy string) is the output of the whole program. I had never given much thought to the fact that this combines so well with data flow programming: input and output are nicely interleaved.

The hardest thing to translate elegantly is is current. Here is an example with nested loops in Lucid, a program that for each two numbers of input x and n, computes x^n:
p asa index eq N
    X is current x;
    N is current n;
    p = 1 fby p * X;
The is current statements "freeze" the variables x and n, so that for each pair of x and n, a complete stream p is made (based on the frozen x) and also a complete stream of index eq n. The expression p asa index eq N then maps an "as soon as" over what are actually two streams of streams, and then only uses the "firsts" of the results to construct a single output stream, that once again "runs at the same speed" as the streams of x and n.

Which is strange stuff. I had to translate this a bit less literally: instead of declaring somewhere "this variable is now frozen", I say at the places where it is used: "do this with a frozen version of that variable".

The resulting program is pretty long, but that is also caused by the code for parsing and pretty printing, and for distributing the input stream over streams of x and n. Anyway, this is how I rendered it (the whenever, asa and index are just "literal" translations of the Lucid primitives; the magic is in the withCurrent and collapseAsa):
import Data.List
import Data.Maybe

x `whenever` y = map fst $ filter snd $ zip x y
x `asa` y = repeat $ fst $ head $ filter snd $ zip x y

index = 0 : map (+1) index

withCurrent = map
collapseAsa a b = map head $ zipWith asa a b

parse =
  unfoldr (listToMaybe . reads) :: String -> [Integer]
unparse =
  concatMap (\i -> show i ++ "\n")

main = interact $ \str ->
    input = parse str
    select = True : False : select

    x = input `whenever` select
    n = input `whenever` map not select

    p = withCurrent (\x -> let p = 1 : map (*x) p in p)
    s = withCurrent (\n -> map (==n) index)
    unparse $ (p x) `collapseAsa` (s n)  -- s = "selector"
Once again, for a really faithful translation, we should use repeat x and repeat n instead of x and n in the definitions for p and s, and zipWith instead of map.

In all the examples of the use of is current that I found, the collapse back into one dimension is done using asa. I have no idea whether you can also collapse using whenever or something, and what it should mean if you did so. (When not used for collapsing, asa produces constant streams, so taking only the firsts when collapsing is the obvious approach.) According to the same older paper I referred to earlier, asa is more fundamental than whenever and upon and such, so perhaps you should indeed only do this using asa ?

At this point I seem to have treated everything that is really typical for Lucid. So in conclusion: there is a whole lot of Lucid that can be translated into Haskell very faithfully; only the strange is current should be translated more freely.

Post Scriptum

I thought I had found something that would not work in Haskell, namely looking forward in a stream to construct earlier elements of that same stream:
    x = 0 fby 1 fby 2 fby 4 fby 0 fby 7 fby x;
    howfar = if x eq 0 then 0 else 1 + next howfar fi;
(How long until we will see another zero in the input stream x ?)

But using my own zipWith with irrefutable patterns, this wil work too:
irZipWith f ~(a:as) ~(b:bs) = f a b : irZipWith f as bs

main = print howfar
    x = 0: 1: 2: 4: 0: 7: x
    howfar = irZipWith (\x h -> if x == 0 then 0 else 1 + h) x (tail howfar)
A zip that can look into its own future: I would probably never have thought of it without learning Lucid, but Haskell can do it.

Back to Dirk van Deun's Web 1.0 blog