views:

174

answers:

2

How can a value of type:

type Tree =
    | Node of int * Tree list

have a value that references itself generated in a functional way?

The resulting value should be equal to x in the following Python code, for a suitable definition of Tree:

x = Tree()
x.tlist = [x]

Edit: Obviously more explanation is necessary. I am trying to learn F# and functional programming, so I chose to implement the cover tree which I have programmed before in other languages. The relevant thing here is that the points of each level are a subset of those of the level below. The structure conceptually goes to level -infinity.

In imperative languages a node has a list of children which includes itself. I know that this can be done imperatively in F#. And no, it doesn't create an infinite loop given the cover tree algorithm.

+7  A: 

You cannot do this directly if the recursive reference is not delayed (e.g. wrapped in a function or lazy value). I think the motivation is that there is no way to create the value with immediate references "at once", so this would be awkward from the theoretical point of view.

However, F# supports recursive values - you can use those if the recursive reference is delayed (the F# compiler will then generate some code that initializes the data structure and fills in the recursive references). The easiest way is to wrap the refernece inside a lazy value (function would work too):

type Tree = 
    | Node of int * Lazy<Tree list>

// Note you need 'let rec' here!        
let rec t = Node(0, lazy [t; t;])

Another option is to write this using mutation. Then you also need to make your data structure mutable. You can for example store ref<Tree> instead of Tree:

type Tree = 
    | Node of int * ref<Tree> list

// empty node that is used only for initializataion
let empty = Node(0, [])
// create two references that will be mutated after creation    
let a, b = ref empty, ref empty

// create a new node
let t = Node(0, [a; b])
// replace empty node with recursive reference
a := t; b := t

As James mentioned, if you're not allowed to do this, you can have some nice properties such as that any program that walks the data structure will terminate (because the data-structrue is limited and cannot be recursive). So, you'll need to be a bit more careful with recursive values :-)

Tomas Petricek
Nice answer. Thanks.From an efficiency point of view, is one better than the other? (Somehow I feel I will regret this;)
Muhammad Alkarouri
`Lazy` is strictly more complicated than `ref` (it has to track whether it's been evaluated or not), so `ref` should be more efficient, but I suspect there's no actual difference.
Ganesh Sittampalam
+8  A: 

Tomas's answer suggests two possible ways to create recursive data structures in F#. A third possibility is to take advantage of the fact that record fields support direct recursion (when used in the same assembly that the record is defined in). For instance, the following code works without any problem:

type 'a lst = Nil | NonEmpty of 'a nelst
and 'a nelst = { head : 'a; tail : 'a lst }

let rec infList = NonEmpty { head = 1; tail = infList }

Using this list type instead of the built-in one, we can make your code work:

type Tree = Node of int * Tree lst
let rec x = Node(1, NonEmpty { head = x; tail = Nil })
kvb
Interesting. Conceptually, would the definition of 'a lst be in some sense equivalent to a lazy list?
Muhammad Alkarouri
@Muhammad - No, `'a lst` isn't lazy, so it's just like the built-in list. The fact that it goes through a record allows you to create self-referential data structures, but you couldn't use this type to do something like creating a stream of all even numbers like you could with a lazy list.
kvb
+1 Nice trick, I didn't know this was possible!
Tomas Petricek
Thanks. That is what I am looking for.
Muhammad Alkarouri