Haskell中的列表交错列表 [英] Interleave List of Lists in Haskell

问题描述

我想知道如何在Haskell中编写一个将列表列表交织到单个列表中的函数，例如，如果我有一个名为
$ b interleavelists :: [[a]] - > [a]

它应该能够交织元素。例如： [[1,2,3] [4,5,6] [7,8]] - > [1,4,7,2,5,8,3,6] 。

这些清单既可以是有限的，也可以是无限的。 。能否使用 foldr ？

解决方案

是使用 转置 from Data.List 。

  import Data.List 
 
 interleavelists :: [[a]]  - > [a] 
 interleavelists = concat。转置
  

转置选择每个元素的第一个元素非空的参数列表，将它们放入一个列表中，之后，转置 s列表 tail s的论点的元素。 concat 输入转置列表的结果会根据需要交错列表。它适用于一些元素列表是无限的，但如果列表列表本身拥有无限多的元素，它当然永远不会超过头部 s的列表。但是，处理这种情况无论如何都是有问题的。



使用 foldr 交错列表并不是微不足道的。假设你有



  interleavelists xss = foldr something zero xss 
  

interleavelists [] 应该可能产生 [] ，这样'd是零值。和

  interleavelists [xs] = xs 
  

似乎很自然，所以



  something xs [] = xs 
  code> 

但如果第二个参数不是 [] ？然后，您想将不同距离的 something 的第一个参数的元素插入到第二个参数中。但在哪些距离？如果所有列表具有相同的长度，则每个列表的距离是恒定的，那么您可以将该距离作为另一个参数传递，



  interleavelists = snd。 foldr insertAtDistance（0，[]）
其中
 insertAtDistance xs（d，ys）=（d + 1，helper d xs ys）
 helper _ [] ws = ws 
助手k（b：bs）cs = b：us ++助手k bs vs 
其中
（us，vs）= splitAt k cs 
  

这不是很漂亮，如果列表不是所有相同的长度都会产生可能不是所需输出的东西。但是，如果列表的长度都相同，它就可以完成这项工作。

I was wondering how could I write a function in Haskell that interleaves a list of lists into a single lists, for example, if I had a function called

interleavelists :: [[a]] -> [a]

it should be able to interleave the elements.

Example: [[1,2,3] [4,5,6] [7,8]] --> [1,4,7,2,5,8,3,6].

The lists can be both finite or infinite... Can I use foldr?

解决方案

The quickest way to write it is to use transpose from Data.List.

import Data.List

interleavelists :: [[a]] -> [a]
interleavelists = concat . transpose

transpose picks the first element of each non-empty list of its argument, putting them into one list, and after that, transposes the list of tails of the argument's elements. concatenating the lists of transpose's result interleaves the lists as desired. It works if some element lists are infinite, but if the list of lists itself has infinitely many elements, it of course never gets past the list of heads. But handling that case is problematic anyway.

Using foldr to interleave the lists is not trivial. Suppose you had

interleavelists xss = foldr something zero xss

interleavelists [] should probably produce [], so that'd be the zero value. And

interleavelists [xs] = xs

seems natural, so

something xs [] = xs

But what if the second argument isn't []? Then you want to insert the elements of the first argument of something at varying distances into the second argument. But at which distances? If all lists have the same length, the distances for each list are constant, then you could pass the distance as a further parameter,

interleavelists = snd . foldr insertAtDistance (0, [])
  where
    insertAtDistance xs (d, ys) = (d+1, helper d xs ys)
    helper _ [] ws = ws
    helper k (b:bs) cs = b : us ++ helper k bs vs
      where
        (us,vs) = splitAt k cs

That isn't very pretty, and if the lists are not all the same length will produce what probably isn't the desired output. But if the lists all have the same length, it does the job.

这篇关于Haskell中的列表交错列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！