Anubis / Anubis

  Author       : Matthieu Herrmann
  Creation     : 2014/02/10
  Last update  : 2015/03/31 18:24 by matthieu@Embryo (inserted by vim).
  ======================================================================================================================

  ======================================================================================================================
  = Public part ========================================================================================================
  ======================================================================================================================

  The iterators are used to provide a "list-like" abstraction to other containers, such as trees.

  *** (1) Iterator definition and helper for lists.
  *** (2) Basic accesses
  *** (3) Item filtering/mapping function
  *** (4) Reducing/folding/unfolding functions
    *** (4.1) Classical functions
    *** (4.2) With "while" and "Maybe" condition
    *** (4.3) Unfold
  *** (5) Iterator advanced functions
  *** (6) Iterator printing

  *** (1) Iterator definition and helper for lists.
      ==================================================================================================================

public type Iterator($A):
  nil,                                // Empty iterator
  $A head .. One->Iterator($A) next.  // The head and the function providing the next iterator.

    Helper for definition without writing the functional.
public define Iterator($A) $A head .. Iterator($A) next.

    Reverse an iterator (linear time)
public define Iterator($A) reverse(Iterator($A) it).

    Create an iterator on the list l, from left to right.
public define Iterator($A) take_left(List($A) l).

    Create an iterator in the list l, from right to left.
public define Iterator($A) take_right(List($A) l).

    Creating a list from an iterator, conserve the order.
public define List($A) to_list(Iterator($A) it).

    Creatin a list from an iterator, reverse order but faster than "to_list"
public define List($A) to_reverse_list(Iterator($A) it).

    Create an iterator on an integer range, from "start" to (exlucded) "stop" by step "step".
  Note: * "start", "stop" and "step" must be coherend with their sign.
        * Step must be different than 0
              range(0, 5, 1)      => 0 .. 1 .. 2 .. 3 .. 4 .. nil
              range(-1, -5, -2)   => -1 .. -3 .. nil
              range(7, 5, -1)     => 7 .. 6 .. nil
              range(0, 5, -1)     => nil
              range(0, -5, 2)     => nil
public define Iterator(Int) range(Int start, Int stop, Int step).

    Like above, from 0 to stop by step of 1 or -1 according to the sign of stop.
public define Iterator(Int) range(Int stop).

  *** (2) Basic accesses
      ==================================================================================================================

    Get the current item of the iterator if it exist.
public define Maybe($A) get(Iterator($A) it).

    Get the next iterator.
public define Iterator($A) next(Iterator($A) it).

    Get the nth element starting from current iterator it.
  Equivalent to applying n times the next function and taking the head, but stop early if not enough item.
public define Maybe($A) nth(Int n, Iterator($A) it).

    Get the Iterator after the n next item from current iterator it.
public define Iterator($A) nthcdr(Int n, Iterator($A) it).

    Like nth but always return an element, being "default" instead of "failure"
public define $A force_nth(Int n, Iterator($A) it, $A default).

    Get an iterator composed of the first n item of current iterator it.
public define Iterator($A) first(Int n, Iterator($A) it).

  *** (3) Item filtering/mapping/iterating function
      ==================================================================================================================

    Lazily filtering/transforming element from the current iterator it.
public define Iterator($B) filter( $A -> Maybe($B) test, Iterator($A) it).

    A variant without transformation.
public define Iterator($A) filter( $A -> Bool test, Iterator($A) it).

    Lazily mapping element from the current iterator it.
public define Iterator($B) map( $A -> $B fun, Iterator($A) it).

    A variant with an extra parameter for the mapping function.
public define Iterator($B) map( ($A, $P) -> $B fun, $P parameter, Iterator($A) it).

    Apply **immediately** 'fun' to each element from the iterator.
public define One map_forget( $A -> $B fun, Iterator($A) it).

  *** (4) Reducing/folding/unfolding functions
      ==================================================================================================================

    *** (4.1) Classical functions
        ==================================================================================================================

    Get a left reduction function function for the operator op.
public define ($B, Iterator($A)) -> $B reduce_l( ($B, $A) -> $B op ).

    Get a righ reduction function for the operator op.
  Warning: non terminal recursion here !
public define (Iterator($A), $B) -> $B reduce_r( ($A, $B) -> $B op ).

    Monoïdal variant to use when you really have a monoïd (use left reduction).
