2012-11-11 25 views
7

Sto cercando di implementare turtle graphics in Haskell. L'obiettivo è quello di essere in grado di scrivere una funzione come questa:Turtle Graphics come Haskell Monad

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

e poi farlo produrre un elenco di punti (magari con proprietà aggiuntive):

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

ho tutto questo lavoro in un 'normale', ma non sono riuscito a implementarlo come Haskell Monad e ad usare la notazione. Il codice di 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] 

Con questo ora posso scrivere

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

E ottenere il risultato atteso. Tuttavia, non posso rendere questa un'istanza di Monad.

instance Monad [State] where 
    ... 

risultati in

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

e se mi avvolgo la lista in un nuovo oggetto

data StateList a = StateList [State a] 

instance Monad StateList where 
    return x = StateList [x] 

ottengo

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] 

ho provato varie altre versioni, ma non ho mai ottenuto di funzionare come mi piacerebbe. Che cosa sto facendo di sbagliato? Cosa capisco in modo errato?

+0

Dovrebbe essere possibile implementare una monade turtlegraphics, facendo crescere una storia di posizioni e intestazioni di tartaruga. Ma il modo in cui stai cercando di implementare un'istanza di 'Monad' confonde il tipo usato per rappresentare i numeri in questa storia con i tipi di valori in generale. Il tuo 'ret' e' bind' riguardano calcoli che considerano solo gli stati come valori. Ma 'return' e' >> = 'dovrebbero spiegare come organizzare calcoli riguardanti valori di qualsiasi tipo, alcuni dei quali potrebbero anche estendere la traccia della tartaruga. – pigworker

+0

Se si desidera che la "monade" generi una lista di punti, si può desiderare Writer + Stato piuttosto che Stato. Lo scrittore è in genere il "monade dell'accumulazione" sebbene possa funzionare in altri modi. Per progredire devi anche considerare perché le monadi di stato sono funzioni avvolte da un 'newtype' - sono funzioni dallo stato corrente a una coppia di nuovi stati più una risposta, non solo un nuovo stato. Spesso la risposta è 'unit' aka(). per esempio, forward sarebbe tipicamente 'forward :: Float -> Turtle()' assumendo una monade chiamata Turtle. –

risposta

6

La monade che stai progettando deve avere due parametri tipo. Uno per la traccia salvata (che verrà riparata per una particolare sequenza do) e un'altra per i risultati dei calcoli.

È inoltre necessario pensare a come comporre due valori tartaruga-monadici in modo che l'operazione di associazione sia associativa. Ad esempio,

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

deve essere pari a

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

(e naturalmente similmente per >>= ecc). Ciò significa che se si rappresenta la cronologia della tartaruga mediante un elenco di punti, molto probabilmente l'operazione di rilegatura non può aggiungere le liste di punti insieme; forward 100 da solo si tradurrà in qualcosa come [(0,0),(100,0)] ma quando è prepended con rotazione, i punti salvati devono essere ruotati anche.


Direi che l'approccio più semplice sarebbe quella di utilizzare il Writer monade. Ma non salverei i punti, salverei solo le azioni che la tartaruga esegue (in modo che non abbiamo bisogno di ruotare i punti quando si combinano i valori). Qualcosa di simile

data Action = Rotate Double | Forward Double 

type TurtleMonad a = Writer [Action] a 

(Questo significa anche che non abbiamo bisogno di tracciare la direzione della corrente, è contenuta nelle azioni.) Quindi ciascuna delle vostre funzioni appena scrive la sua tesi nel Writer.E alla fine, è possibile estrarre l'elenco definitivo da esso e fare una semplice funzione che converte tutte le azioni in un elenco di punti:

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

Aggiornamento: Invece di usare [Action] sarebbe meglio usare Seq da Data.Sequence. È anche un e concatenating two sequences è molto veloce, la sua complessità ammortizzata è O (log (min (n1, n2))), rispetto a O (n1) di (++). Quindi il tipo migliorato sarebbe

type TurtleMonad a = Writer (Seq Action) a