Type hydra = Node of hydra list

Hello everyone ,
In order to prepare an exam which is in one week , i’ve tried many things to solve this problem , but i actually miss a part something , i can’t figure it out …

The following exercice is this one :slight_smile:
type hydra= Node of hydra list
The arity of a node of a hydra is its number of “girls”. ̨
Write ̨ a ̨ function ̨ arite_max : hydra-> int
which calculates the maximum arity of a node in a hydra. ̨

I’ve tried this : ( this is quite awfull , but was the closest to the result I need to find…)

  let rec arite h =
     match h with
     | Node([ ])->0
     | Node(a :: b)-> 1 + arite (Node(b))
   let rec aritemax h  =
     match h with
     |Node([ ])->0
     |Node(a :: [ ])-> aritemax a
     |Node(a:: b ::c)->max(arite (Node(a:: b ::c))) (arite (Node( c )))

but when I test it with following examples :

# let _ = aritemax (Node([Node([Node([]);Node([]);Node([]);Node([])]);Node([])]));;
- : int = 2
# let _ =  aritemax (Node([Node([Node([]);Node([]);Node([])])]));;
- : int = 3
# let _ = aritemax (Node([Node([Node([Node([]);Node([]);Node([]);Node([]);Node([])])])]));;
- : int = 5

If i get correctly the exercice , I think the first example shoud return 4 but seems to stop the level before it can calcule it …

If someone is familiar to this and can help me ( just an idea is enough ) , thanks a lot & happy new year !
For everyone else , Happy new year !

You should use backquotes (```) around your code snippets so that they’re displayed properly.

The problem, as you have identified, is that you don’t fully recurse into the structure, which is why the first example returns the wrong answer (you just never inspected the interior list of nodes). The easiest way is to solve it with a single recursive function with two accumulators; as you go down the list you’re accumulating the length of the list of “girls” and recursively keeping track of the biggest arity of each of those “sub-hydra” giving something like this:

let aritemax (Node hs) =
  let rec walk_girls acc cur = function
  | [] ->
      (* left to the reader *)
  | (Node h)::hs ->
      walk_girls (* left to the reader *) (succ cur) hs
  walk_girls (* left to the reader *)

(I’ve filled in the code for the second accumulator, which is working out the length of the current list - you can fill in the remaining code for recursing into each hydra and keeping track of the biggest list seen so far)

1 Like