Back to Questions
2.4k
views10
comments
Doubly linked list via circular program
f#

Has anyone managed to create a doubly linked list in F# using techniques such as are described in [link:www.csse.monash.edu.au] ?

Thanks

.

I tried this just now and came up with the following. I'm sure there is a more refined technique I can use, but this was a great learning exercise for me! This isn't perfect due to the mutable field in the node, in particular in the article you linked they use a lazy evaluation of the node, but there might be a way to eliminate it. Maybe someone smarter than me can figure it out :)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

type dbl_list = 
   | None
   | Node of dbl_node
and dbl_node = {
   mutable Prev:dbl_list;
   Element:int;
   Next:dbl_list;
}

let dbl_cons x list = 
   match list with 
   | None -> Node({ Prev=None; Element=x; Next=None })
   | Node(node) -> 
         let new_node = { Prev=None; Element=x; Next=Node(node) }
         node.Prev <- Node(new_node)
         Node(new_node)

let rec print_dbl_list head = 
   match head with
   | None -> ()
   | Node(x) -> 
         let prev = match x.Prev with
                           | None -> "--"
                           | Node(y) -> y.Element.ToString()
         let cur = x.Element.ToString()
         let next = match x.Next with 
                           | None -> "--"
                           | Node(y) -> y.Element.ToString()
         printfn "Prev: %s, Cur: %s, Next: %s" prev cur next
         print_dbl_list x.Next

let my_dbl_list = None |> dbl_cons 1 |> dbl_cons 2 |> dbl_cons 3 |> dbl_cons 4
print_dbl_list my_dbl_list

Output is:
Prev: --, Cur: 4, Next: 3
Prev: 4 , Cur: 3, Next: 2
Prev: 3 , Cur: 2, Next: 1
Prev: 2 , Cur: 1, Next: --

By on 11/21/2008 11:40 AM ()

The mutable field here has been bugging the daylights out of me, and I almost gave up on trying to find a way to get O(1) inserts while not making the list destructive. I finally hit on the winning idea, but it comes at a tradeoff: Namely, space. Typically a doubly linked list uses O(n) space (3 fields per element of the list), and this approach uses O(n^2) space. Instead of keeping a simple reference to the previous object and a reference to the next object, it keeps an entire list for both the next and an entire list for the previous. So conceptually if you have this list:

A -> B -> C -> D

then the nodes are as follows:
A : Next = [ B; C; D ] Prev = []
B : Next = [ C; D ] Prev = [ A ]
C : Next = [ D ] Prev = [ B; A ]
D : Next = [] Prev = [ C; B; A ]

Notice that the Prev list is in reverse. The advantage to this approach is that when inserting at an arbitrary location, you can easily construct the new prev and next values by simply manipulating the lists.

I think it's probably impossible to achieve O(1) insertions using a recursive data structure, and as such the techniques in the link you mentioned I don't think are going to be practical. I'd love for someone to prove me wrong, because it looks like a neat technique, but conceptually I just can't see how it's possible to implement a purely function doubly linked list using a recursive data structure in any language and have inserts be O(1).

