[Haskell-cafe] `zip` doesn't work with infinite `Seq`s

[Carter Schonwald]

the halting problem has nothing to do with it. Simply you can't cache the
tail if no finite number of steps will get you there :)

(halting problem style impossibility results tend to be wayyyy niftier)

On Mon, Oct 6, 2014 at 11:49 PM, Chris Wong <lambda.fairy at gmail.com> wrote:

> > Data.Sequence provides a general-purpose *finite* sequence. There is
> > no such thing as an infinite Seq!
> >
> > In fact, you'll find that while
> >
> >     head $ repeat 'a'
> >
> > results in 'a',
> >
> >     Seq.head . Seq.fromList $ repeat 'a'
> >
> > never returns.
>
> To add to my previous comment: the key feature of Seq is constant-time
> access to both ends of the sequence. It does this by caching the the
> first and last few elements in the constructor.
>
> Given these constraints, the behavior you observe makes sense. To
> construct a Seq (as the call to fromList does), we must find the last
> element in the list so that we can cache it. But an infinite list
> doesn't have a last element (by definition). So fromList never
> terminates.
>
> I don't think there's a way to allow infinite sequences while also
> having efficient access to both ends. The Halting Problem probably
> comes into it somewhere. The solution you gave is likely the best one.
>
> Chris
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20141007/9b785ebe/attachment.html>