[Haskell-cafe] Collections
Thomas Conway
drtomc at gmail.com
Tue Jun 19 19:26:51 EDT 2007
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.
More information about the Haskell-Cafe
mailing list