[Haskell-cafe] Re: Pickling a finite map (Binary + zlib) [was: Data.Binary poor read performance]

[Christian Maeder]

Felipe Lessa wrote:
 The builds seem fine, but we spot a (length xs) on the beginning.
 Maybe this is the culprit? We already know the size of the map (it was
 serialized), so it is just a matter of exporting
 
 fromDistinctAscSizedList :: Int - [(k, a)] - Map k a

Excellent idea, what does stop you? fromDistinctAscList is already a
function with a precondition that is not checked.

 Too bad 'Map' is exported as an abstract data type and it's not
 straighforward to test this conjecture. Any ideas?

One really doesn't want to see the actual implementation (except for
debugging or tuning purposes), but maybe conversions to and from a fully
(and uniquely) balanced binary tree are desirable.
(a basic binary tree data type is still missing on hackage).

I think, equal maps should not yield different serialization results
just because the internal tree structure happens to be different, but
that's of course debatable.

Cheers Christian

Maybe the discussion should be continued on librar...@haskell.org?

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: Pickling a finite map (Binary + zlib) [was: Data.Binary poor read performance]

[Christian Maeder]

 fromDistinctAscList :: [(k,a)] - Map k a
 fromDistinctAscList xs
   = build const (length xs) xs
   where
 -- 1) use continutations so that we use heap space instead of stack 
 space.
 -- 2) special case for n==5 to build bushier trees.
 build c 0 xs'  = c Tip xs'
 build c 5 xs'  = case xs' of
((k1,x1):(k2,x2):(k3,x3):(k4,x4):(k5,x5):xx)
 - c (bin k4 x4 (bin k2 x2 (singleton k1
 x1) (singleton k3 x3)) (singleton k5 x5)) xx

By the way, did anyone test if (or when) this n==5 case bushier trees
gains something?

Thanks Christian
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe