Turtle Graphics Basics

Some weeks ago, I watched Don't fear the Monads, again. Beckman said something like "there nothing about monads that you don't already know" and "after some time, you'd be inventing monads yourself, but you probably wouldn't know that they were monads". Beckman inspired me to start a small (!) project on Turtle Graphics blog posts.

The idea is to write a very small piece of Haskell code in each post, where every post is a Turtle Graphics implementation. Or, not implementation, but rather just a model, so no real graphics. You can see them as small Turtle Graphics APIs, that focus entirerly on the data and not anything about presenting the data.

Now, not every API is an internal DSL, but for these posts I'll try to put on my language sun-glasses..

First we need a definition of a Turtle:

> data Turtle = Turtle {
>           x :: Double,
>           y :: Double,
>           alpha :: Double -- alpha = 0 means East
>   }
>   deriving (Show)

The first idea (the trivial/naïve implementation) is to define functions with the type signatures Turtle -> Turtle. The functions I have in mind is go, left, right, and rotate, hopefully all self-explanatory. Let's do a type synonym, because it's fun:

> type Command = Turtle -> Turtle

Here are the commands, very basic:

> go, left, right :: Command
> go t = t { x = x t + step * cos (alpha t),
>            y = y t + step * sin (alpha t),
>            alpha = alpha t }

> left t = t { alpha = alpha t + pi/2 }
> right t = t { alpha = alpha t - pi/2 }

> rotate :: Double -> Command
> rotate v t = t { alpha = alpha t + v }

> step = 1

Note that rotate has a different type. Also note the order of the arguments: we can use currying so that if we give rotate just one argument (an angle), we will get a Command.

Let us just see what the user code looks like:

*Main> let t = Turtle {x = 1, y = 1, alpha = 0}
*Main> t
Turtle {x = 1.0, y = 1.0, alpha = 0.0}

*Main> go t
Turtle {x = 2.0, y = 1.0, alpha = 0.0}

We can combine functions with the operator (.)

*Main> (go . go) t
Turtle {x = 3.0, y = 1.0, alpha = 0.0}

And, of course, we can define new functions in terms of the basic ones:

*Main> let go2 = go . go
*Main> go2 t
Turtle {x = 3.0, y = 1.0, alpha = 0.0}

The presentation is a bit rough, especially for non-zero angles..

*Main> right t
Turtle {x = 1.0, y = 1.0, alpha = -1.5707963267948966}

..but I assume you can calculate from radians to degrees in your head.. ;)

As you might have seen, the ordering of arguments for rotate was important:

*Main> (go . (rotate pi) . go) t
Turtle {x = 1.0, y = 1.0000000000000002, alpha = 3.141592653589793}

If the ordering of arguments were different, the above would not have been possible to write. Instead we would have been forced to write a lambda-expression, which is maybe not the best example of a good user code (if you can avoid it, at least).

Note that we also can remove the definitions of left and right, and replace them with

> left' = rotate (pi/2)
> right' = rotate (-pi/2)

Now, a nice feature would be to let a user give a list of Commands and a Turtle to a function, returning the final position:

> runR :: [Command] -> Turtle -> Turtle
> runR [] t = t
> runR (c:cs) t = runR cs (c t)

Here's where I think it can be useful to know something about functions is general. For example, functions with type a -> a forms a monoid [1,2] together with the operator (.) and identity id. This allows us to write runR in a more readable form (now called run):

> run :: [Command] -> Turtle -> Turtle
> run cs t = (foldr (.) id cs) t

A monoid is a nice thing to be, but what is really the purpose with the run function? Isn't the whole goal with a "Turtle Graphics" that we compute a list of positions, so that we can plot them somewhere? It's no use just to calculate a final position: the picture will become pretty boring eventually.. ;)

What we need is a function that takes a list of commands and a start position, returning a list of positions:

> runHistory :: [Command] -> Turtle -> [Turtle]

We make runHistory a wrapper function around runToList:

> runHistory cs t = runToList cs [t]

> runToList :: [Command] -> [Turtle] -> [Turtle]
> runToList [] ts = ts
> runToList _ [] = []
> runToList (c:cs) (t:ts) = runToList cs ((c t) : t : ts)

<Update>

Joel pointed out (in the comments) that runHistory could be written as:

> runHistory = flip (scanr ($)) . reverse

It's of course a lot better than my definition(s), from a readable code perspective. I imagine that my version is more performant (since I do not reverse), but as we all know, performance only matters until you notice the problem (as I pointed out in the comments myself). So, I fell into the trap of pre-optimizing.. Oh my, oh my.

</Update>

Let's try it out:

*Main> runHistory [go,right,rotate pi, go,go] t
[Turtle {x = 2.0, y = 3.0, alpha = 1.5707963267948966},Turtle {x = 2.0, y = 2.0, alpha = 1.5707963267948966},Turtle {x = 2.0, y = 1.0, alpha = 1.5707963267948966},Turtle {x = 2.0, y = 1.0, alpha = -1.5707963267948966},Turtle {x = 2.0, y = 1.0, alpha = 0.0},Turtle {x = 1.0, y = 1.0, alpha = 0.0}]

Hmm, the presentation gets real ugly. Perhaps an implementation of (Show) would be nice, but that's out of scope for this post.

I think there's some smelly code here. We have "bolted on" a history feature on top of the basic commands, so the only knowledge of a history (or log) is in runHistory itself. From a logging perspective, the basic functions do not compose at all! Let me show you what I mean..

Suppose we define a go2 in terms of go (see above). Clearly, we would like go2 to write to the log twice. With the current implementation, this is impossible! There's no way that runHistory can write more than one time to the log, per command. Well, it could be done, but it's not pretty:

*Main> let go2 = [go,go]
(*Main> let prog = [go,go2,go] -- type error)
*Main> let prog = [[go],go2,[go]]
*Main> runHistory (concat prog) t

Even uglier:

*Main> let go3 = [go2,[go]]
(*Main> let prog = [[go],go3,[go]] -- type error)
*Main> let prog = [[[go]],go3,[[go]]]
*Main> runHistory (concat (concat prog)) t

From this, it's obvious that we need to let the basic functions be aware of history/logging. That would be the goal of future posts.


Comment/spoiler: Kenn Knowles has also written a blog post on a Turtle Graphics implementation. Though, the aim of my post(s) is to start out real basic and then evolve the code through several posts. Basically, Kenn's implementation is a "state-over-writer" monad transformer, with a self-implemented difference list as the writer monoid.