Turtle Graphics as Haskell Monastery

Question

I am trying to implement tortoise graphics in Haskell. The goal is to write a function like this:

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

and then create a list of points (possibly with additional properties):

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

Everything works fine for me, but I did not implement it as a Haskell Monad and used do-notation. Main 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 cannot make this an instance of Monad .

 instance Monad [State] where ... 

leads to

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

And if I move the list to 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 different versions, but I never started it as I would like. What am I doing wrong? What do I misunderstand?

Answer 1

The monad you are developing must have two types of parameters. One for the saved path (which will be fixed for a specific do sequence) and the other for the calculation results.

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

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

must be equal

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

(and, of course, similarly for >>= , etc.). This means that if you represent the history of turtles using a list of points, the snap operation most likely simply cannot attach the lists of points; forward 100 alone will lead to something like [(0,0),(100,0)] , but when it is added with rotation, the saved points also need to be rotated.

---

I would say that the easiest approach is to use the Writer monad. But I will not save points, I would save only the actions that the turtle performs (so we do not 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 keep track of the current direction contained in the actions.) Then, each of your functions simply writes its argument to Writer . And at the end, you can extract the final list from it and create 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 is also monoid and concatenation of two sequences is very fast, it is the amortized complexity of O (log (min (n1, n2))) compared to O (n1) of (++) . So the improved type will be

 type TurtleMonad a = Writer (Seq Action) a