`[ (x !! 0, x !! 1) | x <- mapM (const ['A', 'B', 'C'] ) [1..2], head x < head (tail x) ]` 工作吗？

Question

我是 Haskell 的新手，想知道语句如何

[ (x !! 0, x !! 1) | x <- mapM (const ['A', 'B', 'C'] ) [1..2], head x < head (tail x) ]

作品。（我在 StackOverflow 上找到了它。）我知道它输出什么，但我并没有真正理解它。

Answer 1

好吧，上面的表达式可能不是惯用的Haskell表达式。可能更好的版本是：

[ (x0, x1) | (x0:x1:_) <- mapM (const "ABC") [1..2], x0 < x1 ]

这更清晰，如果 中的列表mapM (const "ABC")将返回包含少于两个元素的列表（这里不可能），它不会出错。

可能这里的核心问题是了解mapM工作原理。该表达式mapM (const "ABC") [1..2]归结为：

mapM (\_ -> "ABC") [1..2]

由于我们不考虑列表的值，它等价于：

replicateM 2 "ABC"

这replicateM对于2可改写为（伪Haskell语法）：

replicateM 2 :: [a] -< [[a]]
replicateM 2 l = do
    x0 <- l
    x1 <- l
    return [x0, x1]

或者如果我们对此进行脱糖：

replicateM 2 l = l >>= \x0 -> l >>= \x1 -> return [x0, x1]

对于列表， 的实例Monad实现为：

instance Monad [] where
    return x = [x]
    (>>=) = flip concatMap

所以这意味着对于列表 this replicateM 2，实现为：

replicateM 2 l :: [a] -> [[a]]
replicateM 2 l = concatMap (\x0 -> concatMap (\x1 -> [[x0, x1]]) l) l

或更简单：

replicateM 2 l :: [a] -> [[a]]
replicateM 2 l = concatMap (\x0 -> map (\x1 -> [x0, x1]) l) l

因此，我们对列表中的两个项目进行了所有可能的组合。因此，这意味着：

Prelude Control.Monad> replicateM 2 "ABC"
["AA","AB","AC","BA","BB","BC","CA","CB","CC"]

然后我们在列表推导中使用它，并且对于这些具有两个元素的子列表中的每一个，我们检查第一个元素x0是否小于列表推导中具有过滤器部分的第二个元素( x0 < x1)。如果是这种情况，我们将这些元素生成为 2 元组。

因此"ABC"，如果第一个元素（严格地）小于第二个元素，则它为 中的每两个项目创建 2 元组。

然而，这里我们做了一些“太多工作”：超过一半的元素将被拒绝。我们可以通过使用来优化它tails :: [a] -> [[a]]：

import Data.List(tails)

[(x0, x1) | (x0:xs) <- tails "ABC", x1 <- xs ]

产生相同的值：

Prelude Control.Monad Data.List> [(x0, x1) | (x0:xs) <- tails "ABC", x1 <- xs ]
[('A','B'),('A','C'),('B','C')]