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?