Anyway, here's the code for my new attempt. I wrote it as a discriminated union with member functions, since I'm not familiar with module syntax yet (still only on chapter 6 of Expert F#)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

type 'a DblList = 
    | None
    | Some of ('a list * 'a * 'a list)
    member x.Next() = 
        match x with
        | None -> None
        | Some(_, _, []) -> None
        | Some(prev, cur, next::tail) -> Some(cur::prev, next, tail)
    member x.Prev() = 
        match x with
        | None -> None
        | Some([], _, _) -> None
        | Some(prev::prevtail, cur, next) -> Some(prevtail, prev, cur::next)
    member x.Length() = 
        match x with
        | None -> 0
        | Some(_, _, next) -> 1 + List.length next
    member x.TotalLength() = 
        match x with
        | None -> 0
        | Some(prev, _, next) -> 1 + List.length next + List.length prev
    member x.InsertBefore(value:'a) = 
        match x with
        | None -> Some([], value, [])
        | Some(prev, cur, next) -> Some(prev, value, cur::next)
    member x.InsertAfter(value:'a) = 
        match x with
        | None -> Some([], value, [])
        | Some(prev, cur, next) -> Some(cur::prev, value, next)
    member x.ScanToHead() = 
        match x with 
        | None -> None
        | Some([],_,_) -> x
        | Some(_,_,_) -> x.Prev().ScanToHead()
    override x.ToString() = 
        match x with
        | None -> String.Empty
        | Some(_, v, []) -> v.ToString() 
        | Some(_, v, _) -> v.ToString() + ", " + x.Next().ToString()
By on 11/22/2008 8:19 PM ()

Good attempt. The problem with this solution though is not that it uses O(n^2): it doesn't, it only uses O(n) as expected. F# lists are linked lists not arrays so you do not copy the old list when you cons a new element onto the front. So each call to your insert functions is reusing the (singly-linked) lists from the old doubly-linked list and not reallocating them. Hence making the insert memory performance O(1), which is expected.

The problem with this solution is when traversing the list. Your Prev and Next operations do allocate memory, which is bad. Each Prev/Next operation allocates a Some cell and a (::) cell, making their memory allocation cost O(1), not O(0) as you'd expect. So when you iterate through this doubly-linked list you are actually consuming memory. This is not actually a huge problem because, provided that you don't hold on to the lists from old iterations, this memory will churn quickly through the GC. But it is still not a desirable situation.

Generally to implement a circular data structure like a doubly-linked list you need one of two things: mutation or laziness. Your first solution uses mutation. Here is a solution that uses laziness.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

let force (x:Lazy<_>) = x.Force()


let rec fix f = f (lazy (force (fix f)))

type DblList<'a> = Lazy<Cell<'a> >


and Cell<'a> = DEmpty | DJoin of DList<'a> * 'a * DList<'a>

let empty () = lazy DEmpty


let join prev x next = lazy DJoin (prev, x, next);

let before x dl =


  match force dl with


  | DEmpty -> join (empty ()) x (empty ())


  | DJoin (prev, y, next) -> fix (fun curr -> join prev x (join curr y next))

When inserting an element into the list it uses the fix-point combinator to build the current node of the list in terms of itself. If F# had special "let rec" syntax for lazy values then you might imagine this line being written

1

let rec curr = join prev x (join curr y next))

The fix function is just like a poorman's "let rec".

By on 11/22/2008 11:08 PM ()

The problem with this solution is when traversing the list. Your Prev and Next operations do allocate memory, which is bad. Each Prev/Next operation allocates a Some cell and a (::) cell, making their memory allocation cost O(1), not O(0) as you'd expect. So when you iterate through this doubly-linked list you are actually consuming memory. This is not actually a huge problem because, provided that you don't hold on to the lists from old iterations, this memory will churn quickly through the GC. But it is still not a desirable situation.

Hi, I have a question. Using the lazy construct, don't we also have some memory overhead as well in the form of lamba(or is it thunk) ? I tried to expand based on your example. Please comment as I am still learning 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

let force (x:Lazy<_>) = x.Force()
let rec fix f = f(lazy (force (fix f)))

type DList<'a> = Lazy<Cell<'a> >
and Cell<'a> = DEmpty | DJoin of DList<'a> * 'a * DList<'a>

let empty () = lazy DEmpty
let join prev x next = lazy DJoin (prev, x, next);

let prev dl =
  match force dl with
  | DEmpty -> failwith "empty list"
  | DJoin (prev, y, next) -> 
    match force prev with
    | DEmpty -> failwith "already at head"
    | DJoin (prev, y, next) -> join prev y dl
  
let next dl = 
  match force dl with
  | DEmpty -> failwith "empty list"
  | DJoin (prev, y, next) ->
    match force next with
    | DEmpty -> failwith "already at end"
    | DJoin (prev, y, next) -> join dl y next
    
let before x dl =
  match force dl with
  | DEmpty -> join (empty ()) x (empty ())
  | DJoin (prev, y, next) -> fix (fun curr -> join prev x (join curr y next))

let after x dl =
  match force dl with
  | DEmpty -> join (empty ()) x (empty ())
  | DJoin (_prev, y, _next) -> next (fix (fun curr -> join _prev y (join curr x _next)))

  
let elem dl =
  match force dl with
  | DEmpty -> failwith  "empty list"
  | DJoin (prev, y, next) -> y
  

  
let rec fst dl =
  match force dl with
  | DEmpty -> dl
  | DJoin (p, y, n) -> 
    match force p with
    | DEmpty -> dl
    | _ -> fst (prev dl)

let rec last dl =
  match force dl with
  | DEmpty -> failwith "empty list"
  | DJoin (p, y, n) -> 
    match force n with
    | DEmpty -> dl
    | DJoin(p',_,n') -> last n

let length dl =
  let rec _lenn dl acc =
    match force dl with
      |DEmpty -> acc
      |DJoin (prev, y, next) -> _lenn next (acc + 1) 
      
  let rec _lenp dl acc =
    match force dl with
      |DEmpty -> acc
      |DJoin (prev, y, next) -> _lenp prev (acc + 1) 
  
  match force dl with
  | DEmpty -> 0
  | DJoin(prev, y, next) -> _lenp prev 0 + _lenn next 0 + 1
  

let pop dl =
  match force dl with
  | DEmpty -> failwith "empty list"
  | DJoin(prev, y, next) -> 
    match force prev with
    |DEmpty -> (y, next);
    |DJoin(p,x,n) -> (y, join p x next);
By on 12/1/2008 12:49 AM ()

Yes, the lazy construct forms thunks which are only evaluated once. If you want to track memory usage you can count the number of times a data constructor (DEmpty or DJoin) is called. It is easy in this case because we already have helper functions to build these data values so you can just stick a counter increment in there. E.g.,

1
2

let callCount = ref 0
let join prev x next = incr callCount; lazy DJoin (prev, x, next)

Then read callCount after you have run some test.

I'm not sure what your prev and next functions are meant to do, but if they are meant to advance forward and backward through the list then I would have them work like this (where they return DEmpty if you go off the end of the list).

1
2
3
4
5
6
7
8
9
10

let next dl =


  match force dl with


  | DEmpty -> lazy failwith "empty list"


  | DJoin (_, _, next) -> next

after I would write:

1
2
3
4
5
6
7
8
9
10

let after x dl =


  match force dl with


  | DEmpty -> join (empty ()) x (empty ())


  | DJoin (prev, y, next) -> fix (fun curr -> join (join prev y curr) x next)

fst/last are ok. They are doing a redundant pattern match on each recursion though (e.g., on the recursive call to last, n is already known to be DJoin, but it is tested against DEmpty when it recurses (and I don't think the compiler will optimize this for you)). So I would prefer to write fst as 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

let first dl =


  let rec first' curr last =


    match force curr with


    | DEmpty -> last


    | DJoin (prev, _, _) -> first' prev curr


  first' dl (lazy failwith "empty list")
By on 12/1/2008 8:29 PM ()

thanks.

At first, I wrote prev/next as what you have shown but some how, I cannot do the reverse, i.e. I cannot satisfy the following :

Assert(next (prev dl) == dl)

Which is why I wrote it like it is now and also my question of even I am scanning through the list, in order to maintain the above, I need to reconstruct another thunk. May be I have missed something though.

It seems that forcing laziness into a non-lazy language is quite complex.

By on 12/2/2008 12:24 AM ()

I was hoping that I woke up in time to correct the comment about the O(n^2) space, because I also realized that it's indeed O(n) space a little while later :P The code fragment you've given is a little over my head, but maybe in a few weeks or months after I learn more about F# it will make sense. Thanks!

By on 11/23/2008 7:48 AM ()

The code shouldn't be all that hard given that you know already the basics of F#: disciminated union data types, pattern matching, etc. If you don't already know how the Lazy type works in F# then that's something you should learn first. After that don't worry about how the fix function works -- that is hard. Instead just appreciate how the fix function is used. If you see a line

1

fix (fun x -> ... x ...)

and you squint and tilt your head it actually looks like

1

let rec x = ... x ...

so intuitively you are just defining a value in terms of itself. As you commonly do for functions.

By on 11/23/2008 7:31 PM ()

While I think about the "fix" function here is the solution I reached over the weekend after looking at pg 220 of "Expert F#":type tdbllist =
| Nil
| Nod of tdbllist*int*tdbllist
| Delay of Lazy<tdbllist>

let rec mkdbllist (lst:tdbllist) x =
match x with
| h::t -> let rec n() = let m = Delay( lazy( mkdbllist (n()) t))
Nod(lst, h, m)
n()
| [] -> Nil

let y = mkdbllist Nil [1;2;3;4;5]

Graeme

By on 11/24/2008 3:09 AM ()

Here is a print function:let rec printright node prev =
match node with
| Nod(l,i,r) -> printf "pr item %d\n" i
printright r node
| Delay(d) -> printright (d.Force()) prev
| _ -> prev

Thanks for the feedback

Graeme

By on 11/24/2008 3:11 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