[Haskell-cafe] Prime sieve and Haskell demo

[Doug McIlroy]

With deep apologies for sending the wrong file, I try again.

Doug

>> How about simply changing `sieve` to `trialDiv`?  It's not that I
>> don't like the given example, because it gives a very small use case
>> for laziness that is difficult enough to reproduce in an eagerly
>> evaluated language.
> 
> Is it really so difficult to reproduce in a strict language? Here is
> that Haskell example in OCaml
> 
> let primes =
>   let rec trialDiv (Cons (p,xs)) =
>     Cons (p, lazy (trialDiv @@ filter (fun x -> x mod p <> 0) @@ Lazy.force xs))
>   in trialDiv @@ iota 2

I'm afraid I don't understand why the program isn't a sieve. Is
the concern that the sequence of integers is thinned by dropping
composites rather than by merely marking them and counting across
them? Or is it that a trace of lazy evaluation will show that all
the divisibility tests on a single integer are clustered together
in time? Or something I haven't thought of?

Of course the program can be written in any Turing-complete language,
but the effort is likely to cause beads of sweat, like "lazy",
"force", or "spawn" to be shed on the algorithmic pearl. The sieve
can even be written succinctly as a bash shell script (below),
which exhibits warts (e.g. five flavors of parentheses) but no sweat.

Though both the Ocaml and the shell code are compact, neither dulls
the luster that lazy evaluation imparts to the Haskell.

    sift() {
        while true; do
            read p
            if (( $p % $1 != 0 )); then echo $p; fi
        done }
        
    sink() { read p; echo $p; sift $p | sink }

    seq 2 1000000 | sink