Make <|> for ZipLists lazy for infinite lists

Discussion:

박신환

2018-06-05 03:36:34 UTC

Ivan Lazar Miljenovic

2018-06-05 04:33:19 UTC

Permalink

Seems to work for me:

$ ghci
GHCi, version 8.2.2: http://www.haskell.org/ghc/ :? for help
Loaded GHCi configuration from /Users/ivan/.ghci
Prelude> import Control.Applicative
Prelude Control.Applicative> let zAppend (ZipList xs) (ZipList ys) =
ZipList (xs ++ drop (length xs) ys)
Prelude Control.Applicative> take 10 (getZipList (ZipList [1..4] `zAppend`
ZipList [5..])) :: [Int]
[1,2,3,4,9,10,11,12,13,14]
Prelude Control.Applicative> take 10 (getZipList (ZipList [1..] `zAppend`
ZipList [5..])) :: [Int]
[1,2,3,4,5,6,7,8,9,10]
Prelude Control.Applicative>

(After all, the `length` call will never get evaluated.)

However, I do prefer your solution to avoid traversing the first list
twice, so +0.5 from me.

ZipList <http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicative.html#ZipList> xs <http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicative.html#local-6989586621679319881> <|> <http://hackage.haskell.org/package/base-4.11.1.0/docs/src/GHC.Base.html#%3C%7C%3E> ZipList <http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicative.html#ZipList> ys <http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicative.html#local-6989586621679319882> = ZipList <http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicative.html#ZipList> (xs <http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicative.html#local-6989586621679319881> ++ <http://hackage.haskell.org/package/base-4.11.1.0/docs/src/GHC.Base.html#%2B%2B> drop <http://hackage.haskell.org/package/base-4.11.1.0/docs/src/GHC.List.html#drop> (length <http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Data.Foldable.html#length> xs <http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicative.html#local-6989586621679319881>) ys <http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicative.html#local-6989586621679319882>)
ZipList [] <|> ys = ys
xs <|> ZipList [] = xs
ZipList (x:xs) <|> ZipList (_:ys) = ZipList (x : (ZipList xs <|> ZipList ys))
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

--
Ivan Lazar Miljenovic
***@gmail.com
http://IvanMiljenovic.wordpress.com

Chris Wong

2018-06-05 07:00:58 UTC

Permalink

The proposed definition has one drawback: it is strict in its second
argument.

It should be possible to make it lazy in its second argument while keeping
the single-pass behavior, though. Something like this?

ZipList xs <|> ZipList ys = ZipList $ go xs ys 0
where
go [] ys n = drop n ys
go (x:xs) ys n = x : (go xs ys $! n + 1)

Edward Kmett

2018-06-06 08:39:02 UTC

Permalink

I rather like this version. It avoids needlessly holding onto the entire
list from the start, unlike the original version, which is leakier, and
avoids the unnecessary strictness problem of the second version.

We should definitely keep the original in a comment as a description of the
meaning of the operator, with an explanation of the change, though, as the
road here is rather convoluted, and to Andreas' point it is far easier to
understand even if it has undesirable garbage collection properties.

-Edward

_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Andreas Abel

2018-06-06 06:43:24 UTC

Permalink

I prefer the original definition

ZipList xs <|> ZipList ys = ZipList (xs ++ drop (length xs) ys)

for sake of clarity.

Post by Chris Wong
The proposed definition has one drawback: it is strict in its second
argument.
It should be possible to make it lazy in its second argument while
keeping the single-pass behavior, though. Something like this?
ZipList xs <|> ZipList ys = ZipList $ go xs ys 0
where
go [] ys n = drop n ys
go (x:xs) ys n = x : (go xs ys $! n + 1)
ZipList
<http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicative.html#ZipList>xs
<http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicative.html#local-6989586621679319881><|>
<http://hackage.haskell.org/package/base-4.11.1.0/docs/src/GHC.Base.html#%3C%7C%3E>ZipList
<http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicative.html#ZipList>ys
<http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicative.html#local-6989586621679319882>=ZipList
<http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicative.html#ZipList>(xs
<http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicative.html#local-6989586621679319881>++
<http://hackage.haskell.org/package/base-4.11.1.0/docs/src/GHC.Base.html#%2B%2B>drop
<http://hackage.haskell.org/package/base-4.11.1.0/docs/src/GHC.List.html#drop>(length
<http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Data.Foldable.html#length>xs
<http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicative.html#local-6989586621679319881>)ys
<http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicative.html#local-6989586621679319882>)
ZipList [] <|> ys = ys
xs <|> ZipList [] = xs
ZipList (x:xs) <|> ZipList (_:ys) = ZipList (x : (ZipList xs <|> ZipList ys))
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

--
Andreas Abel <>< Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

***@gu.se
http://www.cse.chalmers.se/~abela/