如何实现惰性常数空间三分区函数？

Question

我已经概括了现有的Data.List.partition实现

partition :: (a -> Bool) -> [a] -> ([a],[a])
partition p xs = foldr (select p) ([],[]) xs
  where
    -- select :: (a -> Bool) -> a -> ([a], [a]) -> ([a], [a])
    select p x ~(ts,fs) | p x       = (x:ts,fs)
                        | otherwise = (ts, x:fs)

到“三分区”函数。

ordPartition :: (a -> Ordering) -> [a] -> ([a],[a],[a])
ordPartition cmp xs = foldr select ([],[],[]) xs
  where
    -- select :: a -> ([a], [a], [a]) -> ([a], [a], [a])
    select x ~(lts,eqs,gts) = case cmp x of
        LT -> (x:lts,eqs,gts)
        EQ -> (lts,x:eqs,gts)
        GT -> (lts,eqs,x:gts)

但是现在我在使用ghc -O1编译时遇到了一种令人困惑的行为，“foo”和“bar”函数在常量空间中工作，但是doo函数会导致空间泄漏。

foo xs = xs1
  where
    (xs1,_,_) = ordPartition (flip compare 0) xs

bar xs = xs2
  where
    (_,xs2,_) = ordPartition (flip compare 0) xs

-- pass-thru "least" non-empty partition
doo xs | null xs1  = if null xs2 then xs3 else xs2
       | otherwise = xs1
  where
    (xs1,xs2,xs3) = ordPartition (flip compare 0) xs


main :: IO ()
main = do
    print $ foo [0..100000000::Integer] -- results in []
    print $ bar [0..100000000::Integer] -- results in [0]
    print $ doo [0..100000000::Integer] -- results in [0] with space-leak

所以我现在的问题是，

1. ，doo的空间泄漏是什么原因，我觉得很奇怪，因为foo和bar没有显示出这样的空间泄漏？
2. 是否有一种实现ordPartition的方法，当它在诸如doo这样的函数中使用时，它以恒定的空间复杂度执行？

Answer 1

这不是空间泄漏。要确定组件列表是否为空，必须遍历整个输入列表，如果是，则必须构造其他组件列表(作为块)。在doo的情况下，xs1是空的，所以在决定输出什么之前，必须构建整个程序。

这是所有分区算法的一个基本属性，如果结果之一为空，并且检查其空值作为条件，则在遍历整个列表之前不能完成该检查。