我正在尝试实现 turtle graphics在 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]
我尝试了各种其他版本,但我从来没有让它像我想的那样运行。我究竟做错了什么?我怎么理解不正确?
最佳答案
您正在设计的 monad 需要有两个类型参数。一个用于保存的轨迹(将针对特定的 do
序列进行修复),另一个用于计算结果。
您还需要考虑如何组合两个turtle-monadic 值,以便绑定(bind)操作具有关联性。例如,
right 90 >> (right 90 >> forward 100)
必须等于
(right 90 >> right 90) >> forward 100
(当然对于
>>=
等也是类似的)。这意味着如果你用点列表来表示 turtle 的历史,绑定(bind)操作很可能不能将点列表附加在一起; forward 100
单独会导致类似 [(0,0),(100,0)]
但是当它带有旋转时,保存的点也需要旋转。我想说最简单的方法是使用
Writer
单子(monad)。但我不会保存点,我只会保存 turtle 执行的 Action (这样我们在组合值时不需要旋转点)。就像是data Action = Rotate Double | Forward Double
type TurtleMonad a = Writer [Action] a
(这也意味着我们不需要跟踪当前方向,它包含在 Action 中。)然后您的每个函数只需将其参数写入
Writer
.最后,您可以从中提取最终列表并制作一个简单的函数,将所有 Action 转换为点列表:track :: [Action] -> [(Double,Double)]
更新:而不是使用
[Action]
最好使用Seq
来自 Data.Sequence .也是一个monoid和 concatenating two sequences非常快,它的摊销复杂度是 O(log(min(n1,n2))),与 (++)
的 O(n1) 相比.所以改进的类型将是type TurtleMonad a = Writer (Seq Action) a
关于haskell - 作为 Haskell Monad 的 Turtle Graphics,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13331336/