strict bits of datatypes

Claus Reinke claus.reinke at talk21.com
Tue Mar 20 11:37:16 EDT 2007


    x `seq` x    === x

and so

    x = x `seq` x     === x = x

but, in general,

    x = x `seq` foo     =/=     x = foo

consider

    x = x `seq` ((1:) x)
    x = x `seq` ((1:) (x `seq` ((1:) x)))
    x = x `seq` ((1:) (x `seq` ((1:) (x `seq` ((1:) x)))))
    ..

ignoring evaluation order, partially unrolling/substituting x also unrolls/substitutes 
applications of seq (in proper call-by-need, we couldn't even do the substitution until 
after the evaluation, so we'd never get this far). no part of the right-hand side is defined 
unless x is - that is what seq is about, isn't it?

i do like the argument about different fixpoints - does that correspond to inductive vs 
coinductive definitions which are so often mixed in haskell? when working with cyclic 
structures, we often are quite happy without a base case. so instead of the inductive

    f 0 = True
    f n = f (n-1)
    -- provided that (f (n-1)) is defined, (f n) is defined 

we have things like

    nats = 1:map (+1) nats 
    -- nats is partially defined if we just assume that nats is partially defined

and it is nice to have both available, if not all that well separated. whether we're 
talking co-recursion or recursion seems to depend entirely on whether the recursive
references are in a non-strict or strict context (so that the definitions are productive
or not). 

so it seems to me that adding seq to a (co-)recursion is precisely about resolving
this ambiguity and forcing induction

    nats = (1:) $! map (+1) nats 
    -- nats is defined if we can prove that nats is defined, which we can't anymore

and saying that we can get back to co-induction by eliding the seq may be correct,
but irrelevant. and the same reasoning ought to apply to strict fields in data constructors.

sorry for waving about precisely defined terms in such a naive manner. 
i hope it helps, and isn't too far of the mark!-)

claus



More information about the Haskell-prime mailing list