难以在所有值上定义单子

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

类型系统会抱怨，因为“绑定”运算符

>>=

具有签名：

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

所以让我们专门为

LinkedList

签名：

(>>=) :: LinkedList a -> (a -> LinkedList b) -> LinkedList 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]

。 “绑定”必须满足以下规则：

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

，并基本上构造一个几乎重复，除了当我们到达末尾时，我们将继续连接绑定的结果剩余元素。