[Haskell-cafe] `zip` doesn't work with infinite `Seq`s
byorgey at gmail.com
Thu Oct 9 13:23:25 UTC 2014
On Tue, Oct 7, 2014 at 12:29 AM, Carter Schonwald <
carter.schonwald at gmail.com> wrote:
> 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>
>> > 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
>> 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.
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe