[svn] r6017: nemerle/trunk/lib: list.n rlist.n
d
svnadmin at nemerle.org
Sun Dec 18 20:25:44 CET 2005
Log:
Introducing Random Access Lists as described by Chris Okasaki in "Purely Functional Data Structures" (1999).
Author: d
Date: Sun Dec 18 20:25:43 2005
New Revision: 6017
Added:
nemerle/trunk/lib/rlist.n
Modified:
nemerle/trunk/lib/list.n
Modified: nemerle/trunk/lib/list.n
==============================================================================
--- nemerle/trunk/lib/list.n (original)
+++ nemerle/trunk/lib/list.n Sun Dec 18 20:25:43 2005
@@ -1404,7 +1404,7 @@
/**
* Return a list of characters, which values are incremented by [step],
- * beginning with [beg], up to [end], excluding [end] itself.
+ * beginning with [beg], up/down to [end], excluding [end] itself.
*/
public Range (b : char, e : char, step = 1) : list [char] {
when (step == 0)
Added: nemerle/trunk/lib/rlist.n
==============================================================================
--- (empty file)
+++ nemerle/trunk/lib/rlist.n Sun Dec 18 20:25:43 2005
@@ -0,0 +1,199 @@
+namespace Nemerle.Collections {
+
+ [Record]
+ public class Pair ['a] {
+ public fst : 'a;
+ public snd : 'a;
+ }
+
+ public variant RList ['a] {
+ | Nil
+ | Zero { arg : RList [Pair ['a]] }
+ | One { arg1 : 'a; arg2 : RList [Pair ['a]] }
+
+ public static Empty : RList ['a] = Nil ();
+
+ public static IsEmpty (xs : RList ['a]) : bool {
+ | Nil => true
+ | _ => false
+ }
+
+ public IsEmpty () : bool {
+ IsEmpty (this)
+ }
+
+ public static Equals (xs : RList ['a], ys : RList ['a]) : bool {
+ | (Nil, Nil) => true
+ | (Zero (ps), Zero (qs)) => Equals (ps, qs)
+ | (One (x, ps), One (y, qs)) when x.Equals (y) => Equals (ps, qs)
+ | _ => false
+ }
+
+ [Nemerle.OverrideObjectEquals]
+ public Equals (ys : RList ['a]) : bool {
+ Equals (this, ys)
+ }
+
+ public static Cons (x : 'a, xs : RList ['a]) : RList ['a] {
+ match (xs) {
+ | Nil => One (x, Nil ())
+ | Zero (ps) => One (x, ps)
+ | One (y, ps) => Zero (RList [Pair ['a]].Cons (Pair (x, y), ps))
+ }
+ }
+
+ public Cons (x : 'a) : RList ['a] {
+ Cons (x, this)
+ }
+
+ public static UnCons (xs : RList ['a]) : 'a * RList ['a] {
+ | Nil => throw System.Exception ("Empty")
+ | One (x, Nil ()) => (x, Nil ())
+ | One (x, ps) => (x, Zero (ps))
+ | Zero (ps) => def ((x, y), ps') = RList [Pair ['a]].UnCons (ps);
+ (x, One (y, ps'))
+ }
+
+ public UnCons () : 'a * RList ['a] {
+ UnCons (this)
+ }
+
+ public static Head (xs : RList ['a]) : 'a {
+ | Nil => throw System.Exception ("Empty")
+ | One (x, _) => x
+ | Zero (ps) => def (x, _) = RList [Pair ['a]].Head (ps); x
+ }
+
+ public Head () : 'a {
+ Head (this)
+ }
+
+ public static Hd (xs : RList ['a]) : 'a {
+ Head (xs)
+ }
+
+ public Hd () : 'a {
+ this.Head ()
+ }
+
+ public static Tail (xs : RList ['a]) : RList ['a] {
+ def (_, xs') = UnCons (xs);
+ xs'
+ }
+
+ public Tail () : RList ['a] {
+ Tail (this)
+ }
+
+ public static Tl (xs : RList ['a]) : RList ['a] {
+ Tail (xs)
+ }
+
+ public Tl () : RList ['a] {
+ this.Tail ()
+ }
+
+ static _Length (xs : RList ['a], pow = 0.0, count = 0.0) : int {
+ match (xs) {
+ | Nil => count :> int
+ | Zero (ps) => RList [Pair ['a]]._Length (ps, pow + 1.0, count)
+ | One (_, ps) => _Length (Zero (ps), pow, count + System.Math.Pow (2, pow))
+ }
+ }
+
+ public Length : int {
+ get {
+ _Length (this)
+ }
+ }
+
+ public static Nth (xs : RList ['a], i : int) : 'a {
+ match (xs) {
+ | Nil => throw System.Exception ("Subscript")
+ | One (x, ps) => if (i == 0) x else Nth (Zero (ps), i - 1)
+ | Zero (ps) => def (x, y) = RList [Pair ['a]].Nth (ps, i / 2);
+ if (i % 2 == 0) x else y
+ }
+ }
+
+ public Nth (i : int) : 'a {
+ Nth (this, i)
+ }
+
+ static FUpdate (f : 'a -> 'a, i : int, xs : RList ['a]) : RList ['a] {
+ match (xs) {
+ | Nil => throw System.Exception ("Subscript")
+ | One (x, ps) => if (i == 0) One (f (x), ps) else Cons (x, FUpdate (f, i - 1, Zero (ps)))
+ | Zero (ps) => def f' (p) { match (p) { | Pair where (fst = x, snd = y) => if (i % 2 == 0) Pair (f (x), y) else Pair (x, f (y)) } }
+ Zero (RList [Pair ['a]].FUpdate (f', i / 2, ps))
+ }
+ }
+
+ _FUpdate (f : 'a -> 'a, i : int) : RList ['a] {
+ FUpdate (f, i, this)
+ }
+
+ public static Update (i : int, y : 'a, xs : RList ['a]) : RList ['a] {
+ FUpdate (fun (_) { y }, i, xs)
+ }
+
+ public Update (i : int, y : 'a) : RList ['a] {
+ Update (i, y, this)
+ }
+
+ public static FoldLeft ['b] (xs : RList ['a], acc : 'b, f : 'a * 'b -> 'b) : 'b {
+ match (xs) {
+ | Nil => acc
+ | Zero (ps) => def f' (a, b) { f (a.snd, f (a.fst, b)) }
+ RList [Pair ['a]].FoldLeft (ps, acc, f')
+ | One (x, ps) => FoldLeft (Zero (ps), f (x, acc), f)
+ }
+ }
+
+ public FoldLeft ['b] (acc : 'b, f : 'a * 'b -> 'b) : 'b {
+ FoldLeft (this, acc, f)
+ }
+
+ public static FoldRight ['b] (xs : RList ['a], acc : 'b, f : 'a * 'b -> 'b) : 'b {
+ match (xs) {
+ | Nil => acc
+ | Zero (ps) => def f' (a, b) { f (a.fst, f (a.snd, b)) }
+ RList [Pair ['a]].FoldRight (ps, acc, f')
+ | One (x, ps) => f (x, FoldRight (Zero (ps), acc, f))
+ }
+ }
+
+ public FoldRight ['b] (acc : 'b, f : 'a * 'b -> 'b) : 'b {
+ FoldRight (this, acc, f)
+ }
+
+ public static Rev (xs : RList ['a]) : RList ['a] {
+ FoldLeft (xs, Nil (), Cons)
+ }
+
+ public Rev () : RList ['a] {
+ Rev (this)
+ }
+
+ public static ToList (xs : RList ['a]) : list ['a] {
+ Nemerle.Collections.List.Rev (FoldLeft (xs, [], fun (x, y) { x :: y }))
+ }
+
+ public ToList () : list ['a] {
+ ToList (this)
+ }
+
+ public static ToString (xs : RList ['a]) : string {
+ xs.ToString ()
+ }
+
+ public override ToString () : string {
+ match (this) {
+ | Nil => "Nil"
+ | One (x, ps) => "One (" + x.ToString () + ", " + ps.ToString () + ")"
+ | Zero (ps) => "Zero (" + ps.ToString () + ")"
+ }
+ }
+ }
+}
+
More information about the svn
mailing list