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

有两种可能性,取决于您是否需要尾递归解决方案(并且不关心反转元素的顺序),或者是懒惰地使用其参数的解决方案.

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

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

但是在某些情况下,你既不关心元素的排序也不关心懒惰,而是关心速度.(例如,在实现排序算法时.)然后使用累加器来构建结果的变体(请参阅累积参数:去除"几乎"在"几乎尾递归"中)以实现尾递归更合适:

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