How to correctly make a selection of all locations in a structure that match a pattern (memoization)?


#1

When traversing a structure, pattern matching can be successful for one or several locations. It could be required to apply several functions on all elements of a same selection as a sequence (f1 on all nodes; f2; f3; … ).
In order to avoid repeating of the exactly same recursion, especially on very large structures, I would like to do some memoization, e.g. storing the path to each matching location in a list.
We assume that no other function is concurrently accessing the same structure.

I’m thinking about the following simple solutions:

(* 1 without type modification, returning a path to matching values as a string list list *)
type t = Leaf of int | Node of  t *  t
val selection : t -> int -> string list list

let t1 = Node ( Node (Leaf 0, Leaf 2), ( Node (Leaf 0, Leaf 4) ) )
selection t1 0 = [ ["L"; "L" ] ; ["R"; "L" ] ]
(* 2 with type modification, such as an additional identifier field *)
type t = Leaf of int | Node of  t *  t * string
val selection : t -> int -> string list list

let t1 = Node ( Node (Leaf 0, Leaf 2), ( Node (Leaf 0, Leaf 4) ) )
selection t1 3 = [ ["1 ";"2";"3"] ; ["1 ";"5";"6"] ]

Is there another way that could take advantage of the OCaml way of storing values?
What about using the value representation in memory of targeted elements ? (not very FP style, but just to know if it makes sense, for some exotic applications)

Or even more simple: are there some OCaml libraries or bindings for doing that job (traverse, select/memoization) in an optimized way?


#2

I am a bit in a hurry at the moment, have a look at https://gitlab.inria.fr/fpottier/fix (it is also published on opam)


#3

Thanks.
That confirms that even if it’s very instructive to write such generic functions (and must be attempted), people before us had the same requirements and wrote well founded and optimized libs.


#4

There’s also a memoization function in janestreet’s Core.Memo module:

https://ocaml.janestreet.com/ocaml-core/latest/doc/core_kernel/Core_kernel/Memo/