haskell - 很难定义所有值的单子(monad)

Question

我试图编写将所有数据节点乘以给定数字的 monad。我不知道如何正确定义 Monad。

module Main where  
data LinkedList a = NodeWithoutNext a | Node a (LinkedList a) deriving (Show)

instance Functor LinkedList where
  fmap f (NodeWithoutNext x) = NodeWithoutNext (f x)
  fmap f (Node a next) = Node (f a) (fmap f next)

instance Applicative LinkedList where
   pure = NodeWithoutNext
   (NodeWithoutNext f) <*> (NodeWithoutNext x) = NodeWithoutNext (f x)
   (NodeWithoutNext f) <*> (Node a next) = Node (f a) (fmap f next)

instance Monad LinkedList where
   return = NodeWithoutNext
   (NodeWithoutNext a) >>= f = f a
   **(Node a next) >>= f =  Node (f a) (next >>= f)**

main :: IO ()
main  =  do  
    let list = Node 3 (Node 2 (NodeWithoutNext 7))
    print (list)
    print (list >>= (\x -> NodeWithoutNext (x+200)))

我收到错误 -

Bla.hs:16:39: error:
    * Couldn't match type `b' with `LinkedList b'
      `b' is a rigid type variable bound by
        the type signature for:
          (>>=) :: forall a b.
                   LinkedList a -> (a -> LinkedList b) -> Linked
        at Bla.hs:15:24-26
      Expected type: LinkedList (LinkedList b)
        Actual type: LinkedList b
    * In the second argument of `Node', namely `(next >>= f)'
      In the expression: Node (f a) (next >>= f)
      In an equation for `>>=':
          (Node a next) >>= f = Node (f a) (next >>= f)
    * Relevant bindings include
        f :: a -> LinkedList b (bound at Bla.hs:16:22)
        (>>=) :: LinkedList a -> (a -> LinkedList b) -> LinkedLi
          (bound at Bla.hs:15:24)
   |
16 |    (Node a next) >>= f =  Node (f a) (next >>= f)
   |                                       ^^^^^^^^^^

这里我需要修复什么？问题出在带有**的那一行。

Answer 1

类型系统会提示，因为“bind”运算符 >>=有签名:

<b>(>>=) :: Monad m => m a -> (a -> m b) -> m b</b>

因此，让我们专门研究 LinkedList 的签名:

(>>=) :: <b>LinkedList a</b> -> (a -> <b>LinkedList b</b>) -> <b>LinkedList b</b>

所以该函数在左侧取 LinkedList a ，右侧是映射 a 的函数(!) 到 LinkedList b ，我们预计结果是 LinkedList b 。您定义的函数不能这样做:因为如果您构造一个 Node (f a) (next >>= f) ，结果将是 LinkedList (LinkedList b) 。确实，您申请f至a (列表的头部)，产生 LinkedList b (作为 Node 的负责人)。

如果我们看一下上面的签名，可能会出现一些想法，但最直接的想法可能是实现某种 concatMap :: [a] -> (a -> [b]) -> [b] 。 “绑定(bind)”必须满足以下规则:

1. return a >>= k = k a ;
2. m >>= return = m ;和
3. m >>= (\x -> k x >>= h) = (m >>= k) >>= h .

concatMap函数满足三个约束。 (1) 如果我们包装一个值 x进入LinkedList ，然后申请f在(单例列表的)每个元素上，我们将获得一个包含一个列表的列表，即 k a 的结果。 ，但是通过使用concat的concatMap ，我们再次将其展平。 (2) 如果我们使用m >>= return使用 concat，我们会将每个元素包装在一个新的单例列表中，但是串联将再次将其解开。

所以我们可以将其实现为:

instance Monad LinkedList where
   return = NodeWithoutNext
   (NodeWithoutNext a) >>= f = f a
   (Node a next) >>= f =  build (f a)
       where build (NodeWithoutNext x) = (Node x (next >>= f))
             build (Node x xs) = Node x (build xs)

所以这里build将迭代LinkedList由 f a 制作，并且基本上构造一个几乎重复，除了当我们到达末尾时，我们将继续连接剩余元素的绑定(bind)结果。