list=cluster [t:type] is create, cons, first, rest, is_in, is_empty,
                         equal, similar, copy

  rep=oneof[some:pair, empty:null]
  pair=struct[elem:t, rest:list[t]]

  create=proc() returns (cvt)
     return (rep$make_empty(nil))
  end create

  cons=proc(i:t,lst:list[t]) returns (cvt)
    return (rep$make_some(pair${elem:i, rest:lst}))
  end cons

  first=proc(lst:cvt) returns (t) signals (empty)
    tagcase lst
      tag some(p:pair): return (p.elem)
      tag empty       : signal empty
    end
  end first

  rest=proc(lst:cvt) returns (list[t]) signals (empty)
    tagcase lst
      tag some(p:pair): return (p.rest)
      tag empty       : signal empty
    end
  end rest

  is_in=proc(lst:cvt,i:t) returns (bool)
        where t has equal: proctype (t,t) returns (bool)
    while true do
      tagcase lst
        tag empty:        return (false)
        tag some(p:pair): if p.elem=i then return (true)
                                      else lst:=down(p.rest)
                                      end
      end
    end
  end is_in

  is_empty=proc(lst:cvt) returns (bool)
    return (rep$is_empty(lst))
  end is_empty

  elements=iter(lst:cvt) yields (t)
    tagcase lst
      tag some(p:pair): yield(p.elem)
                        for i:t in elements(p.rest) do yield(i) end
      tag empty:
    end
  end elements

  equal=proc(lst1,lst2:cvt) returns (bool)
        where t has equal:proctype (t,t) returns (bool)
    return (lst1=lst2)
  end equal

  similar=proc(lst1,lst2:cvt) returns (bool)
          where t has equal:proctype (t,t) returns (bool)
    tagcase lst1
      tag empty: return (is_empty(up(lst2)))
      tag some(p1:pair): tagcase lst2
                           tag empty: return (false)
                           tag some(p2:pair):
                               if p1.elem=p2.elem then
                                 return (similar(p1.rest,p2.rest))
                               else
                                 return (false)
                               end
                         end
    end
  end similar

  copy=proc(lst:list[t]) returns (list[t])
    return (lst)
  end copy

end list