3

您好，我目前正在为考试而学习，并且在回答主题方面遇到问题，如标题所示，目标是concat使用理解列表创建一个非递归函数，查看它的解决方案：

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

但是我不明白为什么会这样，任何帮助都将不胜感激。

4

2 回答 2

10

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

不过，有很多方法可以查看这一点。

机械地，列表推导转换为do符号

do xs <- xss
   x  <- xs
   return x

和do符号转换为(>>=)和(>>)

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

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

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

如果您考虑一下，concatMap (\x -> [x])您可能会将其视为传递一个列表，将每个元素放入一个单例列表，然后将它们连接起来……这只是一种不做任何事情的复杂方式。

concatMap id xss

并且根据concatMap我们的定义

concat (map id xss)

最后只是（来自函子定律！或常识）

concat xss

因此，该功能的工作方式与此相同也就不足为奇了concat。

do当我们在“list monad”中时，我们倾向于从语义上思考如何解释符号？

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 转换xs >>= return，这就是“正确的身份”单子定律，帮助我们看到

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

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

因此，有很多方法可以concat通过列表推导实现，具体取决于您如何看待列表推导。最重要的是，这些都是等价的，并且可以相互构建以形成列表及其 monad 实例真正含义的基础。

于 2013-07-08T06:15:00.403 回答
7

您可以将列表推导式描述为嵌套循环。所以，

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

意思是“for each xin list1, for each yin list2, yield z”，结果列表是所有 yield 值的集合。请注意，这里要产生的值z首先出现在符号中。所以如果我们有：

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

这就是说，“for each xin [1,2], for each yin [3,4,5], yield (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 ]

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

我使用的命名不太可能在野外看到。s对于表示列表的变量，通常使用以 结尾的“复数”名称。发音xs为“exes”。将语言类比看得太远（但它仍然是常见的约定），我们将列表“双重复数”，xss. 我通常不这么发音，因为“exeses”听起来太傻了。因此，您可以通过名称看到xss列表列表，并且xs是列表，它将帮助您阅读这些密集的表达式。

于 2013-07-08T06:50:50.933 回答