MODULE List;

(* Procedures for manipulating lists *)

(* A value "l" is a list if "l" is either NIL or a 
   pair whose CDR is a list. A value "l" is a proper 
   list if "l" is a list other than NIL. *)

PROC res := Member(x, l) IS 
  DO l # NIL AND x # CAR(l) -> l := CDR(l) OD; 
  IF l = NIL -> res := NIL | res := x FI 
END;

(* Returns "x" if "x" appears as a top-level element 
   of the list "l", and "NIL" otherwise. *)

PROC res := Length(l) IS 
  res := 0; 
  DO l # NIL -> res := res + 1; l := CDR(l) OD 
END;

(* Return the number of elements of "l". If "l" is 
   NIL, return 0. A checked run-time error occurs if 
   "l" is not a list. *)

PROC res := Nth(l, n) IS 
  IF 
    n >= 0 -> 
      DO n > 0 -> n := n - 1; l := CDR(l) OD; 
      res := CAR(l) 
  FI 
END;

(* Return the "n"th element of "l", where the first 
   element is numbered zero. A checked run-time error 
   occurs if "l" is not a proper list or if "n" is not 
   in the range [0, Length(l)). *)

PROC res := Last(l) IS 
  DO CDR(l) # NIL -> l := CDR(l) OD; res := CAR(l) 
END;

(* Return the last element of "l". A checked run-time 
   error occurs if "l" is not a proper list. *)

PROC res := Prefix(l, num) IS 
  IF 
    num <= 0 OR l = NIL -> res := NIL 
  | res := (CAR(l), Prefix(CDR(l), num - 1)) 
  FI 
END;

(* Return a list of the first "num" elements of "l". 
   If "num <= 0", return "NIL". If "num >= Length(l)", 
   return (a copy of) "l". *)

PROC res := Suffix(l, num) IS 
  res := SuffixFrom(l, Length(l) - num) 
END;

(* Return a list of the last "num" elements of "l". If 
   "num <= 0", return "NIL". If "num >= Length(l)", 
   return "l". *)

PROC res := SuffixFrom(l, i) IS 
  DO i > 0 AND l # NIL -> i := i - 1; l := CDR(l) OD; 
  res := l 
END;

(* Return the longest suffix of "l" that does not 
   include its first "i" elements. If "i <= 0", return 
   "l". If "i >= Length(l)", return "NIL". *)

PROC res := Reverse(l) IS 
  res := NIL; 
  DO 
    VAR u, v IN 
      l = (u, v) -> res := (u, res); l := v 
    END 
  OD 
END;

(* Return the list containing the elements of "l" in 
   reverse order. If "l" is not a pair, return NIL. *)

PROC res := Sum(l) IS 
  res := 0; 
  DO l # NIL -> res := res + CAR(l); l := CDR(l) OD 
END;

(* Return the sum of the elements of "l". If "l" is 
   NIL, return 0. A checked run-time error occurs if 
   "l" is not a list of numbers. *)