public define ($A, Iterator($A)) -> $A reduce( ($A, $A) -> $A op ).

    Correspond to an application of the left reduction on it, with z for op
public define $B fold_left(Iterator($A) it, $B z, ($B, $A) -> $B op).

    Correspond to an application of the right reduction on it, with z for op
public define $B fold_right(Iterator($A) it, $B z, ($A, $B) -> $B op).

    Correspond to an application of the monoïdal reduction on it, with z for op
public define $A fold(Iterator($A) it, $A z, ($A, $A) -> $A op).

    *** (4.2) With "while" condition
        ==================================================================================================================
    Those function are derived from the above by adding a "while" condition. Operators with "Maybe" abort on failure.

public define ($B, Iterator($A)) -> Maybe($B) reduce_l( ($B, $A) -> Maybe($B) op ).

public define (Iterator($A), $B) -> Maybe($B) reduce_r( ($A, $B) -> Maybe($B) op ).

public define ($A, Iterator($A)) -> Maybe($A) reduce( ($A, $A) -> Maybe($A) op ).


public define ($B, Iterator($A)) -> $B reduce_while_l(($B, $A) -> $B op, $B->Bool go_on ).

public define (Iterator($A), $B) -> $B reduce_while_r(($A, $B) -> $B op, $B->Bool go_on ).

public define ($A, Iterator($A)) -> $A reduce_while(($A, $A) -> $A op, $A->Bool go_on ).


public define Maybe($B) fold_left(Iterator($A) it, $B z, ($B, $A) -> Maybe($B) op).

public define Maybe($B) fold_right(Iterator($A) it, $B z, ($A, $B) -> Maybe($B) op).

public define Maybe($A) fold(Iterator($A) it, $A z, ($A, $A) -> Maybe($A) op).


public define $B fold_while_left(Iterator($A) it, $B z, ($B, $A) -> $B op, $B->Bool go_on).

public define $B fold_while_right(Iterator($A) it, $B z, ($A, $B) -> $B op, $B->Bool go_on).

public define $A fold_while(Iterator($A) it, $A z, ($A, $A) -> $A op, $A->Bool go_on).


    *** (4.3) Unfold
        ==================================================================================================================
    Extract elements of the iterator from a structure of type $B.
public define Iterator($A) unfold($B item, $B -> Maybe(($A, $B)) unspool).

  Example with $B = List($A) :
    unfold(list_a,
      (List($A) l) |-> if l is
      {
        [ ]             then failure
        [head . tail]   then success((head, tail))
      }
    )

  *** (5) Iterator advanced functions
      ==================================================================================================================

    Append it2 at the end of it1.
public define Iterator($A) append(Iterator($A) it1, Iterator($A) it2).

    Create an iterator of couple from to iterator. The resulting iterator will have as many item as the shortest
  input iterator.
public define Iterator(($A,$B)) zip(Iterator($A) it1, Iterator($B) it2).

  *** (6) Iterator printing
      ==================================================================================================================

    Create a sequential string representation of the iterator with a custom separator and enclosing string only puts
  if the iterator is non-empty.
public define String to_string(Iterator($A) it, $A->String op, String first, String sep, String last).

    Create a sequential string representation of the iterator with a custom separator.
public define String to_string(Iterator($A) it, $A->String op, String sep).

    Same as above with the default ", " separator.
public define String to_string(Iterator($A) it, $A->String op).



  ======================================================================================================================
  = Private part =======================================================================================================
  ======================================================================================================================

  *** [1] Basic constructor, constructors for lists.
  *** [2] Basic accesses
  *** [3] Item conversion/filtering function
  *** [4] Reducing/folding/unfolding functions
    *** [4.1] Classical functions
    *** [4.2] With "while" and "Maybe" condition
    *** [4.3] Unfold
  *** [5] Iterator advanced functions
  *** [6] Iterator length
  *** [7] Iterator printing
    *** [7.1] Internal printing definitions
    *** [7.2] Public printing interface.

  *** [1] Basic constructor, constructors for lists.
      ==================================================================================================================

public define Iterator($A) $A head .. Iterator($A) next = head .. (One u)|->next.

    Reverse an iterator (linear time)
public define Iterator($A) reverse(Iterator($A) it) = fold_left(it, nil, (Iterator($A) itl, $A item)|-> item .. itl).

