haskell - 如何使用 concatMap 将列表理解转换为版本？

Question

这个问题已经有答案了:

Replace a 3 parameter list-comprehension by using map, concat (3 个回答)

已关闭 3 年前。

如何将列表理解转换为使用 concatMap 的版本相反？

dPairs xs ys = [(x, y) | x <- xs, y <- ys, x /= y]

Answer 1

列表理解可以重写为 do 语法，例如:

import Control.Monad(guard)

dPairs xs ys = do
    x <- xs
    y <- ys
    guard (x /= y)
    return (x,y)

这个do表达式只是语法糖。事实上，do expression section in the Haskell report展示如何脱糖:

dPairs xs ys = xs >>= (\x -> ys >>= (\y -> guard (x /= y) >> return (x,y)))

对于实例 Monad []，return 和绑定(bind)函数 >>= 定义为:

instance Monad [] where
    return x = [x]
    xs >>= f = concatMap f xs

因此，这意味着我们的 dPairs 定义为:

dPairs xs ys = concatMap (\x -> concatMap (\y -> guard (x /= y) >> [(x,y)]) ys) xs

guard :: Alternative f => Bool -> f ()定义为:

guard True = return ()
guard False = empty

因此对于列表，它定义为:

-- guard for list
guard True = [()]
guard False = []

严格的翻译是:

dPairs xs ys = concatMap (\x -> concatMap (\y -> (concatMap (\_ -> [(x,y)]) (if x /= y then [()] else [])) ys) xs

然而，这是一个相当复杂的表达式。例如，一个 concatMap ，其中函数每次都映射到一个单例列表，它只是一个 map ，而没有将元素包装在单例列表中。因此，我们可以将其简化为:

dPairs xs ys = concatMap (\x -> concatMap (\y -> <b>map (const (x,y)</b>) (if x /= y then [()] else [])) ys) xs

进一步的guard只是一种过滤机制，因此我们可以使用以下方式进行过滤:

dPairs xs ys = concatMap (\x -> map (<b>\y -> (x,y)</b>) (<b>filter (x /=) ys</b>)) xs

然而，一个更简单的函数是:

dPairs :: Eq a => [a] -> [a] -> [(a,a)]
dPairs xs ys = filter (<b>uncurry (/=)</b>) (<b>(,) <$> xs <*> ys</b>)

如@chepner says ，Haskell 报告还有 section how to transform "desugar" list comprehension to concatMaps .