/** Bombs-Must-Detonate: Standard Library
  * Author: Brian Go
  *
  * The following library contains general-purpose useful functions.
  *
  **/

/* * * * *
 * Lists *
 * * * * */

//Returns the length of lst
template <T>
int list_length(T list lst) {
   if(lst = nil[T]) {
      return 0;
   }
   else {
      return 1 + list_length(cdr lst);
   }
}

//Maps foo onto lst
template <T,U>
U list list_map((T) -> U foo, T list lst) {
   if(lst = nil[T]) {
      return nil[U];
   }
   else {
      return foo(car lst)::list_map(foo, cdr lst);
   }
}

//Returns the list of elements in lst satisfying predicate
template <T>
T list list_filter((T) -> bool predicate, T list lst) {
  if (lst = nil[T]) {
    return nil[T];
  }
  else {
    if (predicate(car lst)) {
      return (car lst)::list_filter(predicate, cdr lst);
      }
    else {
      return list_filter(predicate, cdr lst);
    }
  }
}

//Fold Right
template <T,U>
U list_foldr((T,U) -> U fun, U initVal, T list lst) {
   if(lst = nil[T]) {
      return initVal;
   }
   else {
      return fun(car lst,list_foldr(fun, initVal, cdr lst));
   }
}

//Fold Left
template <T,U>
T list_foldl((T,U) -> T fun, T initVal, U list lst) {
   if(lst = nil[U]) {
      return initVal;
   }
   else {
      return list_foldl(fun, fun(initVal, car lst), cdr lst);
   }
}