All entries for Sunday 01 October 2006
October 01, 2006
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.