// $Id$

$use Apply Access Arithm Compare List2;

$func Deparen_Term term = expr;
Deparen_Term {
  (expr) = expr;
  term   = term;
};

$func Paren_Term term = (term);
Paren_Term term = (term);

Id e1 = e1;

Append (e1) e2 = e2 e1;

Ints s.start s.end = <List2.Ints s.start s.end>;

EqTerms t1 t1;

CompareTerms t1 t2 = <Compare (t1) (t2)>; 

Zip (e.list1) (e.list2) =
  (e.list1) (e.list2) /*empty*/ $iter {
    e.list1 : t.first1 e.rest1,
      e.list2 : t.first2 e.rest2 =
      (e.rest1) (e.rest2) e.new_list (t.first1 t.first2);
  } :: (e.list1) (e.list2) e.new_list,
  e.list1 : /*empty*/ =
  e.new_list;

Unzip e.list =
  () () e.list $iter {
    e.list : (t1 e2) e.tail =
      (e.list1 t1) (e.list2 e2) e.tail;
  } :: (e.list1) (e.list2) e.list,
  e.list : /*empty*/ =
  (e.list1) (e.list2);

Map s.Fname e.Fargs (e.list) =
  () e.list $iter {
    e.list : t.item e.rest =
      (e.new_list <Apply.Apply s.Fname e.Fargs t.item>) e.rest;
  } :: (e.new_list) e.list,
  e.list : /*empty*/ =
  e.new_list;

MapIn s.Fname e.Fargs (e.list) =
  () e.list $iter {
    e.list : (e.item) e.rest =
      (e.new_list (<Apply.Apply s.Fname e.Fargs e.item>)) e.rest;
  } :: (e.new_list) e.list,
  e.list : /*empty*/ =
  e.new_list;

Filter s.Fname e.Fargs (e.list) =
  () e.list $iter {
    e.list : t.item e.rest, {
      <Apply.Apply s.Fname e.Fargs t.item> : e =
        (e.new_list t.item) e.rest;
      (e.new_list) e.rest;
    };
  } :: (e.new_list) e.list,
  e.list : /*empty*/ =
  e.new_list;

Split s.Fname e.Fargs (e.list) =
  () () e.list $iter {
    e.list : t.item e.rest, {
      <Apply.Apply s.Fname e.Fargs t.item> : e =
        (e.true_list t.item) (e.false_list) e.rest;
      (e.true_list) (e.false_list t.item) e.rest;
    };
  } :: (e.true_list) (e.false_list) e.list,
  e.list : /*empty*/ =
  (e.true_list) (e.false_list);

IsElem e.list t.item =
  e.list : e t.item e;

Foldr s.Fname e.Fargs (e.value) (e.list) =
  (e.value) e.list $iter {
    e.list : e.something t.last =
      (<Apply.Apply s.Fname e.Fargs t.last e.value>) e.something;
  } :: (e.value) e.list,
  e.list : /*empty*/ =
  e.value;

Foldr1 s.Fname e.Fargs (e.list), {
  e.list : e.something t.last =
    <Foldr s.Fname e.Fargs (t.last) (e.something)>;
  /*empty*/;
};

All s.Fname e.Fargs (e.list) =
  e.list $iter {
    e.list : t.item e.rest =
      <Apply.Apply s.Fname e.Fargs t.item> : e,
      e.rest;
  } :: e.list,
  e.list : /*empty*/;

Any s.Fname e.Fargs (e.list) = # \{
  e.list $iter {
    e.list : t.item e.rest =
      # \{ <Apply.Apply s.Fname e.Fargs t.item> : e; },
      e.rest;
  } :: e.list,
  e.list : /*empty*/;
};

Concat e.lists = <Map &Deparen_Term (e.lists)>;

Paren expr = <Map &Paren_Term (expr)>;

Reverse {
  term e.list = <Reverse e.list> term;
  /*empty*/ = /*empty*/;
};

Intersperse {
  (e.sep) /*empty*/ = /*empty*/;
  (e.sep) t1 = t1;
  (e.sep) t1 e.list =
    (t1 e.sep) e.list $iter {
      e.list : t2 e.rest =
        (e.new_list t2 e.sep) e.rest;
    } :: (e.new_list) e.list,
    e.list : t2 =
    e.new_list t2;
};

