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

Question

您好,我目前正在攻读考试,并且在回答主题时遇到问题,作为标题状态,目标是concat使用理解列表创建非递归函数,查看解决方案:

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

然而我无法理解为什么会有效,任何帮助都会受到赞赏.

Answer 1

列表理解箭头(<-)可以读作"in",如[x | xs <- xss, x <- xs]"xs in xss in xs in xs in xs",表示我们将列表列表中的每个列表解包为其组成元素 - 这有点像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)

最后只是(来自Functor法则!或常识)

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只有"正确的身份"monad法则,帮助我们看到

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

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

因此,有很多方法可以concat通过列表理解来实现,具体取决于您想要如何理解列表推导.最重要的是,这些都是等价的,可以相互建立,形成列表及其monad实例的真正含义的基础.

Answer 2

您可以将列表理解描绘为嵌套循环.所以,

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

表示"每个xin list1,for each yin list2,yield z",结果列表是按顺序排列的所有产生的值.请注意,z此处的值将在符号中排在第一位.所以如果我们有:

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

这说,"对于每个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,for each xin list,yield x".也就是说,从第一个列表中获取所有元素,然后从第二个列表中获取所有元素,依此类推,这对应于连接所有列表.

我使用的命名不太可能在野外看到.s对于用于表示列表的变量,通常使用"复数"名称,以"1"结尾.发音xs为"exes".或许语言学上的比喻可能太过分了(但它仍然是常见的惯例),我们将列表列表"双重复数" xss.我通常不会发音,因为"发出"的声音太傻了.因此,您可以通过名称查看xss列表列表,并且xs是一个列表,您将帮助阅读这些密集表达式.