strict bits of datatypes

[apfelmus at quantentunnel.de]

Ian Lynagh wrote:
> Here I will just quote what Malcolm said in his original message:
> 
>     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.

Well, in a sense, it's exactly the defining property of strict
constructors that they are not automatically different from _|_.

The translation

>     q = FinCons 3 q
> === (by Haskell 98 report 4.2.1/Strictness Flags/Translation
>     q = (FinCons $ 3) $! q

is rather subtle: the first FinCons is a strict constructor whereas the
second is "the real constructor". In other words, the translation loops
as we could (should?) apply

    FinCons
 => \x y -> FinCons x $! y
 => \x y -> (\x' y' -> FinCons x' $! y') x $! y
 => ...

ad infinitum.

> and in his recent e-mail to me:
> 
>     Yes, I still think this is a reasonable interpretation of the Report.  I
>     would phrase it as "After evaluating the constructor expression to WHNF,
>     any strict fields contained in it are also be guaranteed to be in WHNF."

Referring to WHNF would break the report's preference of not committing
to a particular evaluation strategy. That's already a good reason to
stick with FinCons 3 _|_ = _|_.

Besides, having

  let q = FinCons 3 q in q

not being _|_ crucially depends on memoization. Even with the
characterization by WHNF,

  let q x = FinCons 3 (q x) in q ()

is _|_.


Regards,
apfelmus