haskell中理解非递归列表理解concat的问题

Question

您好，我目前正在学习考试，并且在回答题目时遇到了问题，作为标题状态，目标是使用理解列表创建一个非递归的concat函数，并查看解决方案：

concat3 :: [[a]] -> [a]
concat3 xss = [x | xs <- xss, x <-xs]

然而，我不能理解为什么这是可行的，任何帮助都将不胜感激。

Answer 1

列表理解箭头(<-)可以读作" in "，就像[x | xs <- xss, x <- xs]读取“xss中的x和xs中的x”一样，这表明我们正在将列表中的每个列表解包为其组成元素-这有点像concat。

然而，有很多种方法来看待这一点。

机械地将列表理解转换为do表示法

do xs <- xss
   x  <- xs
   return x

do表示法转换为(>>=)和(>>)

xss >>= \xs -> xs >>= \x -> return x

然后，当我们在列表上实例化它们时，(>>=)本身变成了concatMap，return变成了(\x -> [x])。

concatMap (\xs -> concatMap (\x -> [x]) xs) xxs

如果你考虑一下concatMap (\x -> [x])，你可能会把它看作是传递一个列表，把每个元素放到一个单独的列表中，然后把它们连接起来……这只是一种什么都不做的复杂方式。

concatMap id xss

从concatMap的定义来看，我们有

concat (map id xss)

最后(来自函数式法则！或常识)

concat xss

因此，该函数像concat一样工作也就不足为奇了。

当我们在“列表单体”中倾向于从语义上思考时，如何解释do表示法呢？

do xs <- xss
   x  <- xs
   return x

本质上，这可以理解为“从我们的列表列表中非确定性地选择一个构成列表，然后从该列表中非确定性地选择一个元素--从这个过程中收集所有的可能性”，这再次导致了我们只是连接在一起的想法。

我们还可以从Control.Monad函数join中获取幸运的对应关系

join              :: (Monad m) => m (m a) -> m a  -- this looks `concat`-like!
join x            =  x >>= id

如果我们考虑内部的xs >>= \x -> return x，然后使用eta-conversion，我们就有了xs >>= return，它就是"right identity" monad law，帮助我们看到

xss >>= \xs -> xs >>= \x -> return x
===
xss >>= \xs -> xs >>= return
===
xss >>= \xs -> xs
===
xss >>= id
===
join xss

然后我们可以查看如何在list monad中实例化join并查看join = concat。

因此，有许多方法可以将concat看作是通过列表理解实现的，这取决于您对列表理解的看法。最棒的部分是，它们都是等价的，并且可以相互构建，以形成列表及其monad实例真正含义的基础。

Answer 2

您可以将列表理解想象为嵌套循环。所以,

[ z | x <- list1, y <- list2 ]

表示“对于list1中的每个x，对于list2中的每个y，输出z"，结果列表是所有产出值的集合。注意，要产生的值，这里是z，在符号中排在第一位。因此，如果我们有：

[ (x,y) | x <- [1,2], y <- [3,4,5] ]

这就是说，“对于[1,2]中的每个x，对于[3,4,5]中的每个y，产生(x,y)"，因此我们得到：

[ (1,3), (1,4), (1,5),   -- when x = 1
  (2,3), (2,4), (2,5) ]  -- when x = 2

配备了用于列表理解的助记符，我们可以读取您的concat3定义。

concat3 xss = [ x | xs <- xss, x <- xs ]

我将重命名变量以使其更易于阅读：

concat3 listOfLists = [ x | list <- listOfLists, x <- list ]

我们现在可以将其理解为“对于listOfLists中的每个list，对于list中的每个x，产生x”。也就是说，首先生成第一个列表中的所有元素，然后生成第二个列表中的所有元素，依此类推，这相当于连接所有列表。

我使用的命名不太可能在野外看到。对于表示列表的变量，通常使用以s结尾的“复数”名称。将xs读作"exes“。采用语言类比可能太过了(但这仍然是常见的惯例)，我们对列表xss进行“双复数”处理。我通常不会发音，因为"exeses“听起来太傻了。从名称可以看出，xss是一个列表列表，而xs是一个列表，这将帮助您读取像这样的密集表达式。