Back to Questions
3.0k
views3
comments
Mutable Tree Structure and partial locks
f#parallel

Hi!

I am currently working on a kind of binary tree implementation.

Imagine the following defintion

1
2
3

 type 'a Tree =
        | Empty
        | Node of 'a Tree * 'a * 'a Tree

I am quite new to F#. As I understood this structure is immutable and therefore any change of the tree - not matter how many nodes are affected - result in a completely new copy of the tree.

What I want is parallel ("thread safe") processing of the tree - as well reading as modifying. I thought about realizing this using locks on a complete node or the content of a node only. For example the tree should be able to grow while being read.

For this I need to dynamically work on the whole structure - e.g. for adding a node I need to replace a Node(Empty,_,Empty) with Node(Node(Empty,_,Empty),_,Empty) while blocking the Node containing that original Node(Empty,_,Empty) as a child without replacing the whole tree.

Is there any way to realize that in F#?

Thank you in advance!

.

> not matter how many nodes are affected - result in a completely new copy of the tree.

That is not the case - there is typically structure sharing. If you're replacing a node, then it will share the existing left and right sub-trees. So if you're replacing the root node, then the whole rest of the tree is simply linked to. If you're replacing a leaf node, then as you bubble-up, you'll be sharing parts of the existing tree.

By on 5/14/2011 1:56 PM ()

thank you for your answer!

> there is typically structure sharing. If you're replacing a node, then it will share the existing left and right sub-trees.

how do I achieve this? How would I e.g. implement an "add" (member-) method to the tree type I defined that does not return a new tree but changes the existing one instead?

By on 5/16/2011 2:39 AM ()

Try googleing "F# binary tree".

Here's the top one:

Purely Functional Data Structures: An F# Binary Tree

By on 5/20/2011 10:00 AM ()

    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