Finger Exercise β€” The Dragon Curve in Haskell

Posted on 2015-11-17 by fp
Send us your comments.

I really enjoyed the time at university, when I had the opportunity to learn about the syntactic operations that could be used for such boring tasks as compressing files, or to generate really fantastic images while confusing us with broken dimensions and such.

The Dragon Curve is very simple. It starts with a line. This image then is copied, turned by a quarter of a circle and attached to one end of the line. The result is a sequence of two lines.

The algorithm can be repeated and even demonstrated using a strip of paper. Two steps further would yield something like the following.

I had a few minutes of spare time thinking about how easy syntactic manipulation should be in Haskell and half an hour later I had a small program that put out strings of directions E, S, W, N describing a path that resembles a Dragon Curve.

I think that there is beauty in the simplicity of the code. (I simplified it a bit by leaving out type declarations and library names.)

dragoncurves = iterate dragonnext [E]
      where
        dragonnext l = l ++ (map (rotateleft.backwards) (reverse l))

All the Dragon Curves there are can be produced by iteratively applying the algorithm described above. That algorithm is expressed here by the function dragonnext. You give it a string of directions (the variable l) and it takes that string, uses it once as it is and attaches (++) istelf reversed and rotated to itself. The first curve is a unit line going east.

The complete code can be found at github and used to produce things like this:

END—–