[Haskell-cafe] Preventing sharing

[Oleg]

Kim-Ee Yeoh wrote:
> However, the record remains that Oleg has offered little by way of elegant
> bolting. His lazy programs based on a strict language tend to be cluttered
> with lazy and force functions that uglify previously elegant code.
>
> His arguments would persuade many more folks if, for instance, he could
> offer lazy-over-strict translations of Doug McIlroy's power serious
> one-liners with no loss in elegance:
>
> http://www.cs.dartmouth.edu/~doug/powser.html

I wanted to write about ordinary and (inappropriately named, to some)
full laziness and about how much elegance is in the eye of the
beholder and difficult to evaluate, and about many other things. The
quoted paragraph gave a much better topic: a concrete and easy to
evaluate challenge: can we re-write Doug McIlroy's code in a strict
language without ever using lazy and force or thunks everywhere --
basically maintaining the same structure of the code.

I took the challenge and re-wrote the powser code in OCaml, a strict
language. Haskell and OCaml differ in many respects, not just in the
order of evaluation. OCaml is in general a little bit more
verbose. Also, it does not have overloading. That's why you see not
just + but also +. (for float addition) and +% (which I define for
infinite series addition). Here are several examples:

Haskell:
  series f = f : repeat 0
OCaml:
  let series f = I.cons f I.repeat 0.

Things prefixed with I are library functions (just as repeat in Doug
McIlroy's code is a library function).


Haskell (using the tying-the-knot trick!) 
This is probably the most complex code
 (f:ft) / (g:gt) = qs where qs = f/g : series(1/g)*(ft-qs*gt)

OCaml:
 let ( /% ) fs gs = let (f,ft) = I.decon fs and (g,gt) = I.decon gs in
   I.fix @@ I.cons (f /. g) (fun qs -> series (1. /. g) *% (ft -% qs *% gt))

Integration in Haskell: 
  int fs = 0 : zipWith (/) fs [1..]
and OCaml:
  let integ = I.cons 0. (fun fs -> I.zip_with (/.) fs (iota 1.))

Tangent as a polynomial in Haskell: 
  tans = revert(int(1/(1:0:1)))
and OCaml
  let tans = revert @@ integ (int 1 /% from_list [1.;0.;1.])

It seems the OCaml code (executed in the bytecode interpreter) is a
bit faster than Haskell (in ghci). The complete code is available for
inspection at

        http://okmij.org/ftp/ML/powser.ml

There is no lazy/force in sight. Lazy/force could be used to implement
the infinite stream data type (what has been prefixed with I) but no
user of the stream library needs to know how exactly it is
implemented. In particular, all McIlroy's code is written without any
use of lazy/force. His code in OCaml has essentially the same
structure as Haskell code, considering the syntactic differences
between the two languages.

The point is that well-chosen combinators are far more important than
strict/lazy evaluation differences. If a language is expressive enough
to support mini-languages (embedded DSLs), we can write infinite
series and other DSL code without much trouble. Strict evaluation is
not an obstacle to infinite data structures, on demand evaluation,
etc. Once we can define a DSL, we can make it follow any evaluation
strategy we want.


Regarding the elegance, I can't help but quote a paragraph from Doug
McIlroy's powser's page:

   Extensions to handle polynomials make a practical package, doubled in
   size, not as pretty, but much faster and capable of feats like pascal.
   To see the dramatic speedup, try a bigger test like take 20 tans.

Note "not as pretty, but much faster". 

I'm afraid I'll have to significantly delay commenting on other points
raised in this discussion: I have several deadlines coming up.