Turtle Graphics :: The big refactoring

Last time on "Turtle Graphics", we ended up having the type Turtle -> [Turtle] on functions. The combine function had the type [Turtle] -> (Turtle -> [Turtle]) - Turtle. Let's have some "fun"!

First, we add a helpful parameter to the turtle - penIsDown, i.e., the turtle is writing.

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

We then add two useful functions for pen modification:

penDown t = let t' = t {penIsDown = True} in Logged {value = t', logs = [t']} 

penUp t = let t' = t {penIsDown = False} in Logged {value = t', logs = [t']}

Second, we assume that it would be useful to split the functionality of returning a value and log, pretty much following separation of concerns. We could do this in a tuple, but I prefer having names on things:

data Logged l = Logged {
value :: l, 
logs :: [l]  }  deriving (Show)

This has some implications on our code. All the "core" functions must now return both a turtle value and a singleton log. Oh, and by the way, the Command type changed as well.

type Command = Turtle -> Logged Turtle

go, left, right, penDown, penUp :: Command
go t =  let t' = t {x = x t + step * cos (alpha t),
                   y = y t + step * sin (alpha t)
                  }
       in Logged {value = t', logs = [t']}  

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

penDown t = let t' = t {penIsDown = True} in Logged {value = t', logs = [t']} 
penUp t = let t' = t {penIsDown = False} in Logged {value = t', logs = [t']}

We must also change the function for combining functions:

(|>|) :: Logged Turtle -> Command -> Logged Turtle 

logged |>| f = let logged' = f (value logged)
              in Logged {value = value logged',
                         logs = logs logged' ++ logs logged}

As you see, there's a lot of duplicate code. Let's do an ExtractMethod (sort of):

logThis val = Logged {value = val, logs = [val]}

go, penDown, penUp :: Command
go t =  logThis $ t {x = x t + step * cos (alpha t),  
                    y = y t + step * sin (alpha t) }  
penDown t = logThis $ t {penIsDown = True}
penUp t = logThis $ t {penIsDown = False}

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

Still, we could be more generic in our logging type. That is, there is still a restriction on that the value returned and the log have the same type: the log is a list of the same type as the value has. We try to relax this restriction:

data Logged v l = Logged {
 value :: v,
 logs :: l 
}
deriving (Show)

Maybe we did too much, logs isn't a list anymore. However, if it's really necessary, we'll find out through type inference. It's not obvious that we really need a list, just something we can append "stuff" to. Anyway, we get some compiler errors now:

`Logged Turtle' is not applied to enough type arguments Expected kind `?', but `Logged Turtle' has kind `k -> *' In the type synonym declaration for `Command'

We "fix" this by removing the Command type synonym and all references to it. I have a feeling that we'll need to fiddle some more with the types, so right now they're only in the way. If the types really are needed, we will find out (by a compiler error)! Though, it could be interesting to see what the type of e.g., "go" is:

*Main> :t go
go :: Turtle -> Logged Turtle [Turtle]

Ah, just what I expected, but was too lazy too write. ;) Let's check the combining function:

*Main> :t (|>|) 
(|>|) :: Logged v [a] -> (v -> Logged v1 [a]) -> Logged v1 [a]

Hmm, this is rather weird! Before, the function was strongly bound to the Turtle type, which doesn't seem to be the case anymore. Moreover, we see that the input value type (v) doesn't need to be the same as the output value type (v1). How cool is that!?! It would be hard for me to look at the function and calculate the type myself, but Haskell just inferred the most generic type it could find. Coolness!

As always, a design pattern can be hard to spot, especially if you haven't spotted it before. Here's how Gregg Irwin puts it (from an Øredev presentation by Jimmy Nilsson):

1. You use it without being aware that you’re using it
2. You hear about it, read up on it, and tinker a bit
3. You learn more and start using it explicitly, if naively
4. You get the fire and evangelize (optional)
5. Something ”clicks”
6. You learn more and apply it ”less naively”and more implicitly
7. Time passes and you see flaws
8. You question the concept (often because you misapplied it)
9. You either forget about it or add knowledge and experience
(Repeat steps 5-9 if necessary)
10. You use it without being aware that you are using it

Essentially, our Logger type is a monad. Or, actually, the type of |>| resembles >>=, which is the associative function that composes a particular monad. Since monads are important in Haskell, some syntactic sugar (the do-notation) has been added to make it easier to work with them.

Let's try to instantiate the monad class:

instance Monad (Logged a b) where

We get a compiler error:

Kind mis-match
Expected kind `* -> *', but `Logged a b' has kind `*'
In the instance declaration for `Monad (Logged a b)'

We try to remove both type parameters:

instance Monad (Logged) where

..but still an error (yet, another one)

`Logged' is not applied to enough type arguments
Expected kind `* -> *', but `Logged' has kind `* -> * -> *' 
In the instance declaration for `Monad (Logged)'

As you might see, we need to bind one of the types, whereas the other one needs to be "free". This puts us in a dilemma, since we know that we have both a type "v" and "v1". Thus, the type of the log must be bound (or, at least given a parametrized name):

data Logged l v = Logged {  --notice the different order      
 value :: v,
 logs :: l
}
deriving (Show)

instance Monad (Logged l) where

So Logged is missing out one type parameter. It's kind of a function over types, that takes a type and returns another type - just as the error message above implied. Though, we get an error again when we try to implement bind:

instance Monad (Logged l) where  l >>= f = l |>| f

Couldn't match expected type `[a]' against inferred type `l' (a rigid variable)   
`l' is bound by the instance declaration at writer5.hs:46:0 
Expected type: Logged [a] v      
Inferred type: Logged l a1    
In the first argument of `(|>|)', namely `l'    
In the expression: l |>| f

Now, we actually need to say that the log is a list. Maybe we can remove this requirement in a later blog post, but right now we go with the compiler.

data Logged l v = Logged {
 value :: v,
 logs :: [l] 
}
deriving (Show)

Hey, it works! Or, at least it compiles. But that tends to be synonyms in Haskell ;) We specify "return":

instance Monad (Logged l)
where  l >>= f = l |>| f 
return val = Logged {value = val, logs = []}

Notice that we can still use |>| as usual:

*Main> start |>| go |>| go  
Logged {value = Turtle {x = 2.0, y = 0.0, alpha = 0.0, penIsDown = True},
logs = [Turtle {x = 2.0, y = 0.0, alpha = 0.0, penIsDown = True},
Turtle {x = 1.0, y = 0.0, alpha = 0.0, penIsDown = True},
Turtle {x = 0.0, y = 0.0, alpha = 0.0, penIsDown = True}]}

So, why all this trouble? Well, it wasn't that hard! Essentially, all we did was to make the logging a bit more separated and generic. Then we adjusted the types a bit to make them align with Haskell's monad class. The big win is that our Logger is now reusable if we want to log something else than turtles in the future. So, by adjusting towards a common pattern, we gained both syntactic sugar and reusability.

Of course, there are some ways to improve. I'll perhaps cover this in future posts. Oh, and by the way, our Logger monad is actually the Writer monad. Just thought you should know that.. ;)

Conclusion: Brian Beckman was right, we've invented monads by ourselves, maybe without thinking about it. Or?

Note: Since I'm not a master in category theory, I'm not sure if Logger actually was a "real" monad (strictly speaking), before we changed the order of the type parameters and removed a type parameter in the monad instantiation, making it have the right kind. Any ideas?