/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Prolog stream/lazy list demonstration

   Written 2005 by Markus Triska (triska@gmx.at)
   Public domain code.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Sequence interface predicates. A sequence is represented as a term
   of the form seq(Car, Cdr), with Car being the first element, and
   Cdr the predicate to be computed to obtain the next state of the
   sequence.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

seq_make(Car, Cdr, seq(Car,Cdr)).
seq_car(seq(Car,_), Car).
seq_cdr(seq(_,Cdr), Cdr).

seq_next(Seq0, Seq) :-
    seq_cdr(Seq0, Cdr0),
    call(Cdr0, Seq).

seq_add(SeqA, SeqB, SeqAdd) :-
    seq_car(SeqA, CarA),
    seq_car(SeqB, CarB),
    Car is CarA + CarB,
    seq_next(SeqA, SeqANext),
    seq_next(SeqB, SeqBNext),
    seq_make(Car, seq_add(SeqANext,SeqBNext), SeqAdd).


seq_take(N, Seq0, Ls0, Ls) :-
    (	N =:= 0 ->
	Ls0 = Ls
    ;	seq_car(Seq0, Car),
	Ls0 = [Car|Rest],
	seq_next(Seq0, Seq1),
	N1 is N - 1,
	seq_take(N1, Seq1, Rest, Ls)
    ).

seq_take(Seq, N, Ts) :-
    seq_take(Seq, N, Ts, []).


seq_filter(Pred, Seq0, Seq) :-
    seq_car(Seq0, Car),
    seq_next(Seq0, Seq1),
    (	call(Pred, Car) ->
	seq_make(Car, seq_filter(Pred,Seq1), Seq)
    ;	seq_filter(Pred, Seq1, Seq)
    ).

seq_print(Seq) :-
    seq_car(Seq, Car),
    format("~w\n", [Car]),
    seq_next(Seq, Seq1),
    seq_print(Seq1).


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   stream of 1s
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

ones(Seq) :- seq_make(1, ones, Seq).


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   list patterns: [1,2..], [1,5..], [-3,-6..] etc.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

lp(First, Second, Seq) :-
    Diff is Second - First,
    Third is Second + Diff,
    seq_make(First, lp(Second,Third), Seq).


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   sieve of Eratosthenes
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

not_divisible_by(By, D) :- D mod By =\= 0.

primes(Ps) :-
    lp(2, 3, Seq),
    sieve(Seq, Ps).

sieve(Seq0, Seq) :-
    seq_car(Seq0, Car),
    seq_filter(not_divisible_by(Car), Seq0, Seq1),
    seq_make(Car, sieve(Seq1), Seq).


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Fibonacci sequence
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

fib(A, B, Seq) :-
    C is A + B,
    seq_make(A, fib(B,C), Seq).

fibs(Seq) :- fib(0, 1, Seq).


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Harmonic sequence
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

harms(Seq) :- seq_make(1, harmonic(2), Seq).

harmonic(N, Seq) :-
    Next is 1 rdiv N,
    N1 is N + 1,
    seq_make(Next, harmonic(N1), Seq).