# 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 => Concurrent a where
isConcurrent :: a -> a -> Bool

instance Ord a => Concurrent (a, a) where
isConcurrent (x,y) (z,w) = ( (x <= z) && ( y > z) )
|| ( (x >= z) && ( x < w) )

-- the actual algorithm
perfect_elimination_order :: Concurrent a => [a] -> [a]
perfect_elimination_order list = reverse . concat $do_elimination [] [list] split_for_elimination :: Concurrent a => a -> [a] -> [[a]] split_for_elimination x = listify . partition (isConcurrent x) where listify (a,b) = [a,b] do_elimination :: Concurrent a => [a] -> [[a]] -> [[a]] do_elimination used list | null difflist = list | otherwise = do_elimination (pivot:used)$ list >>= (split_for_elimination pivot)
difflist = (concat list) \\ used

-- example
list :: [(Integer, Integer)]
list = [(a,b) | a <- [1,2,3,4,5,6], b<-[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.