Pairing Heap for Clean Language

PairingHeap.dcl

definition module PairingHeap

:: Heap a = Empty | Node a [Heap a]

peek :: (Heap a) -> a
push :: a -> (Heap a) -> (Heap a) | Ord a
pop  :: (Heap a) -> (Heap a) | Ord a
listToHeap :: ([a] -> (Heap a)) | Ord a
heapToList :: (Heap a) -> [a] | Ord a

PairingHeap.icl

implementation module PairingHeap
import StdEnv

peek :: (Heap a) -> a
peek Empty = abort "Heap empty\n"
peek (Node n _) = n

mergeHeap :: (Heap a) (Heap a) -> (Heap a) | Ord a
mergeHeap Empty p = p
mergeHeap p Empty = p
mergeHeap m=:(Node x ps) n=:(Node y qs) 
    | y < x     = Node y [m:qs]
    | otherwise = Node x [n:ps]

push :: a -> (Heap a) -> (Heap a) | Ord a
push x = mergeHeap (Node x [])

pop :: (Heap a) -> (Heap a) | Ord a
pop Empty = Empty
pop (Node _ ps) = foldr mergeHeap Empty (pair ps) where
    pair [a:b:xs] = [mergeHeap a b:pair xs]
    pair xs       = xs

listToHeap :: ([a] -> (Heap a)) | Ord a
listToHeap = foldr push Empty

heapToList :: (Heap a) -> [a] | Ord a
heapToList Empty = []
heapToList n=:(Node x _) = [x:heapToList (pop n)]