[Haskell-beginners] Printing the entries of a Data.Map m

[Manfred Lotz]

On Sun, 15 May 2011 14:23:36 +0200
Daniel Fischer <daniel.is.fischer at googlemail.com> wrote:

> On Sunday 15 May 2011 11:34:33, Matthias Guedemann wrote:
> > Hi Manfred
> > 
> > > It didn't make much of a difference in runtime doing it without
> > > toList. I'm not quite sure if it is really more efficient or not.
> > > Perhaps I would have to create dictonary with some millions
> > > entries in order to see a noticable difference?
> > 
> > Probably, Haskell is not very deterministic for memory / runtime
> > forecasts :-)
> > 
> > In theory there should be no difference in complexity, both need one
> > sweep over all entries of the Map. There could perhaps be a constant
> > cost for constructing the list.
> 
> The call-tree for the list construction is similar to the call-tree
> that traverse builds.
> However, traverse assembles a new Map. While it's trivial to discard 
> consumed list-cells (if the list is consumed sequentially), that is
> not so for Maps. Unless the compiler manages to completely eliminate
> the new Map, that is going to cost considerably more than the
> throwaway list-cells.
> 
> > Nevertheless, laziness should make it
> > possible to run in constant space, as neither the list, nor the
> > transformed Map is used.
> 
> Well, you need the space for the initial Map, that is O(size).
> I assume you mean that the additional memory needed is O(1).
> That is almost true for going through the list, since that is swiftly 
> collected. The call-tree to get at the elements, however, is O(log
> size), but that's practically constant size.
> For traverse, that is only true if the new Map is completely
> discarded (Maps are spine-strict, so if it's not completely ignored,
> its full spine is built, requiring O(size) space).
> 
> > So differences are probably small.
> > 
> > But is possible, take some measurements and report, not just
> > runtime, but also heap space usage.
> 
> Note that the "mapM_ print . toAscList" prints the (key, value) pairs
> while the traverse (or Data.Traversable.mapM) only prints the values.
> That makes a difference.
> 
> I put together a small (trivial) test:
> 
> viaList :: (Ord k, Show k, Show v) => Map k v -> IO ()
> viaList = mapM_ print . toAscList
> 

I also tried something similar, and indeed you are right. mapM_ in
conjunction with toList is better in terms of memory and runtime
(mainly because GC is less busy) than using functions from Traversable.


Really interesting.


-- 
Manfred