Back to Questions
2.3k
views7
comments
Help with functional data structure
f#functional

Hi

I want to create an immutable tree data structure in F#. However, Im populating the tree from data in a different format, and I need to add nodes at various points within the tree structure during the creation of the tree.

This is reasonably easy using a mutable data structure (eg a hierarchy of Dictionary<T,U> objects in C#), but is there a reasonably efficient way of doing this using a purely functional approach ?

Thanks

Dean

.

You might find this helpful Dean:

[link:books.google.com]

Purely Functional Data Structures By Chris Okasaki. I didn't look at the entire thing on Google Books but I'm pretty sure the entire text is free somewhere on the web if it's not all on G Books.

Hope this helps.

--

Onorio

By on 4/6/2010 12:31 PM ()

The Pense-moi blog has been converting these into F#:

[link:lepensemoi.free.fr]

By on 4/6/2010 2:40 PM ()

Good link.

By on 4/6/2010 5:49 PM ()

Thanks all

It looks like I need to brush up on my data structures and take a good look at the references suggested.

Thanks very much for all your help

Dean

By on 4/6/2010 11:43 PM ()

There are functional ds's that maintain functional "holes" so that you can do this sort of thing, I beleive. (I'll try and find the links.) I don't remember how these hold up under multiple readers/writers, if that's your intent.

However, if you really want random write access into the tree I think you'll pay a price in code complexity and must likely run-time cost over just using the nested-dict approach. Do you need a functional DS, or is this an academic exersise? The beauty if f# is being able to choose the best approach at each descision-point.

Though I'm not sure what "from data in a different format" and "add nodes at various places" really means here...

By on 4/6/2010 10:01 AM ()

See if this helps:

[link:scienceblogs.com]

By on 4/6/2010 10:15 AM ()

I really would like to have a generic zipper in F# but from my understanding, it would require delimited continuation(well the Haskell version seems to be implemented using that).

clojure has a zipper library which handles most of its collection types, not sure how it is implemented there.

talking about clojure, it is an interesting language(well the LISP dialect is unlikely to make it main stream) for the JVM. I prefer the ML family like Haskell/F# but getting used to parentheses is not as hard as I thought especially when most of the time things are done via higher order functions.

By on 4/6/2010 10:43 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