hubFS: THE place for F#

Hello,

I keep finding examples of recursion on integers, but could not get anything to work with more complex typeS. Suppose I have a Tree defined as :

type Tree =
    | Leaf of int
    | Node of Tree * Tree

Now I have an object of this type as follows :

let MyTree = Node (Leaf (3), Node (Node(Leaf (2), Leaf (4)), Leaf(1)))

How would I go and calculate recursively the sum of all the integers carried by the leaves ?

Thanks in advance for your help.

Hi,

You should give a try. Show us what you'd like to write, we'll help to make it work.

For information, there are tree structures in the standard library. Have a look in FSharp.Core/set.fs, you'll get an example. Some functions are are not too difficult to understand such as height, iter, exists...

Laurent.

You can find the solution in any book dealing as functional programming.

Usuals solutions are :

let rec sum t =

   match t with

   | Leaf n -> n    

   | Node (l,r) -> sum l + sum r

or

let sum' t =


   let rec sum_aux t s =

       match t with

       | Leaf n -> n + s

       | Node (l,r) -> sum_aux l (sum_aux r s)

   sum_aux t 0

Thanks for your answer. Turning from 20 years of imperative programming to functionnal is a bit hard... It was trying to create a function with the | grammar directly, like this :

let rec sum total =
   | Leaf
   | Node

and I was feeling something was missing, but did not find the match keyword. Also, I knew of lambda expressions, but did not know we could use it in there. I am still at the beginning of F# for scientists, but maybe I should look more into an F# for C# programmers :-)

Thanks again, this really lit my candle, as we say in French

Content d'avoir éclairé votre lanterne...

You can use | with the function keyword

let rec sum = function

| Leaf n -> n

| Node (l,r) -> sum l + sum r

C'est plein de Français dans les langages fonctionnels ! L'héritage d'OCaml, certainement...

En tout cas, merci pour le coup de main. Je crois avoir compris l'équivalence avec le mot-clé function, vu que variables et fonctions peuvent être affectées de la même manière, mais je reviendrai certainement avec d'autres questions...