On Sun, 15 May 2011 14:23:36 +0200
Daniel Fischer
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