[Haskell-cafe] Formalizing lazy lists?

Lennart Augustsson lennart at augustsson.net
Fri Nov 18 13:50:27 EST 2005


What do you mean by represent?
It's easy enough to write down the lambda term that is the
encoding of [0..].

	-- Lennart


Greg Woodhouse wrote:
> Maybe this is old hat, but the question about detecting loops in data
> structures got me thinking about this. I know you can encode the cons
> operator (and ordinary lists) in pure lambda calculus, but how could
> you possibly represent something like [0, 1..]? One thought that
> occurss to me is to treat it ass a kind of direct limit, but of course,
> the essence of a structure like this is that the ith entry is
> computable in a natural way, and it seems that an algebraic limit
> couldn't really capture this intuition unless we were to introduce some
> sort of higher order structure (which may be what we want, anyway).
> 
> 
> ===
> Gregory Woodhouse  <gregory.woodhouse at sbcglobal.net>
> 
> 
> "Interaction is the mind-body problem of computing."
> 
> --Philip Wadler
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 



More information about the Haskell-Cafe mailing list