Grafika żółwia jako moneta Haskella

Question

Próbuję zaimplementować turtle graphics w języku Haskell. Celem jest, aby móc napisać funkcję tak:

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

a następnie go produkować listę punktów (być może z dodatkowymi właściwościami):

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

mam wszystkie te pracujące na "normalny" sposób, ale nie udało mi się go zaimplementować jako Monady Haskella i użyć do-notacji. Kod podstawowy:

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] 

Dzięki temu mogę teraz napisać

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

i uzyskać oczekiwany rezultat. Jednak nie mogę uczynić tego przykładem z Monad.

instance Monad [State] where 
    ... 

skutkuje

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

i gdybym owinąć listę w nowym obiekcie

data StateList a = StateList [State a] 

instance Monad StateList where 
    return x = StateList [x] 

uzyskać

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] 

Próbowałem różne inne wersje, ale nigdy kazał mi biec, jak bym chciał. Co ja robię źle? Co rozumiem niewłaściwie?

Answer 1

Monada, którą wymyślasz, musi mieć dwa parametry typu. Jeden dla zapisanego śladu (który zostanie ustalony dla określonej sekwencji do) i drugi dla wyników obliczeń.

Musisz także przemyśleć, jak skomponować dwie wartości monadyczne żółwia, aby operacja wiązania była asocjacyjna. Na przykład,

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

musi być równa

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

(oczywiście podobny do >>= etc.). Oznacza to, że jeśli reprezentujesz historię żółwia za pomocą listy punktów, operacja wiązania najprawdopodobniej nie może dołączyć list punktów łącznie; forward 100 sam spowoduje, że pojawi się coś takiego jak [(0,0),(100,0)], ale gdy jest on wcześniej z rotacją, zapisane punkty również muszą zostać obrócone.

---

powiedziałbym, że najprostszym rozwiązaniem byłoby użyć Writer monady. Ale nie zapisałbym punktów, zachowałbym tylko akcje wykonywane przez żółwia (abyśmy nie musieli obracać punktów podczas łączenia wartości). Coś jak

data Action = Rotate Double | Forward Double 

type TurtleMonad a = Writer [Action] a 

(oznacza to również, że nie musimy śledzić aktualny kierunek, to zawarte w działaniach). Następnie każda z twoich funkcji tylko pisze swój argument do Writer.A na koniec, można wyodrębnić ostatecznej listy od niego i zrobić prostą funkcję, która przekształca wszystkie działania na listę punktów:

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

Aktualizacja: Zamiast [Action] byłoby lepiej wykorzystać Seq z Data.Sequence. Jest także bardzo szybki, jest on bardzo złożony: O (log (min (n1, n2))), w porównaniu do O (n1) z (++). Tak więc ulepszony typ byłby

type TurtleMonad a = Writer (Seq Action) a