To implement streams as delayed lists in Lisp it's recommended to use Lisp macros.
(defmacro cons-stream (a b)
(cons ,a (delay ,b)))
(defmacro delay (expr)
`(memo-proc (lambda () ,expr)))
What would by Python and Perl way to do the same thing?
EDIT. Is it possible to use such a cool construct as streams
(define primes (sieve (integers-starting-from 2)))
in languages like Python and Perl
In Python, the closest structure would probably be a generator expression.
In Perl, there is not a native lazy list, but the language provides all of the primitives that are needed to build one. I have written a lazy list library called List::Gen which is available on CPAN.
use List::Gen '*';
my $primes = <2..>->filter(\&is_prime); # where you provide &is_prime
say "@$primes[0..10]"; # lazily finds the first 11 primes
the <2..> bit could be written verbosely as range(2, 9**9**9)
runrig suggested the techniques from Mark Dominus's excellent Higher Order Perl. Using the Stream module from HOP's freely available sample code, the sieve of Eratosthenes is
#! /usr/bin/env perl
use strict;
use warnings;
use Stream qw/ filter head node promise show tail upfrom /;
use subs 'sieve'; # no parens on recursive calls
sub sieve {
my($s) = @_;
my $n = head $s;
node $n, promise { sieve filter { $_[0] % $n != 0 } tail $s };
}
sub primes { sieve upfrom 2 }
show primes, 10;
Output:
$ ./primes 2 3 5 7 11 13 17 19 23 29
Borrowing code from a gist by alexbowe, the sieve in Python using streams is
#! /usr/bin/env python
null_stream = (None, None)
def reduce(f, result, stream):
if stream is null_stream: return result
return reduce(f, f(result, head(stream)), tail(stream))
def take(N, stream):
if N <= 0 or stream is null_stream: return null_stream
return (head(stream), lambda: take(N-1, tail(stream)))
def filter(pred, stream):
if stream is null_stream: return null_stream
if pred(head(stream)):
return (head(stream), lambda: filter(pred, tail(stream)))
return filter(pred, tail(stream))
def integers_from(N): return (N, lambda: integers_from(N+1))
def head((H, _)): return H
def tail((_, T)): return T()
def to_array(stream): return reduce(lambda a, x: a + [x], [], stream)
def sieve(stream):
if stream is null_stream: return null_stream
h = head(stream)
return (h, lambda: sieve(filter(lambda x: x%h != 0, tail(stream))))
def primes(): return sieve(integers_from(2))
print to_array(take(10, primes()))
Output:
$ ./prymes [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
In some languages, the stream pattern is invisible. Lazy evaluation is a feature of Haskell, for instance, so you could define primes as
primes = sieve [2 ..]
where sieve (x:xs) =
let remains = filter (not . isMultipleOf x) xs
in x : sieve remains
isMultipleOf a b = b `mod` a == 0
In perl you would use anonymous subroutines (like LISP's lambda). There are plenty of examples in chapter 6 of Higher Order Perl
Although it's hard to tell what you actually want, since many things are subtly different between the different languages, he Python equivalent you're looking for is probably a generator, which is a kind of function that can be asked to produce the next value and then suspends itself. They were previously covered in (for example) What can you use Python generator functions for?, and there are lots of examples and tutorials of them available elsewhere -- for example, http://www.dabeaz.com/generators/index.html
