Discussion:
Make <|> for ZipLists lazy for infinite lists
(too old to reply)
박신환
2018-06-05 03:36:34 UTC
Permalink
Current definion of (<|>) for ZipLists:
ZipList xs <|> ZipList ys = ZipList (xs ++ drop (length xs) ys)

doesn't work if the left argument is infinite. It should be:

ZipList [] <|> ys = ys
xs <|> ZipList [] = xs
ZipList (x:xs) <|> ZipList (_:ys) = ZipList (x : (ZipList xs <|> ZipList ys))
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)
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
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
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
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/
Loading...