backtracking / ptmap Goto Github PK

Downstream for Fedora I wrote this patch which adds supports for Map.filter_map. It is required for OCaml 4.11.
https://src.fedoraproject.org/rpms/ocaml-ptmap/blob/master/f/ptmap-ocaml-4.11.patch

Because obuild can’t build itself on bytecode-only platforms yet

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!

cf. UnixJunkie#1

According to the doc, bindings:

Return the list of all bindings of the given map. The returned list is sorted in increasing order with respect to the ordering Ord.compare, where Ord is the argument given to Map.Make.

The following code prints the returned list, 4 2 6 1 5 3, which is unordered:

let list_to_map lst =
  let rec loop l map = match l with
  | [] -> map
  | item :: ls -> loop ls (Ptmap.add item true map)
  in
  loop lst Ptmap.empty

let test_bindings =
  let l, _ = List.split (Ptmap.bindings (list_to_map [3; 1; 2; 4; 6; 5])) in
  List.iter (Printf.printf "%d ") l

let main () =
  test_bindings

let () = main ()