7

Haskell でタートル グラフィックスを実装しようとしています。目標は、次のような関数を記述できるようにすることです。

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

次に、ポイントのリストを生成します（おそらく追加のプロパティを使用）：

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

これはすべて「通常の」方法で機能していますが、Haskell モナドとして実装して do 表記を使用することに失敗しました。基本的なコード:

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]

これで書けるようになりました

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

そして、期待される結果を得る。ただし、これを のインスタンスにすることはできませんMonad。

instance Monad [State] where
    ...

結果は

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

そして、リストを新しいオブジェクトでラップすると

data StateList a = StateList [State a]

instance Monad StateList where
    return x = StateList [x]

私は得る

    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]

他のさまざまなバージョンを試しましたが、思い通りに実行できませんでした。私は何を間違っていますか？何を間違って理解していますか?

4

1 に答える 1

6

考案するモナドには、2つの型パラメーターが必要です。1つは保存された証跡（特定のdoシーケンスに対して修正されます）用で、もう1つは計算結果用です。

また、バインディング操作が結合されるように、2つのタートルモナディック値を構成する方法についても考慮する必要があります。例えば、

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

と等しくなければなりません

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

（そしてもちろん、などについても同様です>>=）。これは、カメの歴史をポイントのリストで表す場合、バインド操作ではポイントのリストを一緒に追加できない可能性が高いことを意味します。forward 100単独では次のような結果になります[(0,0),(100,0)]が、回転が追加されている場合は、保存されたポイントも回転する必要があります。

Writer最も簡単なアプローチは、モナドを使用することだと思います。ただし、ポイントは保存せず、タートルが実行するアクションのみを保存します（値を組み合わせるときにポイントを回転させる必要がないようにするため）。何かのようなもの

data Action = Rotate Double | Forward Double

type TurtleMonad a = Writer [Action] a

（これは、現在の方向を追跡する必要がないことも意味します。これはアクションに含まれています。）次に、各関数は引数をに書き込むだけWriterです。そして最後に、そこから最終的なリストを抽出し、すべてのアクションをポイントのリストに変換する単純な関数を作成できます。

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

更新：使用する代わりに、 Data.Sequenceから[Action]使用することをお勧めします。これはモノイドでもあり、 2つのシーケンスの連結は非常に高速です。償却された複雑さは、のO（n1）と比較してO （log（min（n1、n2））） ）です。したがって、改良されたタイプはSeq(++)

type TurtleMonad a = Writer (Seq Action) a
于 2012-11-11T16:58:52.503 に答える