persistent
persistent copied to clipboard
polux
Override map, where and expand methods in PersistentMap to return PersistentMap<K, V> as type, instead of Iterable<Pair<K, V>>
The current implementation of PersistentMap does not override Iterable methods like map, where and expand.
A client of PersistentMap that calls myPersistentMap.where((pair) => ...); is clearly expecting another PersistentMap as return, but he gets an Iterable<Pair<K, V>> instead.
If you look at the history, I used to have that, at least for map if I recall correctly. But I wanted to be consistent with Dart's core library where map and where return lazy views of the collections instead of eagerly computing a new collection. For instance:
main() {
print([].map((x) => x).runtimeType);
}
prints MappedListIterable. I was considering adding strict versions of map and where instead (called strictMap and structWhere for instance).
I could definitely improve the situation by adding a constructor to Map that accepts an Iterable of pairs though.
But I wanted to be consistent with Dart's core library where map and where return lazy views of the collections
You still have to come with a solution that returns lazy views of PersistentMap instead of lazy views of Iterable<Pair>.
I could definitely improve the situation by adding a constructor to Map that accepts an Iterable of pairs though.
I thought about that too. It solves this problem at least for now. So I vote for it! :)
Well, I forked and made these palliative measures:
- Created a constructor:
PersistentMap.fromPairs, that accepts an Iterable of pairs - Created a
strictMapandstrictWherethat return PersistentMap instead of Iterable<Pair>
You can see the diff here if you want to.
But the jackpot will be won when overriding map, where and expand to return PersistentMap and keeping it's 'laziness'. I don't have a clue about how to do that.
You can see the diff here if you want to.
Great! Do you mind if I patch those in? (Maybe you want to create a pull request so that github keeps track of that). I actually had a slightly better version of strictMap which recursively created a map with the same shape. I'll revive it and override your default implementation of strictMap. I'll do the same for where (I'm wondering if I didn't have something).
But the jackpot will be won when overriding map, where and expand to return PersistentMap and keeping it's 'laziness'.
Indeed, that would be the best.
I don't have a clue about how to do that.
I have, I'll work on it. The fact that you're using the library kind of revived the interest I had in it :) Are you using it actually, or are you simply looking at it out of curiosity?
If you're interested in FP libs you can look at my other Dart projects on github they all are more or less about FP.
As I said before I'm working on this experimental paypal-merchant library. It returns one big name value pair string that I should parse to make objects out of it. I could isolate separate parts of the message in different maps ant lists of maps. Constructing meaningful objects out of it involves filtering and mapping or even better flatmapping these map structures. Since Dart doesn't provide these FP methods on maps, I'm looking for a library that fits in.
I opened a pull request on that diff.
I've been thinking about the comparison of performance between PersistenceMap insert and lookup and Dart Map [key]= and [key] equivalent operators. It would be good to document this don't you think?
It was my plan to document complexities, but in that case insert and []= have the same big O complexity: O(1) (average case, or assuming no collisions). It's the magic of HAMTs: each node has 32 children, so at most your tree is 6 levels deep before your memory is filled. Which means that any insertion is at most 6 copies of at most 34 bytes (max size of a node). Which means it is "effectively constant time". Same thing for lookup.
Now in practice insert is slower than []= but not that much actually. I think it's fair to say it's "explicitly constant time", just as Scala does. I want to do that but this requires some explanation. I'm opening a feature request: #3.