public define Iterator($A) take_left(List($A) l) = if l is
  {
    [ ]       then nil,
    [h . t]   then h .. (One u) |-> take_left(t)
  }.

public define Iterator($A) take_right(List($A) l) = if reverse(l) is
  {
    [ ]       then nil,
    [h . t]   then h .. (One u) |-> take_left(t)
  }.

public define List($A) to_list(Iterator($A) it) = reverse(to_reverse_list(it)).

    Creating a list from an iterator, reverse order but faster than "to_list": using fold left which is terminal.
public define List($A) to_reverse_list(Iterator($A) it) = fold_left(it, [], (List($A) accu, $A item) |-> [item . accu]).

    Creating an iterator with a sequence of decreasing integers.
define Iterator(Int) range_dec(Int start, Int lower, Int neg_step) =
  if start > lower
  then start .. (One u) |-> range_dec(start + neg_step, lower, neg_step)
  else nil.

    Creating an iterator with a sequence of increasing integers.
define Iterator(Int) range_inc(Int start, Int upper, Int pos_step) =
  if start < upper
  then start .. (One u) |-> range_inc(start + pos_step, upper, pos_step)
  else nil.

    Create an iterator on an integer range, from "start" to (exlucded) "stop" by step "step".
  Note: * "start", "stop" and "step" must be coherend with their sign.
        * Step must be different than 0
              range(0, 5, 1)      => 0 .. 1 .. 2 .. 3 .. 4 .. nil
              range(-1, -5, -2)   => -1 .. -3 .. nil
              range(7, 5, -1)     => 7 .. 6 .. nil
              range(0, 5, -1)     => nil
              range(0, -5, 2)     => nil
public define Iterator(Int) range(Int start, Int stop, Int step) =
  if start < stop
  then if step > 0 then range_inc(start, stop, step) else nil
  else if start > stop
  then if step < 0 then range_dec(start, stop, step) else nil
  else nil. // start == stop

public define Iterator(Int) range(Int stop) =
  if stop < 0       then  range_dec(0, stop, -1)
  else if stop > 0  then  range_inc(0, stop, 1)
  else                    nil.

  *** [2] Basic accesses
      ==================================================================================================================

public define Maybe($A) get(Iterator($A) it) = if it is
  {
    nil           then failure,
    head .. tail  then success(head)
  }.

public define Iterator($A) next(Iterator($A) it) = if it is
  {
    nil           then nil,
    head .. tail  then tail(unique)
  }.

public define Maybe($A) nth(Int n, Iterator($A) it) =
  if it is
  {
    nil           then failure
    head .. tail  then
      if n<0 then failure
      else if n=0 then success(head)
      else nth(n-1, tail(unique))
  }.

public define Iterator($A) nthcdr(Int n, Iterator($A) it) =
  if n =< 0 then it else
  if it is
  {
    nil           then nil,
    head .. tail  then nthcdr(n-1,tail(unique))
  }.

public define $A force_nth( Int n, Iterator($A) it, $A default) = if it is
  {
    nil           then default
    head .. tail  then
      if n<0 then default
      else if n=0 then head
      else force_nth(n-1, tail(unique), default)
  }.

public define Iterator($A) first(Int n, Iterator($A) it) = if it is
  {
    nil           then nil
    head .. tail  then if n =< 0 then nil else head .. (One u) |-> first(n-1, tail(u))
  }.

  *** [3] Item conversion/filtering function
      ==================================================================================================================

public define Iterator($B) filter( $A -> Maybe($B) test, Iterator($A) it) = if it is
  {
    nil           then nil
    head .. tail  then if test(head) is
    {
      failure     then filter(test, tail(unique))
      success(h)  then h .. (One u)|->filter(test, tail(u))
    }
  }.

public define Iterator($A) filter( $A -> Bool test, Iterator($A) it) =
  filter( ($A item)|-> if test(item) then success(item) else failure, it).

public define Iterator($B) map( $A -> $B fun, Iterator($A) it) = if it is
  {
    nil           then nil
    head .. tail  then fun(head) .. (One u)|->map(fun, tail(u))
  }.

public define Iterator($B) map( ($A, $P) -> $B fun, $P parameter, Iterator($A) it) = if it is
  {
    nil           then nil
    head .. tail  then fun(head, parameter) .. (One u)|->map(fun, parameter, tail(u))
  }.

