Haskell 通过主值将列表分成两部分

Question

我想通过主值将 [a] 拆分为 ([a], [a])，并且我有我的代码

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

但是它迭代列表两次生成两个列表，有没有办法只迭代一次？

Answer 1

有两种可能性，具体取决于您是否想要 tail recursive解决方案(并且不关心反转元素的顺序)，或消耗其参数 lazily 的解决方案.

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

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

但是，在某些情况下，您既不关心元素的顺序，也不关心惰性，而是关心速度。 (例如，在实现排序算法时。)那么使用累加器构建结果(参见 Accumulating Parameters: Getting rid of the 'almost' in "almost tail recursive" )以实现尾递归的变体会更合适:

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