如何在列表中实现Applicative,建模非确定性？

Question

当我遇到这个任务时,我在Haskell练习Functor/Applicative Functors + Monads :

4)您已经了解了Monad实例如何用于处理可能失败的事物.Monad的另一个用例是处理非决定论.对非确定性计算进行建模的最简单方法是使用列表.将列表视为包含某些计算的所有可能结果.当您使用众所周知的地图功能时,您正在应用的功能会生成所有可能输入的输出.[...]

像这样定义列表类型:

data MyList a = Cons a (MyList a) | Nil deriving Show

(a)使您的列表成为Functor的实例.
(b)使您的列表成为Applicative的实例.
(c)使你的清单成为Monad的一个实例.

我遇到了一些麻烦.这是我目前的解决方案:

instance Functor MyList where
    fmap f (Nil) = Nil
    fmap f (Cons item other) = (Cons (f item) (fmap f other))

instance Applicative MyList where
    pure item = (Cons item Nil)
    Nil <*> _ = Nil
    _ <*> Nil = Nil
    (Cons f item) <*> something = (fmap f something) ++ (item <*> something)

问题在于(item <*> something).使用列表,++操作员可以实现这一点,但我甚至创建了一个具有++运算符的函数,但这种方法仍然不起作用.如何实施此类型的Applicative？

这是我的++实现:

(++) :: (MyList a) -> a -> (MyList a)
(++) Nil item = (Cons item Nil)
(++) (Cons val other) item = (Cons val (other ++ item))

这是我得到的错误:

Couldn't match expected type ‘a -> b’
            with actual type ‘MyList (a -> b)’
Relevant bindings include
  something :: MyList a (bound at Assignment_6.hs:13:23)
  item :: MyList (a -> b) (bound at Assignment_6.hs:13:13)
  f :: a -> b (bound at Assignment_6.hs:13:11)
  (<*>) :: MyList (a -> b) -> MyList a -> MyList b
    (bound at Assignment_6.hs:11:5)
In the second argument of ‘(++)’, namely ‘item’
In the first argument of ‘(<*>)’, namely
  ‘(fmap f something) ++ item’

Answer 1

比较以下两种类型:

(Prelude.++) :: []     a -> [] a -> []     a
(George.++)  :: MyList a ->    a -> MyList a

你能发现问题吗？