Turtle Graphics comme une Monade Haskell

Question

J'essaye d'implémenter turtle graphics dans Haskell. L'objectif est d'être en mesure d'écrire une fonction comme ceci:

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

, puis l'ont produit une liste de points (peut-être avec des propriétés supplémentaires):

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

J'ai tout cela de travail dans un De façon 'normale', mais je n'ai pas réussi à l'implémenter comme une Monade Haskell et à utiliser la notation Do. Le code de base:

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] 

Avec ce je peux maintenant écrire

> [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] 

et obtenir le résultat attendu. Cependant, je ne peux pas en faire une instance de Monad.

instance Monad [State] where 
    ... 

résultats dans

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

Et si j'enveloppe la liste dans un nouvel objet

data StateList a = StateList [State a] 

instance Monad StateList where 
    return x = StateList [x] 

Je reçois

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] 

J'ai essayé diverses autres versions, mais je ne Je l'ai eu à courir comme je le voudrais. Qu'est-ce que je fais mal? Qu'est-ce que je comprends mal?

Answer 1

La monade que vous concevez doit avoir deux paramètres de type. Un pour la trace sauvegardée (qui sera fixée pour une séquence particulière do) et d'autres pour les résultats des calculs.

Vous devez également réfléchir à la façon de composer deux valeurs de tortue-monadique afin que l'opération de liaison soit associative. Par exemple,

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

doit être égale à

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

(et bien sûr de même pour >>= etc.). Cela signifie que si vous représentez l'historique de la tortue par une liste de points, l'opération de liaison ne pourra probablement pas ajouter les listes de points ensemble; forward 100 seul entraînera quelque chose comme [(0,0),(100,0)] mais quand il est ajouté à la rotation, les points enregistrés doivent être tournés aussi.

---

Je dirais que ce serait d'utiliser le Writer monade l'approche la plus simple. Mais je ne sauverais pas les points, je sauverais juste les actions que la tortue effectue (de sorte que nous n'avons pas besoin de faire pivoter les points en combinant les valeurs). Quelque chose comme

data Action = Rotate Double | Forward Double 

type TurtleMonad a = Writer [Action] a 

(Cela signifie aussi que nous ne avons pas besoin de suivre la direction du courant, il est contenu dans les actions.) Ensuite, chacun de vos fonctions juste écrit son argument dans le Writer.Et à la fin, vous pouvez extraire la liste finale de celle-ci et de faire une simple fonction qui convertit toutes les actions en une liste de points:

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

Mise à jour: Au lieu d'utiliser [Action] il serait préférable d'utiliser Seq de Data.Sequence. C'est aussi un monoid et concatenating two sequences est très rapide, sa complexité amortie est O (log (min (n1, n2))), par rapport à O (n1) de (++). Donc, le type amélioré serait

type TurtleMonad a = Writer (Seq Action) a