All entries for Sunday 01 October 2006

October 01, 2006

Circular, doubly–linked list

Follow-up to Loopy linked lists from codeMonkey.Weblog();

After taking considerable inspiration from a Haskell implementation , I managed to write some Nemerle code that creates a circular, doubly-linked list, without using any mutable variables.
It is not as elegant as the Haskell version because I had to use class fields to get lazy access to variables not yet assigned. Translating lines like:

mkDList xs = let (first,last) = go last xs first
             in  first

into Nemerle is tricky, even with the “lazy” macro.

So here’s the code…

#pragma indent

using System
using Nemerle

[Record] struct Node[T]
    public Prev : LazyValue[Node[T]]
    public Value : T
    public Next : LazyValue[Node[T]]

class LoopList[T]
    private first : Node[T]
    private last : Node[T]

    private this(items : list[T])
        def go = Go(lazy(last), items, lazy(first))
        (first,last) = (go.me, go.last)

    private class Go
        private rest : LazyValue[Node[T]]
        public me : LazyValue[Node[T]]
        public last : LazyValue[Node[T]]

        public this(prev : LazyValue[Node[T]], items : list[T], next : LazyValue[Node[T]])
            match((prev, items, next))
                | (prev, [], next) =>
                    (me, last) = (next, prev)

                | (prev, x::xs, next) =>
                    me = lazy(Node(prev, x, rest))
                    def go = Go(me, xs, next)
                    (rest, last) = (go.me, go.last)

    public static Create(xs : list[T]) : Node[T]
        LoopList(xs).first

// Test Code

mutable n = LoopList.Create([1,2,3,4])

Console.WriteLine("Forwards")
repeat(10)
    Console.Write($"$(n.Value) ")
    n = n.Next

n = n.Prev
Console.WriteLine()
Console.WriteLine("and back again")
repeat(10)
    Console.Write($"$(n.Value) ")
    n = n.Prev

// Output
/*
Forwards
1 2 3 4 1 2 3 4 1 2
and back again
2 1 4 3 2 1 4 3 2 1
*/

I’m planning to use this in my 3rd year project. The Weiler-Atherton algorithm requires a CDDL.


Google Ads

Search this blog

Most recent comments

  • I scratched my eye while i was holding some kind of plastic packaging.. Anyways the corner of the pl… by Ercan on this entry
  • About a year ago my contacts that i was wearing, i guess were fautly, because shortly after they wer… by Jon on this entry
  • I got shower gel in my eye 4 and a half days ago, and becasue i rubbed my eyes a lot, i have scratch… by Chris on this entry
  • This website may help http://www.webmd.com/eye–health/tc/Eye–Injuries–Home–Treatment by S on this entry
  • I somehow got dirt, or debris in my eye. The terrible pain sent me in a tailspin. I was afraid of sa… by Bobbi on this entry

Tags

October 2006

Mo Tu We Th Fr Sa Su
Sep |  Today  | Nov
                  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               

Galleries

Blog archive

Loading…
Not signed in
Sign in

Powered by BlogBuilder
© MMXXI