public define One map_forget( $A -> $B fun, Iterator($A) it) = if it is
  {
    nil           then unique
    head .. tail  then forget(fun(head)); map_forget(fun, tail(unique))
  }.

  *** [4] Reducing/folding/unfolding functions
      ==================================================================================================================

    *** [4.1] Classical functions
        ================================================================================================================

public define ($B, Iterator($A)) -> $B reduce_l( ($B, $A) -> $B op ) =
  ($B z, Iterator($A) it) |-rec_op-> if it is
  {
    nil           then z
    head .. tail  then rec_op(op(z, head), tail(unique))
  }.

public define (Iterator($A), $B) -> $B reduce_r( ($A, $B) -> $B op ) =
  ( Iterator($A) it, $B z ) |-rec_op-> if it is
  {
    nil           then z
    head .. tail  then op(head, rec_op(tail(unique), z))
  }.

public define ($A, Iterator($A)) -> $A reduce( ($A, $A) -> $A op ) = reduce_l(op).


public define $B fold_left(Iterator($A) it, $B z, ($B, $A) -> $B op) = reduce_l(op)(z, it).

public define $B fold_right(Iterator($A) it, $B z, ($A, $B) -> $B op) = reduce_r(op)(it, z).

public define $A fold(Iterator($A) it, $A z, ($A, $A) -> $A op) = reduce(op)(z, it).

    *** [4.2] With "while" and "Maybe" condition
        ================================================================================================================

public define ($B, Iterator($A)) -> Maybe($B) reduce_l( ($B, $A) -> Maybe($B) op ) =
  ($B z, Iterator($A) it) |-rec_op-> if it is
  {
    nil           then success(z)
    head .. tail  then
      if op(z, head) is success(s)
      then rec_op(s, tail(unique))
      else failure
  }.

public define (Iterator($A), $B) -> Maybe($B) reduce_r( ($A, $B) -> Maybe($B) op ) =
  ( Iterator($A) it, $B z ) |-rec_op-> if it is
  {
    nil           then success(z)
    head .. tail  then
      if (Maybe($B))rec_op(tail(unique), z) is success(s)
      then op(head, s)
      else failure
  }.

public define ($A, Iterator($A)) -> Maybe($A) reduce( ($A, $A) -> Maybe($A) op ) = reduce_l(op).



public define ($B, Iterator($A)) -> $B reduce_while_l(($B, $A) -> $B op, $B->Bool go_on ) =
  ($B z, Iterator($A) it) |-rec_op->
  if go_on(z)
  then if it is
  {
    nil           then z
    head .. tail  then rec_op(op(z, head), tail(unique))
  }
  else z.

public define (Iterator($A), $B) -> $B reduce_while_r(($A, $B) -> $B op, $B->Bool go_on ) =
  ( Iterator($A) it, $B z ) |-rec_op->
  if go_on(z)
  then if it is
  {
    nil           then z
    head .. tail  then op(head, rec_op(tail(unique), z))
  }
  else z.

public define ($A, Iterator($A)) -> $A reduce_while(($A, $A) -> $A op, $A->Bool go_on ) = reduce_while_l(op, go_on).


public define Maybe($B) fold_left(Iterator($A) it, $B z, ($B, $A) -> Maybe($B) op) = reduce_l(op)(z, it).

public define Maybe($B) fold_right(Iterator($A) it, $B z, ($A, $B) -> Maybe($B) op) = reduce_r(op)(it, z).

public define Maybe($A) fold(Iterator($A) it, $A z, ($A, $A) -> Maybe($A) op) = reduce(op)(z, it).


public define $B fold_while_left(Iterator($A) it, $B z, ($B, $A) -> $B op, $B->Bool go_on) =
  reduce_while_l(op, go_on)(z, it).

public define $B fold_while_right(Iterator($A) it, $B z, ($A, $B) -> $B op, $B->Bool go_on) =
  reduce_while_r(op, go_on)(it, z).

public define $A fold_while(Iterator($A) it, $A z, ($A, $A) -> $A op, $A->Bool go_on ) =
  reduce_while(op, go_on)(z, it).


    *** [4.3] Unfold
        ================================================================================================================

            Unfolding: In case of "failure" for unspool, returns the nil iterator.
