# An implementation of lists using tuples (Lisp style).
#
# Of course Hindley Milner type inference has trouble with this!
#
# Relies on a primitive: isTuple :: a -> Bool
#
# Author: Bernie Pope
# Date:   10 October 2004

emptyList = nil;

isEmpty = compose not isTuple;

cons = \x -> \list -> (x, list);

hd = fst;

tl = snd;

fromTupList 
   = \list -> 
        ite (isEmpty list) 
            [] 
            (Cons (hd list) (fromTupList (tl list)));

toTupList   
   = \list -> 
        ite (null list) 
            emptyList 
            (head list, toTupList (tail list));

unit = \x -> (x, emptyList);

rev 
   = !list -> 
        ite (isEmpty list) 
            emptyList 
            (join (rev (tl list)) (unit (hd list)));

join 
   = !list1 -> !list2 -> 
        ite (isEmpty list1) 
            list2 
            (hd list1, join (tl list1) list2);