Commits

Yit Phang Khoo  committed dae4c03

Generalize SAList.partition_with_key to take keys of any type.

  • Participants
  • Parent commits a8b2567

Comments (0)

Files changed (2)

File Source/Adapton/SAList.ml

                 ( split_left xs, split_right xs )
 
         (** Create memoizing constructor and updater to partition a self-adjusting list with a predicate and key. *)
-        let memo_partition_with_key pred =
-            PartitionType.memo2 (module R) (module L) begin fun partition k xs -> match force xs with
+        let memo_partition_with_key (type a) (module K : Hashtbl.SeededHashedType with type t = a) pred =
+            PartitionType.memo2 (module K) (module L) begin fun partition k xs -> match force xs with
                 | `Cons ( x, xs ) ->
                     let left, right = split_partition (partition k xs) in
                     if pred k x then
 
         (** Create memoizing constructor and updater to quicksort a self-adjusting list with a comparator. *)
         let memo_quicksort cmp =
-            let partition, _ = memo_partition_with_key (fun k x -> cmp x k < 0) in
+            let partition, _ = memo_partition_with_key (module R) (fun k x -> cmp x k < 0) in
             let quicksort, update_quicksort = memo2 (module L) (module L) begin fun quicksort xs rest -> match L.force xs with
                 | `Cons ( x, xs ) ->
                     let left, right = split_partition (partition x xs) in

File Source/Adapton/Signatures.ml

             : (module SAListType.S with type sa = sa and type data = 'a and type t = 'b) -> ('a -> data -> data) -> ('b -> data -> t) * (t -> 'b -> data -> unit)
         module PartitionType : SAType.S with type sa = sa and type 'a thunk = 'a thunk and type data = t * t and type t = (t * t) thunk
         val split_partition : PartitionType.t -> t * t
-        val memo_partition_with_key : (data -> data -> bool) -> (data -> t -> PartitionType.t) * (PartitionType.t -> data -> t -> unit)
+        val memo_partition_with_key
+            : (module Hashtbl.SeededHashedType with type t = 'a) -> ('a -> data -> bool)
+                -> ('a -> t -> PartitionType.t) * (PartitionType.t -> 'a -> t -> unit)
         val memo_quicksort : (data -> data -> int) -> (t -> t) * (t -> t -> unit)
     end
 end = SAListType