sdrodge 2017-03-06 07:45:40
I'm mostly looking for suggestions about a better way to structure the code, since the structure feels a little disgusting, and possibly ways to improve the asymptotics without using ST or IO.
sdrodge 2017-03-06 07:46:43
Maybe there's some unified data structure that didn't occur to me that does median tracking as well as persistence?
kadoban 2017-03-06 07:49:06
sdrodge: Yay hackerrank haskell people xD Not enough haskellers on there, heh.
sdrodge 2017-03-06 07:49:58
kadoban: xD
dmwit 2017-03-06 07:53:08
f-a: There is `IntMap`.
kadoban 2017-03-06 07:53:58
sdrodge: You can just use Data.Map.Map using either elemAt and size to check the median, or splitRoot in case elemAt isn't in the version they use, can't recall. The constants will be worse, but less code required.
f-a 2017-03-06 07:54:32
dmwit: thanks. are the ints in intmap invariant with the respect to the changes (add/remove) to the map?
kadoban 2017-03-06 07:54:38
IntMap would also work for the same idea, except `size` in O(n) in IntMap
kadoban 2017-03-06 07:54:52
is O(n)*
sdrodge 2017-03-06 07:55:50
Nice. Didn't know about that.
dmwit 2017-03-06 07:57:26
IntMap doesn't support elemAt. =(
kadoban 2017-03-06 07:58:16
Ya, IntMap isn't super useful for this. If you annotate it with the size, so you can check in O(1) time, then you can implement "elemAt" using splitRoot without too much trouble, but at that point I'm not sure it's worth it.
kadoban 2017-03-06 07:58:48
Also splitRoot doesn't really guarantee wtf it does I guess, it's more of an internal function it seems, but ... in practice it'd be fine anyway.
dmwit 2017-03-06 07:58:53
splitRoot won't give you annotated subtrees.
sdrodge 2017-03-06 07:58:55
Still certainly gonna be cleaner than the juggling between two maps that I'm doing.
kadoban 2017-03-06 07:59:06
dmwit: Hmm ... good point.
dmwit 2017-03-06 07:59:43
IntMap doesn't support elemAt for exactly the same reason size is O(n). You could fix both, at the cost of reduced efficiency and increased space usage for all other operations.
dmwit 2017-03-06 07:59:58
This was a conscious engineering decision made by the containers folks and unlikely to be reversed.
sdrodge 2017-03-06 08:03:25
kadoban: That's starting to get just as ugly as the current solution, imo.
kadoban 2017-03-06 08:03:58
Ya, it's not terribly pretty. Anything to avoid having to create actual data structures though :)
sdrodge 2017-03-06 08:04:21
What's wrong with making data structures?
kadoban 2017-03-06 08:05:48
Requires a lot of effort. If I can just reuse one that already exists, and if it wont' get TLE or whatever, I usually do that.
