时间戳

首页 > 解决方案 > `[ (x !! 0, x !! 1) | x <- mapM (const ['A', 'B', 'C'] ) [1..2], head x < head (tail x) ]` 有效吗？

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

问题描述

我是 Haskell 的新手，想知道声明如何

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

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

标签： haskelllist-comprehension

解决方案

好吧，上面的表达式可能不是惯用的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"

这replicateMfor2可以重写为（伪 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')]

推荐阅读