Turtle Graphics作为Haskell Monad

Question

我正在尝试在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 Monad实现并使用do-notation.基本代码:

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]

我试过各种其他版本,但我从来没有像我想的那样运行它.我究竟做错了什么？我错误地理解了什么？

Answer 1

你正在设计的monad需要有两个类型参数.一个用于保存的跟踪(将针对特定do序列固定),另一个用于计算结果.

您还需要考虑如何组合两个turtle-monadic值,以便绑定操作是关联的.例如,

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

必须等于

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

(当然也是类似的>>=).这意味着如果您通过点列表表示乌龟的历史记录,则绑定操作很可能无法将点列表附加在一起; forward 100单独会产生类似的东西,[(0,0),(100,0)]但是当它旋转前,保存的点也需要旋转.

我会说最简单的方法是使用Writermonad.但我不会保存点数,我只保存龟执行的动作(这样我们在组合值时不需要旋转点).就像是

data Action = Rotate Double | Forward Double

type TurtleMonad a = Writer [Action] a

(这也意味着我们不需要跟踪当前的方向,它包含在动作中.)然后你的每个函数都将其参数写入Writer.最后,您可以从中提取最终列表,并创建一个将所有操作转换为点列表的简单函数:

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

更新:而不是使用[Action]它会更好地使用Seq从Data.Sequence.这也是一个独异而连接两个序列是非常快的,它的摊销复杂度为O(日志(分(N1,N2)))相比,O(N1)的(++).所以改进的类型将是

type TurtleMonad a = Writer (Seq Action) a