public define Iterator($A) unfold($B item, $B -> Maybe(($A, $B)) unspool) = if unspool(item) is
  {
    failure     then nil,
    success(s)  then if s is (a, b) then a .. (One u) |-> unfold(b, unspool)
  }.

  *** [5] Iterator advanced functions
      ==================================================================================================================

public define Iterator($A) append(Iterator($A) it1, Iterator($A) it2) = if it1 is
  {
    nil           then it2
    head .. tail  then head .. (One u)|-> append(tail(u), it2)
  }.

public define Iterator(($A,$B)) zip(Iterator($A) it1, Iterator($B) it2) =
  if it1 is
  {
    nil       then nil
    h1 .. t1  then if it2 is
    {
      nil       then nil
      h2 .. t2  then (h1,h2) .. (One u) |-> zip(t1(u), t2(u))
    }
  }.

  *** [6] Iterator length
      ==================================================================================================================

define Int length(Iterator($A) ita, Int so_far) = if ita is
  {
    nil     then so_far
    h .. t  then length(t(unique), so_far+1)
  }.

public define Int length(Iterator($A) ita) = length(ita, 0).

  *** [7] Iterator printing
      ==================================================================================================================

    *** [7.1] Internal printing definitions
        ================================================================================================================

    Put the Separators on the following prints
define String to_string2(Iterator($A) it, $A->String op, String sep, String str) =
  if get(it) is
  {
    failure     then str
    success(s)  then to_string2( next(it), op, sep, str + sep + op(s))
  }.

    Do not put the separator on the 'first' print
define String to_string(Iterator($A) it, $A->String op, String sep, String str) =
  if get(it) is
  {
    failure     then str
    success(s)  then to_string2( next(it), op, sep, str + op(s))
  }.


    *** [7.2] Public printing interface.
        ================================================================================================================

public define String to_string(Iterator($A) it, $A->String op, String first, String sep, String last) =
  if it is nil then "" else to_string(it, op, sep, first) + last.

public define String to_string(Iterator($A) it, $A->String op, String sep) = to_string(it, op, sep, "").

public define String to_string(Iterator($A) it, $A->String op) = to_string(it, op, ", ").



  ======================================================================================================================
  = Testing part =======================================================================================================
  ======================================================================================================================

  read tools/basis.anubis

  global define One test_it(List(String) args) =
  with it1 = range(0, 10, 1),
  with it2 = range(0, -10, -3),
  with it3 = range(0, -10, 1),
  with it4 = range(-5, 0, -1),
  with it5 = range(0, 5, 0),
  with it6 = range(0, 0, 1),
  with it7 = (Iterator(Int))range(15),
  with it8 = (Iterator(Int))range(-10),
  with it9 = (Iterator(Int))range(0),
  println(to_string(it1, to_decimal));
  println(to_string(it2, to_decimal));
  println(to_string(it3, to_decimal));
  println(to_string(it4, to_decimal));
  println(to_string(it5, to_decimal));
  println(to_string(it6, to_decimal));
  println(to_string(it7, to_decimal));
  println(to_string(it8, to_decimal));
  println(to_string(it9, to_decimal));
  with it = (List(Int)) (1 :: 2 ::3 ::4 :: []),
  println(to_string(take_left(it), to_decimal));
  println(to_string(take_right(it), to_decimal));
  println(to_string(first(3, take_left(it)), to_decimal));
  println(to_string(first(3, take_right(it)), to_decimal));
  println(to_string(filter( (Int i)|-> if i =< 2 then success(i) else failure,  take_left(it)), to_decimal));
  println(to_string(filter( (Int i)|-> i =< 2,  take_right(it)), to_decimal));
  println(to_string(map( (Int i)|-> i+10,  take_left(it)), to_decimal));
  println(to_string(map( (Int i, Int j)|-> i+j, 200, take_right(it)), to_decimal));
  println(to_string(append(take_left(it), take_right(it)), to_decimal));
  with val = reduce_l( (Int i, Int j) |-> i - j )(0, it),
  with val2 = reduce_r( (Int i, Int j) |-> i - j )(it, 0),
  println("reduce left: "+val+" reduce right: "+val2);
  println("fold left: " + fold_left(it, 0, (Int i, Int j) |-> i - j));
  println("fold right: " + fold_right(it, 0, (Int i, Int j) |-> i - j));
  unique.