It cannot be directly tied to functional programming, but nothing compares alliances in the design and implementation of data structures. Let's compare two equivalent code snippets:
F #:
type 'a stack = Cons of' a * stack | Nil
let rec to_seq = function
| Nil -> Seq.empty;
| Cons (hd, tl) -> seq {yield hd; yield! to_seq tl}
let rec append xy =
match x with
| Nil -> y
| Cons (hd, tl) -> Cons (hd, append tl y)
let x = Cons (1, Cons (2, Cons (3, Cons (4, Nil))))
let y = Cons (5, Cons (6, Cons (7, Cons (8, Nil))))
let z = append xy
to_seq z |> Seq.iter (fun x -> printfn "% i" x)
Java:
interface IStack<T> extends Iterable<T> { IStack<T> Push(T value); IStack<T> Pop(); T Peek(); boolean IsEmpty(); } final class EmptyStack<T> implements IStack<T> { public boolean IsEmpty() { return true; } public IStack<T> Push(T value) { return Stack.cons(value, this); } public IStack<T> Pop() { throw new Error("Empty Stack"); } public T Peek() { throw new Error("Empty Stack"); } public java.util.Iterator<T> iterator() { return new java.util.Iterator<T>() { public boolean hasNext() { return false; } public T next() { return null; } public void remove() { } }; } } final class Stack<T> implements IStack<T> { public static <T> IStack<T> cons(T hd, IStack<T> tl) { return new Stack<T>(hd, tl); } public static <T> IStack<T> append(IStack<T> x, IStack<T> y) { return x.IsEmpty() ? y : new Stack(x.Peek(), append(x.Pop(), y)); } private final T hd; private final IStack<T> tl; private Stack(T hd, IStack<T> tl) { this.hd = hd; this.tl = tl; } public IStack<T> Push(T value) { return new <T> Stack(value, this); } public IStack<T> Pop() { return this.tl; } public T Peek() { return this.hd; } public boolean IsEmpty() { return false; } public java.util.Iterator<T> iterator() { final IStack<T> outer = this; return new java.util.Iterator<T>() { private IStack<T> current = outer; public boolean hasNext() { return !current.IsEmpty(); } public T next() { T hd = current.Peek(); current = current.Pop(); return hd; } public void remove() { } }; } } public class Main { public static void main(String[] args) { IStack<Integer> x = Stack.cons(1, Stack.cons(2, Stack.cons(3, Stack.cons(4, new EmptyStack())))); IStack<Integer> y = Stack.cons(5, Stack.cons(6, Stack.cons(7, Stack.cons(8, new EmptyStack())))); IStack<Integer> z = Stack.append(x, y); for (Integer num : z) { System.out.printf("%s ", num); } } }
Juliet Jun 16 '09 at 20:03 2009-06-16 20:03
source share