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?