/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 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).