Databases
StackOverflow2013
Postsdbo
POWhat's the right way to do mutable data structures (e.g., skip lists, splay trees) in F#?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhat's the right way to do mutable data structures (e.g., skip lists, splay trees) in F#?
    primarykey
    data
    text
    <p>What's a good way to implement mutable data structures in F#? 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. I know that I “should” use finger trees to get splay tree functionality in a functional language, and that I should do something with laziness to get skip-list functionality, etc. , but I want to get the basics nailed down before I try playing with purely functional implementations.</p> <p>There are lots of examples of how to do functional data structures in F#, but there isn’t much on how to do mutable data structures, so I started by fixing up the doubly linked list <a href="http://cs.hubfs.net/forums/permalink/7895/7896/ShowThread.aspx#7896" rel="noreferrer">here</a> into something that allows inserts and deletes anywhere. My plan is to turn this into a skip list, and then use a similar structure (discriminated union of a record) for the tree structures I want to implement. Before I start on something more substantial, is there a better way to do mutable structures like this in F#? Should I just use records and not bother with the discriminated union? Should I use a class instead? Is this question "not even wrong"? 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> <p>And, if a DU of records is what I want, could I have written the code below better or more idiomatically? It seems like there's a lot of redundancy here, but I'm not sure how to get rid of it.</p> <pre><code>module DoublyLinkedList = type 'a ll = | None | Node of 'a ll_node and 'a ll_node = { mutable Prev: 'a ll; Element : 'a ; mutable Next: 'a ll; } let insert x l = match l with | None -&gt; Node({ Prev=None; Element=x; Next=None }) | Node(node) -&gt; match node.Prev with | None -&gt; let new_node = { Prev=None; Element=x; Next=Node(node)} node.Prev &lt;- Node(new_node) Node(new_node) | Node(prev_node) -&gt; let new_node = { Prev=node.Prev; Element=x; Next=Node(node)} node.Prev &lt;- Node(new_node) prev_node.Next &lt;- Node(new_node) Node(prev_node) let rec nth n l = match n, l with | _,None -&gt; None | _,Node(node) when n &gt; 0 -&gt; nth (n-1) node.Next | _,Node(node) when n &lt; 0 -&gt; nth (n+1) node.Prev | _,Node(node) -&gt; Node(node) //hopefully only when n = 0 :-) let rec printLinkedList head = match head with | None -&gt; () | Node(x) -&gt; let prev = match x.Prev with | None -&gt; "-" | Node(y) -&gt; y.Element.ToString() let cur = x.Element.ToString() let next = match x.Next with | None -&gt; "-" | Node(y) -&gt; y.Element.ToString() printfn "%s, &lt;- %s -&gt; %s" prev cur next printLinkedList x.Next </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USdan
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POWhat's the right way to do mutable data structures (e.g., skip lists, splay trees) in F#?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POWhat's the right way to do mutable data structures (e.g., skip lists, splay trees) in F#?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POWhat's the right way to do mutable data structures (e.g., skip lists, splay trees) in F#?
      1. USstakx
      1. VTFavorite
    1. COSee also http://cs.hubfs.net/forums/thread/14029.aspx
      singulars
      1. POWhat's the right way to do mutable data structures (e.g., skip lists, splay trees) in F#?
      1. USBrian
    2. COYou know, apart from hashtables and linked lists, I personally find the immutable data structures much easier to implement than the mutable counterparts -- especially trees. Your mileage may vary.
      singulars
      1. POWhat's the right way to do mutable data structures (e.g., skip lists, splay trees) in F#?
      1. USJuliet
    3. COJuliet: what about arrays? Surely those are easier to implement mutably.
      singulars
      1. POWhat's the right way to do mutable data structures (e.g., skip lists, splay trees) in F#?
      1. USGabe
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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