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)
            where pivot = head difflist
                  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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.