Как реализовать функцию ленивого трехсекционного константного пространства?

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

Это не космическая утечка.Чтобы выяснить, является ли список компонентов пустым, необходимо просмотреть весь входной список и составить списки других компонентов (как thunks), если он есть.В случае doo, xs1 пусто, поэтому перед тем, как решить, что выводить, нужно построить все.

Это фундаментальное свойство всех алгоритмов разделения, если один из результатов пусти вы проверяете его пустоту как условие, что проверка не может быть завершена, пока не будет пройден весь список.