-- Copyright 1993-1998, by the Cecil Project
-- Department of Computer Science and Engineering, University of Washington
-- See the LICENSE file for license information.

(--
`i_list's are immutable lists implemented with `i_cons' and `i_nil' and
parameterized with the type of elements they keep.  Once created,
fields of `i_cons' cannot be changed.  This makes it possible to have
the co-variance property for its type parameter.
--)


----------------------
-- i_list: parent of i_cons and i_nil
--
abstract object i_list[`T] isa list[T];
extend type i_list[`T] subtypes i_list[`S >= T];

signature first(i_list[`T]):T;
signature rest(i_list[`T]):i_list[T];
signature do(i_list[`T], closure:&(elm:T):void):void;
method length(l@:i_list[`T]):int {
    let var len:int := 0;
    do(l, &(elm:T){ len := len+1 });
    len }

----------------------
-- i_cons: the immutable cons cell
--
template object i_cons[`T] isa i_list[T];
extend type i_cons[`T] subtypes i_cons[`S >= T];

field first(@:i_cons[`T]):T;
field rest(@:i_cons[`T]):i_list[T];

-- cons an element onto a list
method i_cons(elm:`T, l:i_list[`T]):i_list[T] {
    concrete object isa i_cons[T] { first := elm, rest := l } }

method do(l@:i_cons[`T], closure:&(elm:T):void):void {
    eval(closure, l.first);
    do(l.rest, closure);
}

----------------------
-- i_nil is an immutable list of "none" (i.e., bottom), and so, by
-- covariance, of anything else, too
-- (for a mutable list, i_nil would have to be parameterized just like i_cons)
--
concrete object i_nil isa i_list[none];

method first(@:i_nil):none { error("accessing first element of empty list") }
method rest(@:i_nil):none { error("accessing rest of empty list") }
method do(@:i_nil, closure:&(elm:`T):void):void { }


-- if we wanted a list of a specific type (useful for mutable lists), we'd
-- specify that type explicitly
--
method new_i_list[`T](elm:T):i_list[T] {
    concrete object isa i_cons[T] { first := elm, rest := i_nil } }

-- for example
let num_list:i_list[num] := new_i_list[num](5);