[Haskell-cafe] Re: Collections

[apfelmus]

Thomas Conway wrote:
> 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

Eh, why not a simple mergesort that also deletes duplicates?

    -- the nested lists must be sorted: map sort xs == xs
  mergesort :: Ord a => [[a]] -> [a]
  mergesort []  = []
  mergesort xs  = foldtree1 merge xs

  foldtree1 :: (a -> a -> a) -> [a] -> a
  foldtree1 f [x] = x
  foldtree1 f xs  = foldtree1 f $ pairs xs
     where
     pairs []        = []
     pairs [x]       = [x]
     pairs (x:x':xs) = f x x' : pairs xs

  merge :: Ord a => [a] -> [a] -> [a]
  merge []     ys     = ys
  merge xs     []     = xs
  merge xs'@(x:xs) ys'@(y:ys)
      | x  < y    = x:merge xs  ys'
      | x == y    =   merge xs  ys'
      | otherwise = y:merge xs' ys

The function 'foldtree1' folds the elements of the list as if they where
in a binary tree:

  foldrtree1 f [1,2,3,4,5,6,7,8]
 ==>
  ((1 `f` 2) `f` (3 `f` 4)) `f` ((5 `f` 6) `f` (7 `f` 8))

and with f = merge, this serves as heap (although a very implicit one).
The hole mergesort will take

  O(n*log (length xs)) where n = length (concat xs)

time. Moreover, this variant of mergesort happens to generate elements
as soon as they are available, i.e.

 head . mergesort  is  O(n)

See also

 http://article.gmane.org/gmane.comp.lang.haskell.general/15010


> 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).

2-3-Finger trees support efficient splits and concatenations:

  http://www.soi.city.ac.uk/~ross/papers/FingerTree.html

In fact, you can build a plethora of data structures from them.

Regards,
apfelmus