Haskell通过枢轴值将列表分为两部分 [英] Haskell split a list into two by a pivot value

问题描述

我想通过枢轴值将[a]分成([a]，[a])，并且我有我的代码

I want to split [a] into ([a], [a]) by a pivot value and I have my code

splitList :: (Ord a) => a -> [a] -> ([a],[a])
splitList pivot list = 
    ([x | x <- list, x <= pivot], [x | x <- list, x > pivot])

但是将列表重复两次以生成两个列表，有没有办法只重复一次?

But it iterates the list twice to generate two lists, is there a way to iterate only once?

推荐答案

有两种可能，具体取决于您是否需要懒惰.

There are two possibilities, depending on if you want a tail recursive solution (and don't care about reversing the order of elements), or a solution that consumes its argument lazily.

惰性解决方案决定列表的第一个元素进入第一部分还是进入第二部分，并使用简单的递归来处理列表的其余部分.在大多数情况下，这是首选的解决方案，因为懒惰通常比尾递归更重要:

The lazy solution decides if the first element of the list goes into the first or into the second part and uses a simple recursion to process the rest of the list. This would be the preferred solution in most cases as laziness is usually more important than tail recursion:

splitList :: (Ord a) => a -> [a] -> ([a],[a])
splitList _ [] = ([], [])
splitList p (x : xs)
    | x <= p    = (x : l, r)
    | otherwise = (l, x : r)
  where
    ~(l, r) = splitList p xs

但是，在某些情况下，您既不在乎元素的顺序也不在乎懒惰，而在乎速度. (例如，当实施排序算法时.)然后，使用累加器构建结果的变体(请参见累积参数:摆脱几乎尾巴递归"中的几乎"来实现尾巴递归更合适:

However in some cases you care neither for the ordering of elements nor for laziness, but instead for speed. (For example when implementing a sorting algorithm.) Then a variant that uses an accumulator to build the result (see Accumulating Parameters: Getting rid of the 'almost' in "almost tail recursive" ) to achieve tail recursion would be more appropriate:

splitListR :: (Ord a) => a -> [a] -> ([a],[a])
splitListR pivot = sl ([], [])
  where
    sl acc    []        = acc
    sl (l, g) (x : xs)
        | x <= pivot    = sl (x : l, g) xs
        | otherwise     = sl (l, x : g) xs

这篇关于Haskell通过枢轴值将列表分为两部分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！