Turtle Graphics as a Haskell Monad

Question

I'm trying to implement turtle graphics in Haskell. The goal is to be able to write a function like this:

draw_something = do
    forward 100
    right 90
    forward 100
    ...

and then have it produce a list of points (maybe with additional properties):

> draw_something (0,0) 0        -- start at (0,0) facing east (0 degrees)
[(0,0), (0,100), (-100,100), ...]

I have all this working in a 'normal' way, but I've failed to implement it as a Haskell Monad and use the do-notation. The basic code:

data State a = State (a, a) a -- (x,y), angle
    deriving (Show, Eq)

initstate :: State Float
initstate = State (0.0,0.0) 0.0


-- constrain angles to 0 to 2*pi
fmod :: Float -> Float
fmod a 
    | a >= 2*pi = fmod (a-2*pi)
    | a <  0    = fmod (a+2*pi)
    | otherwise = a

forward :: Float -> State Float -> [State Float]
forward d (State (x,y) angle) = [State (x + d * (sin angle), y + d * (cos angle)) angle]

right :: Float -> State Float -> [State Float]
right d (State pos angle) = [State pos (fmod (angle+d))]


bind :: [State a] -> (State a -> [State a]) -> [State a]
bind xs f = xs ++ (f (head $ reverse xs))

ret :: State a -> [State a]
ret x = [x]

With this I can now write

> [initstate] `bind` (forward 100) `bind` (right (pi/2)) `bind` (forward 100)
[State (0.0,0.0) 0.0,State (0.0,100.0) 0.0,State (0.0,100.0) 1.5707964,State (100.0,99.99999) 1.5707964]

And get the expected result. However I can't make this an instance of Monad.

instance Monad [State] where
    ...

results in

`State' is not applied to enough type arguments
Expected kind `*', but `State' has kind `* -> *'
In the instance declaration for `Monad [State]'

And if I wrap the list in a new object

data StateList a = StateList [State a]

instance Monad StateList where
    return x = StateList [x]

I get

    Couldn't match type `a' with `State a'
      `a' is a rigid type variable bound by
        the type signature for return :: a -> StateList a 
          at logo.hs:38:9
    In the expression: x        
    In the first argument of `StateList', namely `[x]'
    In the expression: StateList [x]

I tried various other versions but I never got it to run as I'd like to. What am I doing wrong? What do I understand incorrectly?

Answer 1

The monad you're devising needs to have two type parameters. One for the saved trail (which will be fixed for a particular do sequence) and other for the results of computations.

You also need to think about how to compose two turtle-monadic values so that the binding operation is associative. For example,

right 90 >> (right 90 >> forward 100)

must be equal to

(right 90 >> right 90) >> forward 100

(and of course similarly for >>= etc.). This means that if you represent the turtle's history by a list of points, the binding operation most likely just cannot append the lists of points together; forward 100 alone will result in something like [(0,0),(100,0)] but when it's prepended with rotation, the saved points need to be rotated too.

---

I'd say that the simplest approach would be to use the Writer monad. But I wouldn't save the points, I'd save just the actions the turtle performs (so that we don't need to rotate the points when combining the values). Something like

data Action = Rotate Double | Forward Double

type TurtleMonad a = Writer [Action] a

(This also means that we don't need to track the current direction, it's contained in the actions.) Then each of your functions just writes its argument into the Writer. And at the end, you can extract the final list from it and make a simple function that converts all the actions into a list of points:

track :: [Action] -> [(Double,Double)]

Update: Instead of using [Action] it would be better to use Seq from Data.Sequence. It's also a monoid and concatenating two sequences is very fast, it's amortized complexity is O(log(min(n1,n2))), compared to O(n1) of (++). So the improved type would be

type TurtleMonad a = Writer (Seq Action) a