Perfect elimination ordering and high memory usage The following code calculates a perfect
elimination ordering in a special case in Haskell.

I am less worried about its correctness than
its high use of memory. The following code runs
out of memory on my computer. It seems it should be
possible to execute the algorithm without ever having
more than around 1000 integers in memory.

The function do_elimination is tail-recursive, which is
supposed to be efficient in Haskell.

{-# LANGUAGE FlexibleInstances #-}
import Data.List (partition, (\\))

class Eq a =&gt; Concurrent a where
    isConcurrent :: a -&gt; a -&gt; Bool

instance Ord a =&gt; Concurrent (a, a) where
    isConcurrent (x,y) (z,w) = ( (x &lt;= z) &amp;&amp; ( y &gt; z) )
                || ( (x &gt;= z) &amp;&amp; ( x &lt; w) )

-- the actual algorithm
perfect_elimination_order :: Concurrent a =&gt; [a] -&gt; [a]
perfect_elimination_order list = reverse . concat $ do_elimination [] [list]

split_for_elimination :: Concurrent a =&gt; a -&gt; [a] -&gt; [[a]]
split_for_elimination x = listify . partition  (isConcurrent x) 
            where listify (a,b) = [a,b]

do_elimination :: Concurrent a =&gt; [a] -&gt; [[a]] -&gt; [[a]]
do_elimination used list | null difflist = list
                         | otherwise = do_elimination (pivot:used) 
                            $ list &gt;&gt;= (split_for_elimination pivot)
            where pivot = head difflist
                  difflist = (concat list) \\ used

-- example
list :: [(Integer, Integer)]
list = [(a,b) | a &lt;- [1,2,3,4,5,6], b&lt;-[1,2,3,4,5,6] ]

main = print $ perfect_elimination_order list


Any ideas how to decrease memory usage?
Silly me. The function listify also includes the empty list. Therefore
in each recursion of do_elimination the length of list gets doubled. This
is not bounded by the length of the original list anymore.

All these empty lists get stripped away by concat later.

Acknowledgement: Finding this out would have taken a great deal longer if not for a very kind person who took me by the hand and walked me through it.