如何在Haskell中获得列表的中间位置？

Question

我刚刚开始学习使用Haskel的函数式编程.

我正慢慢地通过Erik Meijer在第9频道的讲座(到目前为止我已经观看了前4个),在第4个视频中,Erik解释了尾部是如何工作的,它让我很着迷.

我试着编写一个返回列表中间的函数(偶数长度为2项,奇数为1项)我想听听其他人如何实现它

• 最少量的Haskell代码
• 最快的Haskell代码

如果你能解释一下你的选择,我将非常感激.

我的初学者代码如下所示:

middle as | length as > 2   = middle (drop 2 (reverse as))
          | otherwise       = as

Answer 1

我没有做任何性能声明,虽然它只处理列表的元素一次(我的假设是计算length t是O(N)操作,所以我避免它),但这是我的解决方案:

mid [] = []                      -- Base case: the list is empty ==> no midpt
mid t = m t t                    -- The 1st t is the slow ptr, the 2nd is fast
  where m (x:_) [_] = [x]        -- Base case: list tracked by the fast ptr has
                                    -- exactly one item left ==> the first item
                                    -- pointed to by the slow ptr is the midpt.
        m (x:y:_) [_,_] = [x,y]  -- Base case: list tracked by the fast ptr has
                                    -- exactly two items left ==> the first two
                                    -- items pointed to by the slow ptr are the 
                                    -- midpts
        m (_:t) (_:_:u) = m t u  -- Recursive step: advance slow ptr by 1, and
                                    -- advance fast ptr by 2.

这个想法是在列表中有两个"指针",一个在递归中的每个点递增一步,另一个递增2.

(这基本上是Carl Smotricz所建议的)

Answer 2

只是为了您的娱乐,来自不会说Haskell的人的解决方案:

编写一个递归函数,它接受两个参数a1和a2,并将列表作为两个参数传递.在每次递归时,从a2中删除2,从a1中删除1.如果你没有a2的元素,那么你将处于a1的中间.您可以处理a2中仅剩1个元素的情况,以回答您的"中间"是否需要1或2个元素.

Answer 3

两个版本

1. 使用模式匹配,tail和init:

   middle :: [a] -> [a]
   middle l@(_:_:_:_) = middle $ tail $ init l
   middle l           = l
   

2. 使用length,take,signum,mod,drop和div:

   middle :: [a] -> [a]
   middle xs = take (signum ((l + 1) `mod` 2) + 1) $ drop ((l - 1) `div ` 2) xs
     where l = length xs
   

第二个基本上是一个单行(但where用于可读性).

Answer 4

我试着编写一个返回列表中间的函数(偶数长度为2项,奇数为1项)我想听听其他人如何实现它

正确问题的正确数据结构.在这种情况下,你已经指定了只在有限列表上有意义的东西,对吧？无限列表没有"中间".因此,只需阅读说明,我们就知道默认的Haskell列表可能不是最佳解决方案:即使我们不需要它,我们也可能为懒惰付出代价.请注意有多少解决方案难以避免2*O(n)或O(n).单链接的惰性列表与准数组问题不太匹配.

幸运的是,我们在Haskell中有一个有限的列表:它叫做Data.Sequence.

让我们以最明显的方式解决它:'index(length/2)'.

Data.Seq.length是O(1)根据文档.Data.Seq.index是O(log(min(i,n-i)))(我认为i = index,n = length).我们打电话吧O(log n).非常好!

请注意,即使我们不是从a开始Seq并且必须将a转换[a]为a Seq,我们仍然可能获胜.Data.Seq.fromList是O(n).因此,如果我们的竞争对手是一个O(n)+O(n)类似xs !! (length xs)的解决方案,那么

middle x = let x' = Seq.fromList x in Seq.index(Seq.length x' `div` 2)

将会更好,因为它会O(1) + O(log n) + O(n)简化O(log n) + O(n),明显优于O(n)+O(n).

(我作为练习留给读者修改中间,如果长度是偶数则返回2个项目,如果长度是奇数,则返回1个.毫无疑问,对于具有恒定时间长度和索引操作的数组,可以做得更好,但是数组不是'我觉得这是一个清单.)

Answer 5

Haskell解决方案受到Carl的回答启发.

middle = m =<< drop 1
   where m []  = take 1
         m [_] = take 2
         m (_:_:ys) = m ys . drop 1