Back to Questions
1.0k
views5
comments
0
score		+
-
Recursion on a tree structure
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 * TreeNow 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.

.Reply
Hide this comment

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

Usuals solutions are :

1
2
3
4
5
6
7
8
9

 

let rec sum t = 

   match t with

   | Leaf n -> n    

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

or 

1
2
3
4
5
6
7
8
9
10
11
12
13
14

 

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
By on 6/29/2009 3:03 PM ()Reply
Hide this comment

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

By on 6/30/2009 1:16 PM ()Reply
Hide this comment

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

You can use | with the function keyword

1
2
3
4
5
6
7
8

 

let rec sum = function

| Leaf n -> n

| Node (l,r) -> sum l + sum r
By on 7/1/2009 12:27 AM ()Reply
Hide this comment

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...

By on 7/1/2009 1:02 PM ()Reply
Hide this comment

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.

By on 6/29/2009 2:50 PM ()Reply

    Topic tags

    See all tags
    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper

    Logging in...