我写的是一个真正的 monad 吗？

Question

我一直在努力理解 monad，自从我最近理解了什么是拉链后，我想我可能会尝试将这两种想法结合起来。 (>>=) 做了我认为 monad 应该做的事情，即它让我以 moveRight >>= moveLeft >>= goAhead >>= return 的形式结合拉链周围的运动，但我觉得我错过了一些东西，因为除其他外，我不能它的类型似乎符合 monad 应该是什么，即 Ma -> (a -> Mb) -> Mb。欢迎任何帮助。

module MonadZipper where

import Prelude hiding (return, (>>=))

data Node a = Fork a (Node a) (Node a)
            | Passage a (Node a)
            | DeadEnd a
              deriving (Show)

data Branch a = TurnLeft a (Node a)
              | TurnRight a (Node a)
              | StraightAhead a
                deriving (Show)

type Trace a = [Branch a]
type Zipper a = (Trace a, Node a)


type Movement a = Zipper a -> Maybe (Zipper a)
--not sure whether this wrapping makes sense

turnLeft :: Zipper a -> Maybe (Zipper a)
turnLeft (t, (Fork v l r)) = Just (TurnLeft v r:t, l)
turnLeft _                 = Nothing

turnRight :: Zipper a -> Maybe (Zipper a)
turnRight (t, (Fork v l r)) = Just (TurnRight v l:t, r)
turnRight _                 = Nothing

goAhead :: Zipper a -> Maybe (Zipper a)
goAhead (t, Passage v a) = Just (StraightAhead v:t, a)
goAhead _                = Nothing

(>>=) :: Movement a -> Movement a -> Movement a
(>>=) turner func = \zippo ->
                      case turner zippo of
                        Nothing -> Nothing
                        Just tree -> func tree

return :: Zipper a -> Maybe (Zipper a)
return tree = Just tree

Answer 1

您的 Movement 类型很像 Maybe monad（允许失败的移动）加上 State monad 与当前 Zipper a 的组合州：

State (Zipper a) b  =  Zipper a -> (b, Zipper a)

我在用 = 作弊。这不是 State 类型的精确定义，但这些类型是同构的，因此您可以认为 State 等于此类型。

换句话说，您已经接近重新发明基于 transformer 的 monad：

type Movement' a b = StateT (Zipper a) Maybe b

主要区别在于 Movement' a b 同构于：

Zipper a -> Maybe (b, Zipper a)

因此它具有您未包含的额外 b 值。

太棒了....

如果您要将 Movement 类型重写为：

type Movement a b = Zipper a -> Maybe (b, Zipper a)

你会有所作为的。这里，Movement 不是 monad——相反，Movement a 是一个可以应用于基础类型 Movement a b.

的 monad

如果您熟悉 Either 作为 monad，那是一回事：Either 本身不是 monad，但 Either String 是一个可以应用于 Either String Double 之类的另一种类型，以表示 return 是 Double 结果或 String 错误消息的计算。

同样，您的 Movement a 是一个单子，可以应用于另一种类型 Movement a b 以表示 return 是 b 的计算，同时保持 Zipper a 作为内部状态并允许通过 returning Nothing.

失败

继续，您的 turnLeft、turnRight 和 goAhead 是纯效果：它们修改状态（monad 的 State 部分）、信号错误如果进行了不可能的移动（monad 的 Maybe 部分），但他们不需要 return 任何东西。没关系，因为他们可以 return ()。 goAhead 的工作原理如下：

goAhead :: Movement a ()
-- same as:  goAhead :: Zipper a -> Maybe ((), Zipper a)
goAhead (t, Passage v a) = Just ((), (StraightAhead v:t, a))
goAhead _                = Nothing

并且您可以对 turnLeft 和 turnRight 进行类似的更改。

现在，重新定义 return 相对容易。它应该将 b 类型的任意值打包到你的 Movement a monad 中，而不需要任何 "effects"。看看你能不能填空：

return :: b -> Movement a b
-- same as:  return :: b -> Zipper a -> Maybe (b, Zipper a)
-- in definitino below, right hand side should be:
--     Movement a b = Zipper a -> Maybe (b, Zipper a)
return b = \z -> _

当然，(>>=)稍微难一点。看看你能不能想出来：

