<*> 对于以 do 表示法实现的列表 - 这不是 "cheating" 吗？

Question

根据'Learn you a Haskell'，列表的<*>实现是：

fs <*> xs = [f x | f <- fs, x <- xs]

我是不是弄错了，或者这个加糖的 monadic 代码是基于 >>= 的？

据我了解，应该可以仅使用 fmap 来实现 <*>，就像应用程序 Maybe 的情况一样。

如何仅使用 fmap 实现列表的 <*>？（可能没有连接东西？）

顺便说一句，几页之后我看到了关于 <*> 应用程序 IO 的实施的相同问题。

Answer 1

有很多 Applicative 实例被 monadic 函数满足的情况，我见过

instance Applicative MyMonadThatIsAlreadyDefined where
    pure = return
    (<*>) = ap

还有，<*>不能只用fmap来写，至少一般情况下是这样。这就是 <*> 的意义所在。试着用 fmap 来写 <*>，如果你能做到（以一种行为良好并遵循适用法则的方式），我会感到非常惊讶。记得链条是

Functor > Applicative > Monad

其中 > 可以被认为是超集。这就是说所有函子的集合包含所有应用程序的集合，它包含所有单子的集合。如果你有一个 monad，那么你就有了将它用作应用程序和函子所需的所有工具。有些类型是函数式的但不是适用的，而类型是适用的而不是单子的。我认为以这种方式定义应用实例没有问题。

Answer 2

不，这不是基于 >>= 的单子代码。如果是，Monad [] 实例中的 definition of >>= 将是循环的。

instance Monad []  where
    {-# INLINE (>>=) #-}
    xs >>= f             = [y | x <- xs, y <- f x]
    ...

列表理解是 let、if 和 concatMap 的语法糖。来自 Haskell Report:

[  e | b,          Q ] = if  b     then [ e | Q ] else []
[  e | let decls,  Q ] = let decls in   [ e | Q ]
[  e | p <- l,     Q ] = let ok p  =    [ e | Q ]
                             ok _  =    []
                         in concatMap ok l

Monad [] 实例很容易根据 concatMap 定义，但 concatMap 是在 GHC.List (and is now possibly defined in Data.Foldable 中定义的。 GHC.List 和 Data.Foldable 都没有导入到 GHC.Base 中，因此根据 concatMap 定义 GHC.Base 中列表的 Monad 实例是不可能的：

instance Monad [] where
    (>>=) = flip concatMap -- concatMap isn't imported

根据列表理解定义这些实例需要导入包含 concatMap 的模块以重用它定义 >>=.

在 GHC 中有两个 implementations of list comprehensions. One rewrites them in terms of the GHC.Base build and foldr similar to the Data.Foldable concatMap. The other implementation generates recursive functions in place of concatMap as described by Wadler。

Answer 3

Am I mistaken, or is this sugared monadic code based on >>= ?

我不知道 >>= 是否真的用于对列表推导进行去糖化处理（但请参阅 Cirdec 的回答以获取并非如此的证据），但在中定义 <*> 实际上是完全合法的>>= 项。在数学术语中，每个 Monad 个实例诱导个唯一对应的 Applicative 个实例，在某种意义上

instance Applicative F where
    pure = return
    af <*> ax = af >>= \ f -> ax >>= \ x -> return (f x)

只要 F 有一个守法 Monad 实例，

就是一个守法 Applicative 实例。

这里有一个数学类比，如果你熟悉的话：

每 inner product induces a norm;
每个范数都会导致 metric;
每个指标都会产生 topology。

类似地，对于每个 monad 结构都有一个兼容的应用结构，并且对于每个应用结构都有一个兼容的 fmap (fmap f ax = pure f <*> ax)，但是相反的含义不成立。

As far as I understand, it should be possible to implement <*> only using fmap, as it is the case with applicative Maybe.

我不明白你的意思。 fmap 肯定不足以定义 <*>，或者每个 Functor 都会是一个 Applicative（嗯，一个 Apply）。

Answer 4

_{这个答案是对已经给出的答案的补充，并且只关注问题的一部分：}

As far as I understand, it should be possible to implement <*> for lists only using fmap, as it is the case with applicative Maybe. How?

你好像指的是this implementation:

instance Applicative Maybe where
    pure = Just
    Nothing  <*> _         = Nothing
    (Just f) <*> something = fmap f something

嗯，是的，我们也可以对列表这样做——只使用 fmap、模式匹配和构造函数：

instance Applicative [] where
    pure = []
    []     <*> _         = []
    (f:fs) <*> something = fmap f something ++ (fs <*> something)
      where
        []     ++ yy = ys
        (x:xs) ++ ys = x : (xs++ys)

诚然，这确实需要某种串联，因为列表是比 Maybe 更复杂的类型。列表还有其他可能的应用实例，它们需要的代码少于此 "everything-with-everything" 行为，但它们与默认的 monad 实例不兼容（这是常见的期望）。

当然，monad 符号确实极大地简化了这一点：

instance Monad m => Applicative m where
    pure = return
    mf <*> something = mf >>= (\f -> fmap f something) -- shorter: (`fmap` something)

…这对 Maybe 和 [] 都适用，如 m.

<*> 对于以 do 表示法实现的列表 - 这不是 "cheating" 吗？

<*> for lists implemented as do notation - isn't this "cheating"?

haskell

list

applicative