haskell - `[ (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 所认为的惯用。可能更好的版本是:

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

这更干净，如果 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

所以这意味着对于一个列表这个 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" 中的每两个项目创建二元组，如果第一个元素(严格)小于第二个元素。

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

import Data.List(tails)

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

产生相同的值:

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