Re: [Haskell-cafe] beginner's problem about lists

11 Oct 2006

      [start this post by reading the last paragraph, i just needed to go
through the rest to figure it out for myself.]

On Wed, Oct 11, 2006 at 03:14:23PM +0100, Malcolm Wallace wrote:
...
To: haskell-cafe@haskell.org
From: Malcolm Wallace 
Date: Wed, 11 Oct 2006 15:14:23 +0100
Subject: Re: [Haskell-cafe] beginner's problem about lists
Matthias Fischmann  wrote:
...
...
No, your Fin type can also hold infinite values.
let q = FinCons 3 q in case q of FinCons i _ -> i  ==>  _|_
does that contradict, or did i just not understand what you are
saying?
That may be the result in ghc, but nhc98 gives the answer 3.
It is not entirely clear which implementation is correct.  The Language
Report has little enough to say about strict components of data
structures - a single paragraph in 4.2.1.  It defines them in terms of
the strict application operator ($!), thus ultimately in terms of seq,
and as far as I can see, nhc98 is perfectly compliant here.
The definition of seq is
    seq _|_ b = _|_
    seq  a  b = b, if a/= _|_
In the circular expression
    let q = FinCons 3 q in q
it is clear that the second component of the FinCons constructor is not
_|_ (it has at least a FinCons constructor), and therefore it does not
matter what its full unfolding is.
Interesting point.  But one could argue that with strictness in data
types this is what happens:

       FinCons 3 q
  ==>  q `seq` FinCons 3 q
  ==>  FinCons 3 q `seq` FinCons 3 q
  ==>  q `seq` FinCons 3 q `seq` FinCons 3 q
  ==>  ...

Section 4.2.1. of the H98 standard sais: "Whenever a data constructor
is applied, each argument to the constructor is evaluated if and only
if the corresponding type in the algebraic datatype declaration has a
strictness flag..."  It is also reduced to strict function application
("$!") there, see Section 6.2.  This yields:

       FinCons 3 q                                       (1.)
  ==>  (\ x1 x2 -> ((FinCons $ x1) $! x2)) 3 q           (2.)
  ==>  (FinCons $ 3) $! q                                (3.)
  ==>  q `seq` ((FinCons $ 3) q)                         (4.)
  ==>  FinCons 3 q `seq` ((FinCons $ 3) q)               (5.)

-- Hh.  I suddenly see what you mean.

Ok, but isn't there a difference between "FinCons 3 q" as an
expression and "FinCons <box> <box>" as HNF?  According to Section
4.2.1., the former is equivalent to a lambda expression in (2.), which
evaluates to (5.).  So the first argument to seq in (5.) should
evaluate to (5.) as well, and so on.

Tell me I'm wrong, I want to learn something!  (-:

thanks,
matthias