OCaml walks of arbitrary depth tuples
I am trying to better understand OCaml type inference. I created this example:
let rec f t = match t with
| (l,r) -> (f l)+(f r)
| _ -> 1
and I want to apply it to any nested-pair binary tuple (pair) to get the total number of leaves. Example: f ((1,2), 3)
Function f refuses to compile because there is a type contradiction at (fl): "This expression is of type" a ", but an expression of type" a * "b" was expected.
The question is, "a being of any type, also cannot be a pair, or can it be handled by case? Is there any method to move tuples of arbitrary depth without converting them to other data structures such as variants?"
PS: In C ++, I would solve this problem by creating two "f" template functions, one to handle tuples and other types.
source to share
There is a way to do this, although I would not recommend it to a new user because of the difficulties that arise. You should get used to writing regular OCaml first.
However, you can do arbitrary types generically by fixing the required structure as a GADT. For this simple task, it's pretty simple:
type 'a ty =
| Pair : 'a ty * 'b ty -> ('a * 'b) ty
| Other : 'a ty
let rec count_leaves : type a . a -> a ty -> int =
fun a ty ->
match ty with
| Pair (ta, tb) -> count_leaves (fst a) ta + count_leaves (snd a) tb
| Other -> 1
Note that pattern a ty
matching in matches pattern matching by value in your (poorly typed) example function.
More useful functions can be written with a more complete type representation, although the mechanism becomes heavy and complex when it is necessary to support arbitrary tuples, records, sum types, etc.
source to share
Any combination of tuples will have a value form fully described by that type (because there is no "choice" in the type structure) - so the question "number of sheets" can be answered completely statically at compile time. Once you have a function working on that type - that function is fixed to only work on that specific type (and shape).
If you want to build a tree that can have different forms (but the same type - hence can be handled by the same function) - you need to add variations to the mix, that is, the classic type 'a tree = Leaf of 'a | Node of 'a tree * 'a tree
or any other type that describes the value with some dynamic "selection" of the shape.
source to share