<div dir="ltr">Thanks to Chris and Sam for the explanation! That explains it.</div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Oct 6, 2014 at 10:57 PM, Chris Wong <span dir="ltr"><<a href="mailto:lambda.fairy@gmail.com" target="_blank">lambda.fairy@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Matteo,<br>
<br>
Data.Sequence provides a general-purpose *finite* sequence. There is<br>
no such thing as an infinite Seq!<br>
<br>
In fact, you'll find that while<br>
<br>
    head $ repeat 'a'<br>
<br>
results in 'a',<br>
<br>
    Seq.head . Seq.fromList $ repeat 'a'<br>
<br>
never returns.<br>
<br>
Chris<br>
<div><div class="h5"><br>
On Tue, Oct 7, 2014 at 3:57 PM, Matteo Ferrando<br>
<<a href="mailto:matteo.ferrando2@gmail.com">matteo.ferrando2@gmail.com</a>> wrote:<br>
> Hello,<br>
><br>
> We are writing a compiler[1] for a course and found that the `zip` function<br>
> included in the `Data.Sequence` module, `zip :: Seq a -> Seq b -> Seq (a,<br>
> b)` would hang on the following code:<br>
><br>
>> -- using the `zip` from `Data.Sequence`<br>
>> zip ys (fomList $ repeat x)<br>
><br>
> We checked the implementation[2] in the source of `Data.Sequence` and found<br>
> the following:<br>
><br>
>> zip :: Seq a -> Seq b -> Seq (a, b)<br>
>> zip = zipWith (,)<br>
><br>
>> -- Here `zipWith` assumes *non-infinite `Seq`s*<br>
>> zipWith :: (a -> b -> c) -> Seq a -> Seq b -> Seq c<br>
>> zipWith f xs ys<br>
>>   | length xs <= length ys      = zipWith' f xs ys<br>
>>   | otherwise                   = zipWith' (flip f) ys xs<br>
><br>
>> -- Function not exported by `Data.Seq`, assumes `length xs <= length ys`<br>
>> zipWith' :: (a -> b -> c) -> Seq a -> Seq b -> Seq c<br>
>> zipWith' f xs ys = snd (mapAccumL k ys xs)<br>
>>   where<br>
>>     k kys x = case viewl kys of<br>
>>            (z :< zs) -> (zs, f x z)<br>
>            EmptyL    -> error "zipWith': unexpected EmptyL"<br>
><br>
> In the lazy reading of the documentation we did, we didn't find any warning<br>
> of using infinite `Seq`s for zips. (Maybe there are warings that we didn't<br>
> see). But looking at the code of `zip` in the `Prelude`:<br>
><br>
>> zip :: [a] -> [b] -> [(a,b)]<br>
>> zip (a:as) (b:bs) = (a,b) : zip as bs<br>
>> zip _      _      = []<br>
><br>
> We see that we could just *pattern-match* both heads, instead of making<br>
> assumptions.<br>
><br>
> Maybe this should be better explained in the documentation[3] of `zip` for<br>
> `Seq`s:<br>
><br>
>> zip :: Seq a -> Seq b -> Seq (a, b)<br>
>> O(min(n1,n2)). zip takes two sequences and returns a sequence of<br>
>> corresponding pairs. If one input is short, excess elements are discarded<br>
>> from the right end of the longer sequence.<br>
><br>
> Or just change the implementation for it to work with infinite `Seq`s.<br>
><br>
> For those of you who are curious, we ended up using the following code to<br>
> fix the *infinite `Seq`s problem*:<br>
><br>
>> -- using the `zip` from `Prelude`<br>
>> zip (toList ys) (repeat x)<br>
><br>
> [1] <a href="https://github.com/chamini2/sapphire" target="_blank">https://github.com/chamini2/sapphire</a><br>
> [2]<br>
> <a href="http://hackage.haskell.org/package/containers-0.5.5.1/docs/src/Data-Sequence.html#zip" target="_blank">http://hackage.haskell.org/package/containers-0.5.5.1/docs/src/Data-Sequence.html#zip</a><br>
> [3]<a href="http://hackage.haskell.org/package/containers-0.5.5.1/docs/Data-Sequence.html#v:zip" target="_blank">http://hackage.haskell.org/package/containers-0.5.5.1/docs/Data-Sequence.html#v:zip</a><br>
><br>
</div></div>> _______________________________________________<br>
> Haskell-Cafe mailing list<br>
> <a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
> <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
><br>
</blockquote></div><br></div>