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

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@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 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe