Fold directly

[matthewleon]

solves #134

This gives over a 10x speed improvement on larger maps (compare branch https://github.com/matthewleon/purescript-maps/tree/foldl-bench):

before

foldl: midsize map (10000)
mean   = 24.36 ms
stddev = 1.59 ms
min    = 22.57 ms
max    = 31.34 ms
foldl: big map (1000000)
mean   = 3.90 s
stddev = 143.96 ms
min    = 3.75 s
max    = 4.25 s

after

foldl: midsize map (10000)
mean   = 2.32 ms
stddev = 485.38 μs
min    = 2.04 ms
max    = 5.29 ms
foldl: big map (1000000)
mean   = 249.78 ms
stddev = 64.46 ms
min    = 226.67 ms
max    = 433.12 ms

[hdgarrood]

This seems very similar to the implementation used in #132; can this be abstracted into a single function which all of these depend on? I also wouldn't want to have foldl do it the fast way and the other two Foldable member implementations do it the slow way, ideally.

[matthewleon]

This seems very similar to the implementation used in #132; can this be abstracted into a single function which all of these depend on?

Will try.

I also wouldn't want to have foldl do it the fast way and the other two Foldable member implementations do it the slow way, ideally.

foldMap is switched to use foldl. I'll try giving foldr a similar rewrite. I'm not sure the benefits would be as drastic, as you won't get TCO.

[matthewleon]

I also wouldn't want to have foldl do it the fast way and the other two Foldable member implementations do it the slow way, ideally.

After attempting to do this, I've restored right folds to using the intermediate lists. Any attempt to do a right fold directly on the Map is not stack-safe.

[matthewleon]

This seems very similar to the implementation used in #132; can this be abstracted into a single function which all of these depend on?

I can't see a way to do this. It seems to me that folding and toUnfoldable are in some way "opposites". They bear a superficial similarity, but I can't see have them rely on a common function.

[matthewleon]

I've edited down my last two posts here... I believe common functionality between keys, values, and toAscUnfoldable can indeed by refactored. I think that's out of scope for this particular PR though. I will try some strategies on the appropriate PR.