[Haskell-cafe] Collections

[Thomas Conway]

On 6/20/07, Spencer Janssen <sjanssen at cse.unl.edu> wrote:
>  (I often miss priority queues)

I must say, there have been several times lately where I have wanted
such a type. Actually, I've found Data.Map isn't too bad if you use
deleteMin/deleteMax. What's more, deleteM{in,ax} & insert are both
O(log n) for most reasonable implementations that could be used for a
Data.Map-like structure, which works out much the same in many cases.

In particular, I find my self wanting to use a priority queue for
N-way sorted merge, which you can do with Data.Map: (compiles, so
clearly works even though I have not tested it. ;-) )

import Data.List as List
import Data.Map as Map

merge :: Ord t => [[t]] -> [t]
merge lists = merge' $ Map.fromList $ concatMap makePair lists
    where
    makePair [] = []
    makePair (x:xs) = [(x,xs)]

merge' heap
    | Map.null heap = []
    | otherwise     = x:(merge' $ removeEqual x $ reinsert xs heap')
    where
    ((x,xs), heap') = deleteFindMin heap

reinsert [] heap = heap
reinsert (x:xs) heap = Map.insert x xs heap

removeEqual x heap
    | Map.null heap = heap
    | x /= y        = heap
    | otherwise     = removeEqual x $ reinsert ys heap'
    where
    ((y,ys), heap') = deleteFindMin heap


The other thing I have found myself doing often is using splitLookup
followed by union, though what I really want is "join" being the dual
of split - i.e. requiring all the keys in the rhs to be greater than
the keys in the lhs. My own AVL tree implementation has this operation
which is O(log n), which is rather better than union's O(n log n).

T.
-- 
Dr Thomas Conway
drtomc at gmail.com

Silence is the perfectest herald of joy:
I were but little happy, if I could say how much.