[Haskell-cafe] beginner's problem about lists

[Matthias Fischmann]

[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 at haskell.org
> From: Malcolm Wallace <Malcolm.Wallace at cs.york.ac.uk>
> Date: Wed, 11 Oct 2006 15:14:23 +0100
> Subject: Re: [Haskell-cafe] beginner's problem about lists
> 
> Matthias Fischmann <fis at wiwi.hu-berlin.de> 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20061011/f89239c9/attachment.bin