backtracking
Merge implementation
Out of curiosity, is there a reason that the merge implementation is as 2 folds as as opposed to the recursive one written in the original Okasaki paper?
The running time of the papers implementation is O(n_1 + n_2) whereas I believe that your version has an extra (albeit 'constant', log_32) cost for the lookup? My knowledge of SML is only based on my OCaml, so I might be missing something from the paper.
Thank you ahead of time!
@UnixJunkie I was referencing the code in the Okasaki's paper on page 83. It is explicitly written out there, albeit in SML. I haven't compared the two versions to see if this version is faithful to the paper (it does seem to be), so this issue is a question of perhaps there is a good reason to merge this way (although one of the points of the Okasaki paper was the better merge).
For my problem the computation doesn't map neatly onto Patricia tree's so I never pursued using ptmap.
OCaml's merge function, as promised in Map.S, is much more complex than the function merge in Okasaki&Gill's paper.
Indeed, the function passed as argument is used for a binding present in both maps for a given key (in as in the paper) but also for keys present in one map but not in the other (contrary to the paper). This would make the code of merge really complex. I guess this is the reason why @UnixJunkie contributed this simpler (but less efficient) implementation of merge.
Yeah, sorry. I just added merge for interface compatibility reasons, IIRC.
@rleonid note that if you submit a more efficient version, it will very probably be accepted
At least I made a more efficient implementation of union following the paper (see commit b18f4c3).