(>>=) :: Movement a b -> (b -> Movement a c) -> Movement a c
-- in definition below, right-hand side is a:
--   Movement a c = Zipper a -> Maybe (b, Zipper a)
mb >>= bToMc = \z1 -> case mb z1 of ...

如果您放弃，我已经在下面提供了答案。

有了这个 monad，事情会变得更有趣。例如，您可以引入一个做 return 某事的动作。有效动作集怎么样？

data Move = LeftOk | RightOk | StraightOk

validMoves :: Movement a [Move]
validMoves z@(t, n) = case n of
  (Fork _ _ _)  -> Just ([LeftOk, RightOk], z)
  (Passage _ _) -> Just ([StraightOk], z)
  (DeadEnd _)   -> Just ([], z)

或者当前位置的元素：

peek :: Movement a a
peek z@(_, n) = case n of
  Fork a _ _  -> Just (a, z)
  Passage a _ -> Just (a, z)
  DeadEnd a   -> Just (a, z)

使用它，您可以构建一个走拉链的单子动作，始终使用第一个有效移动，并且 returns 是死胡同处的值：

findDeadEnd :: Movement a a
findDeadEnd =
    validMoves >>= \moves ->
    case moves of [] -> peek
                  (mv:_) -> (case mv of StraightOk -> goAhead
                                        LeftOk     -> turnLeft
                                        RightOk    -> turnRight)
                            >>= \() -> findDeadEnd

如果这是一个真正的 monad 实例，您可以用 do 表示法更清楚地编写上面的内容。

还不错吧？

无论如何，包含 return 和 >>= 答案的完整代码如下。接下来，您可能想尝试将 Movement 包装成一个新类型，以便您可以定义实例：

newtype Movement a b 
  = Movement { runMovement :: Zipper a -> Maybe (b, Zipper a) }
instance Functor (Movement a) where
instance Applicative (Movement a) where
instance Monad (Movement a) where

看看你是否可以重写所有内容以使其成为真实的 Monad。

完整示例：

module MonadZipper where

import Prelude hiding (return, (>>=))

data Node a = Fork a (Node a) (Node a)
            | Passage a (Node a)
            | DeadEnd a
              deriving (Show)

data Branch a = TurnLeft a (Node a)
              | TurnRight a (Node a)
              | StraightAhead a
                deriving (Show)

type Trace a = [Branch a]
type Zipper a = (Trace a, Node a)

type Movement a b = Zipper a -> Maybe (b, Zipper a)

(>>=) :: Movement a b -> (b -> Movement a c) -> Movement a c
mb >>= bToMc = \z1 -> case mb z1 of
                        Nothing -> Nothing
                        Just (b, z2) -> bToMc b z2

return :: b -> Movement a b
return b z = Just (b, z)

turnLeft :: Movement a ()
turnLeft (t, (Fork v l r)) = Just ((), (TurnLeft v r:t, l))
turnLeft _                 = Nothing

turnRight :: Movement a ()
turnRight (t, (Fork v l r)) = Just ((), (TurnRight v l:t, r))
turnRight _                 = Nothing

goAhead :: Movement a ()
goAhead (t, Passage v a) = Just ((), (StraightAhead v:t, a))
goAhead _                = Nothing

data Move = LeftOk | RightOk | StraightOk

validMoves :: Movement a [Move]
validMoves z@(t, n) = case n of
  (Fork _ _ _)  -> Just ([LeftOk, RightOk], z)
  (Passage _ _) -> Just ([StraightOk], z)
  (DeadEnd _)   -> Just ([], z)

peek :: Movement a a
peek z@(_, n) = case n of
  Fork a _ _  -> Just (a, z)
  Passage a _ -> Just (a, z)
  DeadEnd a   -> Just (a, z)

findDeadEnd :: Movement a a
findDeadEnd =
    validMoves >>= \moves ->
    case moves of [] -> peek
                  (mv:_) -> (case mv of StraightOk -> goAhead
                                        LeftOk     -> turnLeft
                                        RightOk    -> turnRight)
                            >>= \() -> findDeadEnd

test = case findDeadEnd ([], (Fork 1 (Fork 2 (Passage 3 (DeadEnd 4))
                                             (DeadEnd 5))
                                     (Passage 6 (DeadEnd 7)))) of
         Just (v, _) -> print v

我写的是一个真正的 monad 吗？

Is what I wrote an actual monad?

monads

haskell

functional-programming