海龟图形作为 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]

我尝试了各种其他版本，但始终无法按照我的意愿运行。我做错了什么？我理解错误了什么？

- iliis

---

应该可以实现一个海龟图形的单子，记录海龟位置和方向的历史。但是你尝试实现Monad实例的方式混淆了用于表示历史中数字的类型与一般值的类型。你的ret和bind只涉及将状态作为值进行计算。但是return和>>=应该解释如何组织涉及任何类型值的计算，其中一些可能也会扩展海龟的路径。 - pigworker

如果你希望“单子”生成一系列点，则可能需要使用Writer+State而不是State。Writer通常是“积累单子”，但它也可以以其他方式工作。要进步，您还需要查看状态单子为什么是由newtype包装的函数-它们是从当前状态到新状态加答案对的函数，而不仅仅是新状态。通常答案是unit即()。例如，假设有一个叫Turtle的单子，那么forward通常会是forward :: Float -> Turtle ()。 - stephen tetley

Answer 1

你正在设计的单子需要有两个类型参数。一个是保存路径的（将为特定的do序列固定），另一个是计算结果的。

你还需要考虑如何组合两个turtle-monadic值，使得绑定操作是结合律的。例如：

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

更新： 与其使用[Action]，最好使用Data.Sequence 中的Seq。它也是一个Monoid，并且连接两个序列非常快，它的摊销复杂度为O(log(min(n1,n2)))，而不是(++)的O(n1)。因此，改进后的类型将是：

type TurtleMonad a = Writer (Seq Action) a

- Petr