StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<blockquote> <p>The reason I’m asking is because I want to go back and implement the data structures I learned about in the algorithms class I took this semester (skip lists, splay trees, fusion trees, y-fast tries, van Emde Boas trees, etc.), which was a pure theory course with no coding whatsoever, and I figure I might as well try to learn F# while I’m doing it.</p> </blockquote> <p>If this is an educational exercise then you may well find it easier and more enlightening to implement some of the data structures (such as skip lists) in their purely functional form. Okasaki is a great reference for elegant purely functional data structures and is very enlightening (but of little practical use).</p> <blockquote> <p>Before I start on something more substantial, is there a better way to do mutable structures like this in F#?</p> </blockquote> <p>You are working along the right lines. If you want examples, look at this <a href="http://www.lri.fr/~filliatr/ftp/ocaml/ds/heap.ml" rel="nofollow noreferrer">mutable heap implementation</a> written in OCaml by Jean-Christophe Filliatre. There are many other great examples of simple and efficient mutable data structures that use functional programming in their APIs that are written in OCaml.</p> <blockquote> <p>Should I just use records and not bother with the discriminated union?</p> </blockquote> <p>In the case of mutable data structures, their parts are often stored contiguously in an array. This is why they are often a lot more efficient than their purely functional counterparts.</p> <blockquote> <p>Should I be doing the mutable structures in C#, and not dip into F# until I want to compare them to their purely functional counterparts?</p> </blockquote> <p>No. Do not use F# as if it were a <em>purely</em> functional programming language. The whole point of impure functional languages (and the reason they are far more popular) is that mutation is useful and should not always be avoided. Arrays and hash tables are great data structures. Mutable data structures like the ones you've listed can also be useful.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload