list a ::= Nil | Cons a (list a);

;;

lid l = case l of Nil -> l; Cons x xs -> l end;
  {abstract identity on 4}


foldr f asl b
   = case asl of
        Nil -> lid b;
        Cons a as -> d_68_LL f b (lid a) as
     end;

d_68_LL f b x y
   = f x (foldr f y b);

foldr f a l 
  = case l of
       Nil -> lid a; 
       Cons x xs -> f x (foldr f a xs)
    end;
{
map f
  = foldr (\a b -> Cons (f a) b) Nil;

sum
  = foldr (\x y -> x + y) 0;

length xs
  = sum (map (\a -> 1) xs);

lengthRec l
  = case l of
       Nil -> 0;
       Cons x xs -> 1 + lengthRec xs
    end;
}
append xl yl
   = case xl of
        Nil -> yl;
        Cons x xs -> Cons x (append xs yl)
     end;

concat = foldr append Nil;