Ocaml recursion: pattern matching
I am trying to write to a recursive fn that changes an untagged tree to a marked tree using a helper function.
necessary information:
type nucleotide =
| G | C
| A | T
type helix = nucleotide list
type tree =
| Leaf of helix
| Node of tree * tree
type labeled_tree =
| LLeaf of helix
| LNode of labeled_tree * helix * labeled_tree
This is a helper function:
let rec guess_parent_helix (x1: helix) (x2: helix) : helix =
begin match (x1, x2) with
([], []) -> []
| (h1 :: t1, h2 :: t2) ->
(if h1 = h2 then h1 else A) :: guess_parent_helix t1 t2
| _ -> failwith "invalid input: x1 and x2 have unequal lengths"
end
I wrote the following function but can't compile as it says I haven't run out of pattern matching: Node ((Node (_, _), _)). I don't understand how this is not part of the Node (rt, lt) template:
let rec add_ancestor_labels (r: tree) : labeled_tree =
begin match r with
| Leaf x -> LLeaf x
| Node (lt,rt) ->
begin match r with
| Leaf x -> LLeaf x
| Node (Leaf[m], Leaf[n]) ->
LNode (add_ancestor_labels lt, guess_parent_helix [m] [n], add_ancestor_labels rt)
end
end
source to share
It is an internal coincidence that is incomplete. The external match is excellent.
Update
The code as it stands doesn't make a lot of sense. After matching r
and finding the inner node, you are matching again r
. There is no need to do this, you already know that this is an internal node.
It is difficult for me to give specific advice, since I do not know how the labels should look. Here is some code that sets each label to the nucleotide concatenation below it:
let labeled_tree_of_tree tree =
let rec go t =
match t with
| Leaf x -> (x, LLeaf x)
| Node (lt, rt) ->
let (llabel, llt) = go lt in
let (rlabel, lrt) = go rt in
let label = llabel @ rlabel in
(label, LNode (llt, label, lrt))
in
let (_, ltree) = go tree in
ltree
Perhaps this will give you an idea of what your code looks like. Surely it will be more difficult than that.
source to share
The exhaustiveness check applies only to cases of a single match. Information about which cases are possible will not be propagated to nested matches, which can sometimes lead to some "impossible" cases.
If possible, it is best to continue the match with additional cases like this:
let rec add_ancestor_labels = function
| Leaf x -> LLeaf x
| Node (Leaf x, Leaf y) ->
LNode (LLeaf x,
guess_parent_helix x y,
LLeaf y)
| Node (Leaf x, Node (l, r)) ->
LNode (LLeaf x,
...,
LNode (add_ancestor_labels l,
...,
add_ancestor_labels r))
| Node (Node ..., Leaf x) -> ...
| Node (Node ..., Node ...) -> ...
An alternative to repeating an external constructor is to bind the arguments to variables and then match them:
let rec add_ancestor_labels = function
| Leaf x -> LLeaf x
| Node (l, r) ->
begin
match l, r with
| ...
end
Finally, note that Leaf [m]
this only matches leaves with spirals of length 1 - leaves with spirals of other lengths are not processed. It's unclear if this is what you intended, but the consistency check will warn you if you forget to handle the case with leaves of a different length.
The warning messages OCaml gives you for non-exhaustive matches should contain some of the missing cases, so read them carefully.
As for your function, I think it would be written like this:
let add_ancestor_labels tree =
let rec label = function
| Leaf x -> x, LLeaf x
| Node (left, right) ->
let llabel, ltree = label left in
let rlabel, rtree = label right in
let l = guess_parent_helix llabel rlabel in
l, LNode (ltree, l, rtree) in
snd (label tree)
(which is very similar to Jeffrey's suggestion.)
source to share
let rec add_ancestor_labels (r: tree) : labeled_tree =
begin match r with
| Leaf x -> LLeaf x
| Node (lt,rt) ->
begin match (lt, rt) with
| (Leaf m, Leaf n) ->
LNode (LLeaf m, guess_parent_helix m n,
LLeaf n)
| (lt,Leaf n)-> LNode(add_ancestor_labels lt,
guess_parent_helix (helix_of_tree (add_ancestor_labels lt)) n, LLeaf n)
| (Leaf m,rt)->LNode(LLeaf m, guess_parent_helix
(helix_of_tree(add_ancestor_labels rt)) m, add_ancestor_labels rt)
| (_,_)-> failwith"invalid input"
end
end
I managed to finish. Thank you for your help.
source to share