How to implement lazy tri-partition function of constant space?

Question

I have summarized the existing implementation of 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 px ~(ts,fs) | px = (x:ts,fs) | otherwise = (ts, x:fs) 

to the tri-partition function

 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) 

But now I come across confusing compilation behavior with ghc -O1 , the foo and bar functions work in constant space, but the doo function is leaking space.

 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 

So my question is:

• What is the cause of the space leak in doo , which seems surprising to me since foo and bar do not have such a space leak? and

• Is there a way to implement ordPartition in such a way that when used in the context of functions such as doo , it performs with the constant complexity of the space?

Answer 1

This is not a space leak. To find out if the component list is empty, the entire input list must be passed, and the remaining component lists are built (in the form of tricks), if so. In the case of doo xs1 empty, so you need to build all this before deciding what to output.

This is a fundamental property of all partitioning algorithms; if one of the results is empty and you check its emptiness as a condition, this check cannot be performed before the entire list is passed.