F# Hiding stuff?

Question

Sry for the bad headline could find the right words.

At the moment I'm trying to make some basic data structures that F# can use in any situation the first one is a Double linked list.

My question is not as much how to get it implemented, but rather if there is a why to hide the ugliness of the data structure. short form, i have something that as node at could look like

type Node<'N> = 
  | (node<'N> ref, 'N, node<'N>)
  | Empty

and to analyse this when we have more then three items of the list is rather error prone. So is there a way that i can make the "look" the user of the library sees so it could look more like a List from the .NET. I'm asking for a way that doesn't rely on an already established data type, and one that not return a string look ( " ... " )

Answer 1

You can wrap your F# type in a class and keep the actual F# representation hidden. For example, if you wanted a super simple mutable list, you could do something like this:

type private MyListNode<'T> = 
  | Empty 
  | Cons of 'T * MyListNode<'T>

type MyList<'T>() =
  let mutable nodes = Empty
  member x.Prepend(el) = nodes <- Cons(el, nodes)
  member x.ToArray() = 
    let rec loop el = seq {
      match el with 
      | Empty -> ()
      | Cons(x, xs) -> 
          yield x
          yield! loop xs }
    loop nodes |> Array.ofSeq

The C# user can work with MyList, which is ordinary class with Prepend and ToArray methods. The MyListNode type is private (hidden inside your F# library) and C# users will never see it.

Answer 2

This is not an answer to the question, but to the comments, because what I'm going to say requires diagrams and so it won't work in comments.

kam wrote:

But my Double Linked List are running in O(1) and if we assume that it is only the data and not the "pointers" that are immutable then you could still copy the whole list in O(1) time since the only thing you do when adding or deleting are changing or make a pointer (ref cell) to the old list then we still have that we have a copy of the old list without copying every single element again.

If you try to do that, you will find that with a doubly-linked list, you can't, in fact, preserve the old list pointers. Here's why.

With a singly-linked list, you can prepend to a list in O(1) time while maintaining any pointers to the old list intact. Here's an example:

Old list containing three items:

New list after prepending a new head:

Note how the reference from the other code has stayed intact. The old list, referenced by the other code, is ["Item 1"; "Item 2"; "Item 3"]. The new list is ["New head item"; "Item 1"; "Item 2"; "Item 3"]. But the reference held by a different part of the code still points to a well-formed list. The "well-formed" part is important, as you're about to see.

With a doubly-linked list, things get more complicated — and it turns out that it is not possible to maintain immutability and have O(1) time. First let's look at the old list containing three items:

This is a well-formed doubly-linked list. It obeys the following properties that all well-formed doubly-linked lists should obey:

1. All nodes have a Fwd and Back pointer.
2. All nodes but the head node have a valid (non-null) Back pointer. Only the head node's Back pointer is null.
3. All nodes but the tail node have a valid (non-null) Fwd pointer. Only the tail node's Fwd pointer is null.
4. From any node that isn't the tail, going forward and then back should bring you back to the same node you started at.
5. From any node that isn't the head, going back and then forward should bring you back to the same node you started at.

Now, how do we add a new head item while still making sure that the reference from the other code continues to point to a well-formed doubly-linked list?

Here's a first attempt. We add the new head item, adjust its Fwd pointer to point to the "old" head node, and rewrite that node's Back pointer to point to the new head node:

This is still a well-formed list, as you can easily verify. All five properties still hold true for every node. But wait! The reference from some other part of the code has had its list changed out from under it! Where before it was pointing to a list of three items, now it's pointing to the second item of a list of four items! If that other code is only iterating forwards, it won't notice a change. But the minute it tries to iterate backward, it will notice that there's a new head item that wasn't there before! We have broken the immutability promise. Immutability is a guarantee to other code that consumes our data structure that "If you have a reference to this data structure, the data you see will never change out from under you." And we just broke that promise: the old code used to see the list ["Item 1"; "Item 2"; "Item 3"], and now it sees the list ["New head item"; "Item 1"; "Item 2"; "Item 3"].

Okay, then. Are there ways to keep that promise, and not change what the other code sees? Well, we could try not rewriting that old head node; that way the old code still sees a doubly-linked list of three items, and everyone's happy, right? Well, let's see what it would look like if we did it that way:

Great: the other code still sees the exact same doubly-linked list that it used to see, and there's no way to get from the old list to the new head node. So any part of that other code that tries to go backwards from the head of the list will find that the head still goes to null, like it should. But wait: what about the five properties of a well-formed list? Well, it turns out we've violated property #4: from the head node, going forward and then going back ends up at a null pointer, not the node we started at. So we no longer have a well-formed list: bummer.

Okay, so that approach won't work. What else could we try. Well... hey! I have an idea! Let's just make a copy of the old head node, and adjust the copy while we leave the old head node alone! That's still O(1) since we know we're only copying one node. Then the other code sees exactly what it used to see, a list of three items, but the new list has four items. Brilliant! Just what we want, right? Well, let's look at it:

Okay, does this work? Well, the other code has a reference to the old, unchanged head node, so that's fine: it can't ever accidentally see the new data, so it still continues to see exactly what it used to have, a list of three items. Good. And from the new head node, we can go forward and back and end up where we started, so that's good... but wait... no, there's still a problem. From the copy of item 1 node, going forward and then back takes us to the old "item 1" node, not to the "copy of item 1" node. So we have still violated the properties of well-formed lists, and this list isn't well-formed either.

There's an answer to that one, too: copy the node with item 2 in it. I'm getting tired of drawing diagrams and this answer is getting long, so I'll let you work that one out for yourself — but you'll quickly see that then, the node with the copy of item 2 has the same problem as before: going forward and back takes you to the "old" item 2. (Or else you've adjusted the "old" item 2 node, and thereby broken the immutability promise since the other code can now see the "new" data via some series of Fwd and/or Back operations).

But there's a solution to that one, too: just copy item 3 as well. I won't draw that diagram either, but you can work it out for yourself. And you'll find that once you've copied items 1, 2, and 3 into the new list, you've managed to satisfy both the immutability promise, and all the properties of well-formed lists. The other code still sees the untouched old list, and the new list has four items in it. The only problem is, you had to copy every item in the list — an O(N) operation, by definition — in order to achieve this result.

Summary: Singly-linked lists have three properties:

1. You can prepend items in O(1) time.
2. Other code that had a reference to the old list still sees the same data after your prepend operation.
3. The old list and the new list are both well-formed.

With doubly-linked lists, however, you only get to have two of those three properties. You can have an O(1) prepend operation and maintain well-formed lists, but then any other code will see the list data change. Or you could have O(1) prepend and still have the other code see the same data it used to, but then your lists will no longer be well-formed. Or, by copying every node in the list, you can let the other code still see the same data it used to, AND your new list will be well-formed — but you had to do an O(N) operation in order to achieve this result.

This is why I said that it's not possible to have an immutable doubly-linked list with O(1) operations.