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

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

这不是空间泄漏。要查明组件列表是否为空，必须遍历整个输入列表，如果是，则构造其他组件列表（作为 thunk）。在 doo 情况下，xs1 是空的，因此在决定输出什么之前必须构建整个内容。

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