Back to Questions
1.4k
views2
comments
Expert F# - computing tree size with continuations
f#

Hi,

first of all i would like to say that i really love F# and definetly enjoy reading this book.

I had some starting problems understanding continuations,
but now i think i found a little mistake that troubled my mind.

In Listing 8-11 (p.205) the size of the tree is computed with continuations,
but the count is only increased for Tips, but the Nodes contain content as well.
If i now get it right, there should be added 1 to the result of the sub-trees in the computation.

e.g. with a tree like:

1
2
3
4
5
6
7
8
9
10

(*
         x
        / \
       /   \
      x     x
     / \   / \
    o   o o   o
*)

let tree = Node( "n1", Node("n2",Tip("t1"),Tip("t2")), Node("n3",Tip("t3"),Tip("t4")) )

It computes a count of 4, wich is the count of Tips,
but there are actually 7 values in the tree.
Can someone confirm this, or else explain it to me please?
thx

.

That's exactly right. I guess its an exercise for the reader to update this to count the internal nodes as well. :-)

Kind regards

Don

By on 5/17/2008 5:11 AM ()

Here's the trivial "fix" to count all the internal nodes as well. [:)]

1
2
3
4
5
6

 let rec sizeContAcc acc tree cont =
  match tree with
  | Tip _ -> cont (1+acc)
  | Node(_,treeLeft,treeRight) -> sizeContAcc (1+acc) treeLeft (fun accLeftSize -> 
                                  sizeContAcc accLeftSize treeRight cont)

-Matteo

By on 5/25/2008 11:51 PM ()

    Topic 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