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

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是空的,所以在决定输出什么之前必须构建整个事物.

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