[Haskell] lazy constructors

[Jeremy Gibbons]

On 13 Oct 2004, at 06:59, Serge D. Mechveliani wrote:

> bottomStr :: String
> bottomStr = let xs = xs in xs
>
> bottomSPair :: (String, String)
> bottomSPair = let p = p in p

Note here that bottomSPair is bottom...

> addToSPair :: Char -> (String, String) -> (String, String)
> addToSPair    c       (xs,     ys    ) =  (c:xs,   ys    )

> In a more clear presentation, the computation should (?) be
>
>    head $ fst $ addToSPair 'a' bottomSPair
>    =
>    head $ fst $ addToSPair 'a' (bottomStr, bottomStr)

...so this step is wrong: bottomSPair is not the same as the pair 
(bottomStr, bottomStr). Haskell pairs are lifted: (bottom,bottom) is 
different from bottom.

> bottomSPair  is of type  (String, String).
> addToSPair   is declared as returning  (String, String).
> Hence, the complier knows ab initio that after  addToSPair
> the result is of kind
>                       ('a': _,  _) :: (String, String)

No. The result is necessarily of type (String,String), but need not be 
a proper pair. (And indeed, addToSPair c bottom yields bottom, not a 
proper pair.)

> So, similarly as
>               head ('a' : bottomStr)                    = 'a',   (1)
> it should be
>               head $ fst $ addToSPair 'a' bottomSPair   = 'a'    (2)
>
> Question 1
> ----------
> What may be the consequences for the language
> (let us call it HCLazy)  if it treats the data constructors like in
> (2), like more `lazy' ones?

That is, what if Haskell had unlifted pairs? Interesting question. Nils 
Anders Danielsson (http://www.cs.chalmers.se/~nad/) has been looking at 
it, with his work on Chasing Bottoms 
(http://www.cs.chalmers.se/~nad/software/ChasingBottoms/docs/).

> For example,  fst (bottom :: (a,b)) =  (bottom :: a)

I don't think this example is what you mean. This applies in Haskell 
already. I think what you mean is that (fst p, snd p) equals p for 
every p, including p=bottom.

> How to arrange the above `lazy' output?
> The whole result story is ready in several hours, or days,
> and each step should be displayed immediately as it is ready.

Another poster mentioned the possibility of using an irrefutable 
pattern (by adding a tilde). Equivalently, you can define

> addToSPair :: Char -> (String, String) -> (String, String)
> addToSPair c p =  (c : fst p, snd p)

Then addToSPair c bottom is (c:bottom,bottom) as you're hoping, not 
bottom.

Jeremy