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

[Brent Yorgey]

http://hackage.haskell.org/package/fmlist-0.8/docs/Data-FMList.html

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>
> 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
>>
>
>
> _______________________________________________
> 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/20141009/d8316431/attachment.html>