Separate (e.sep) e.list =
  e.list (/*e.ll*/) $iter {
    e.list : e1 e.sep e2 = e2 (e.ll (e1));
    (e.ll (e.list));
  } :: e.list (e.ll),
  e.list : /*empty*/ =
  e.ll;

Nub e.expr = <NubBy &EqTerms e.expr>;

NubBy s.eqTerms e.expr =
  e.expr () $iter {
    e.expr : term e.rest, {
      <Any s.eqTerms term (e.selected)> = e.rest (e.selected);
      e.rest (e.selected (term));
    };
  } :: e.expr (e.selected),
  e.expr : /*empty*/ =
  <Concat e.selected>;

Replicate s.n e.expr =
  s.n /*e.list*/ $iter
    <Arithm.Sub s.n 1> e.list e.expr
  :: s.n e.list,
  <Le (s.n) (0)> =
  e.list;



$func QSort_Split t.num e.list = (e.list) (e.list);

QSort_Split t.num e.list,
  () () (e.list) $iter {
    e.list : t.head e.tail, {
      <Le (t.head) (t.num)>,
        (e.smaller t.head) (e.greater) (e.tail);
      (e.smaller) (e.greater t.head) (e.tail);
    };
  } :: (e.smaller) (e.greater) (e.list),
  e.list : /*empty*/,
  (e.smaller) (e.greater);

QSort {
  /* empty */   = /* empty */;
  t.head e.tail = <QSort_Split t.head e.tail> :: (e.smaller) (e.greater),
    <QSort e.smaller> t.head <QSort e.greater>;
};

SortBy s.cmpTerms e.list =
  <Length e.list> :: s.len,
  {
    <Le (s.len) (1)> = e.list;
    <Div s.len 2> :: s.k =
      <Merge s.cmpTerms (<SortBy s.cmpTerms <Left 0 s.k e.list>>) (<SortBy s.cmpTerms <Middle s.k 0 e.list>>)>;
  };

$func Merge s.cmpTerms (e.left) (e.right) = e.merged_list;
Merge s.cmpTerms (e.left) (e.right) =
  (e.left) (e.right) $iter {
    e.left : t.l e.left_rest, e.right : t.r e.right_rest = {
      <Apply.Apply s.cmpTerms t.l t.r> : '<' = (e.left_rest) (e.right) e.merged t.l;
      = (e.left) (e.right_rest) e.merged t.r;
    };
  } :: (e.left) (e.right) e.merged,
  \{
    e.left  : /*empty*/ = e.merged e.right;
    e.right : /*empty*/ = e.merged e.left;
  };

Sort e.list = <SortBy &CompareTerms e.list>;

/*
 * Returns number of e.expr entries in e.source and e.source without all e.expr's.
 */
//Entries e.expr (e.source) =
//  0 e.source () $iter {
//    e.source : e1 e.expr e2 = <"+" s.num 1> e2 (e.res e1);
//    s.num (e.res e.source);
//  } :: s.num e.source (e.res),
//  e.source : /*empty*/ =
//  s.num e.res;

/*
 * Add to the first list all new elements from the second one.
 */
Or (e.list1) e.list2 =
  (e.list1) e.list2 $iter {
    e.list2 : term e.rest,
      {
        e.list1 : e term e = (e.list1) e.rest;
        (e.list1 term) e.rest;
      };
  } :: (e.list1) e.list2,
  e.list2 : /*empty*/ =
  e.list1;

/*
 * Choose from the first list all elements present in the second one.
 */
And (e.list1) e.list2 =
  (e.list1) /*empty*/ $iter {
    e.list1 : term e.rest,
      {
        e.list2 : e term e = (e.rest) e.and term;
        (e.rest) e.and;
      };
  } :: (e.list1) e.and,
  e.list1 : /*empty*/ =
  e.and;

/*
 * Choose from the first list all elements not present in the second one.
 */
Sub (e.list1) e.list2 =
  (e.list1) /*empty*/ $iter {
    e.list1 : term e.rest,
      {
        e.list2 : e term e = (e.rest) e.not;
        (e.rest) e.not term;
      };
  } :: (e.list1) e.not,
  e.list1 : /*empty*/ =
  e.not;