Help in designing a tree structure - Tension between functional and OOP

Question

Hi, I've been learning f# in the previous days, writing a small project which, at last, works (with the help of SO, of course).

I'm trying to learn to be as idiomatic as possible, which basically means that I try to not mutate my data structures. This is costing me a lot of effort :-) In my search for idiomatic functional programming, I have been trying to use as much as possible lists, tuples and record, rather than objects. But then "praticality beats purity" and so I'm rewriting my small project using objects this time.

I thought that you could give me some advice, surely my idea of "good functional programming design" is not yet very well defined.

For instance I have to modify the nodes of a tree, modifying at the same time the states at two different levels (L and L+1). I've been able to do that without mutating data, but I needed a lot of "inner" and "helper" functions, with accumulators and so on. The nice feeling of being able to clearly express the algorithm was lost for me, due to the need to modify my data structure in an involved way. This is extremely easy in imperative languages, for instance: just dereference the pointers to the relevant nodes, modify their state and iterate over. Surely I've not designed properly my structure, and for this reason I'm now trying the OOP approach.

I've looked at SICP, at How to design programs and have found a thesis by C. Okasaki ("Purely functional data structures") but the examples on SICP and HTDP are similar to what I did, or maybe I'm not able to understand them fully. The thesis on the other hand is a bit too hard for me at the moment :-)

What do you think about this "tension" which I am experiencing? Am I interpreting the "never mutate data" too strictly? Could you suggest me some resource?

Thanks in advance, Francesco

Answer 1

What do you think about this "tension" which I am experiencing? Am I interpreting the "never mutate data" too strictly? Could you suggest me some resource?

In my opinion, if you're learning functional programming for the first time, its best to start out with zero mutable state. Otherwise, you'll only end up falling back on mutable state as your first resort, and all of your F# code will be C# with a little different syntax.

Regarding data structures, some are easier to express in a functional style than others. Could you provide a description of how you're trying to modify your tree?

For now, I would recommend F# Wikibook's page on data structures to see how data structures are written in a functional style.

I've looked at SICP, at How to design programs and have found a thesis by C. Okasaki ("Purely functional data structures")

I personally found Okasaki's book more readable than the thesis online.

Answer 2

I guess if you start your sentence with " I have to modify the nodes of a tree, modifying at the same time the states at two different levels" then you're not really tackling your problem in a functional way. It's like writing a paper in a foreign language by first writing it in your mother tongue, then trying to translate. Doesn't really work. I know it hurts, but in my opinion it's better to immerse yourself completely. Don't worry about comparing the approaches just yet.

One way I've found to learn "the functional way" is to look at (and implement yourself!) some functional pearls. They're basically well document uber-functional elegant progams to solve a variety of problems. Start with the older ones, and don't be afraid to stop reading and try another one if you don't get it. Just come back to it later with renewed enthousiasm and more experience. It helps :)

Answer 3

For instance I have to modify the nodes of a tree, modifying at the same time the states at two different levels (L and L+1)

Why? In a functional language, you'd create a new tree instead. It can reuse the subtrees which don't need to be modified, and just plug them into a newly created root. "Don't mutate data" doesn't mean "try to mutate data without anyone noticing, and by adding so many helper methods that no one realize that this is what you're doing".

It means "don't mutate your data. Create new copies instead, which are initialized with the new, correct, values".

Answer 4

I have to modify nodes of a tree.

No you don't. That's your problem right there.

This is costing me a lot of effort

This is typical. It's not easy to learn to program with immutable data structures. And to most beginners, it seems unnatural at first. It's doubly difficult because HTDP and SICP don't give you good models to follow (see footnote).

I thought that you could give me some advice, surely my idea of "good functional programming design" is not yet very well defined.

We can, but you have to tell us what the problem is. Then many people on this forum can tell you if it is the sort of problem whose solution can be expressed in a clear way without resorting to mutation. Most tree problems can. But with the information you've given us, there's no way for us to tell.

Am I interpreting the "never mutate data" too strictly?

Not strictly enough, I'd say.

Please post a question indicating what problem you're trying to solve.

---

Footnote: both HTDP and SICP are done in Scheme, which lacks pattern matching. In this setting it is much harder to understand tree-manipulation code than it is using the pattern matching provided by F#. As far as I'm concerned, pattern matching is an essential feature for writing clear code in a purely functional style. For resources, you might consider Graham Hutton's new book on Programming in Haskell.

Answer 5

Take a look at the Zipper data structure.