Make <|> for ZipLists lazy for infinite lists - Libraries - Haskell.org

newer
Proposal: Add Foldable1 from...

Make <|> for ZipLists lazy for infinite lists

older
Package take over: eigen

박신환

4 Jun 2018 4 Jun '18

11:36 p.m.

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))

Attachments:

attachment.html (text/html — 4.3 KB)

Reply

Sign in to reply online Use email software

Show replies by date

Ivan Lazar Miljenovic

5 Jun 5 Jun

12:33 a.m.

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. On 5 June 2018 at 13:36, 박신환 wrote:

Current definion of (<|>) for ZipLists:

ZipList http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ... xs http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ... <|> http://hackage.haskell.org/package/base-4.11.1.0/docs/src/GHC.Base.html#%3C%... ZipList http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ... ys http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ... = ZipList http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ... (xs http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ... ++ http://hackage.haskell.org/package/base-4.11.1.0/docs/src/GHC.Base.html#%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... xs http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ...) ys http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ...)

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))

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

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

Reply

Sign in to reply online Use email software

Chris Wong

3 a.m.

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) On Tue, Jun 5, 2018, 15:36 박신환 wrote:

Current definion of (<|>) for ZipLists:

ZipList http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ... xs http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ... <|> http://hackage.haskell.org/package/base-4.11.1.0/docs/src/GHC.Base.html#%3C%... ZipList http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ... ys http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ... = ZipList http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ... (xs http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ... ++ http://hackage.haskell.org/package/base-4.11.1.0/docs/src/GHC.Base.html#%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... xs http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ...) ys http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ...)

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))

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

Reply

Sign in to reply online Use email software

Andreas Abel

6 Jun 6 Jun

2:43 a.m.

I prefer the original definition ZipList xs <|> ZipList ys = ZipList (xs ++ drop (length xs) ys) for sake of clarity. On 05.06.2018 09:00, Chris Wong wrote:

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)

On Tue, Jun 5, 2018, 15:36 박신환 mailto:ndospark320@naver.com> wrote:

Current definion of (<|>) for ZipLists:

ZipList http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ...xs http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ...<|> http://hackage.haskell.org/package/base-4.11.1.0/docs/src/GHC.Base.html#%3C%...ZipList http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ...ys http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ...=ZipList http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ...(xs http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ...++ http://hackage.haskell.org/package/base-4.11.1.0/docs/src/GHC.Base.html#%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...xs http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ...)ys http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ...)

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))

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

_______________________________________________ Libraries mailing list Libraries@haskell.org 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 andreas.abel@gu.se http://www.cse.chalmers.se/~abela/

Reply

Sign in to reply online Use email software

Edward Kmett

4:39 a.m.

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 On Tue, Jun 5, 2018 at 3:00 AM, Chris Wong wrote:

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)

On Tue, Jun 5, 2018, 15:36 박신환 wrote:

...
Current definion of (<|>) for ZipLists:

ZipList http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ... xs http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ... <|> http://hackage.haskell.org/package/base-4.11.1.0/docs/src/GHC.Base.html#%3C%... ZipList http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ... ys http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ... = ZipList http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ... (xs http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ... ++ http://hackage.haskell.org/package/base-4.11.1.0/docs/src/GHC.Base.html#%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... xs http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ...) ys http://hackage.haskell.org/package/base-4.11.1.0/docs/src/Control.Applicativ...)

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))

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

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

Reply

Sign in to reply online Use email software

2540

Age (days ago)

2541

Last active (days ago)

Download

4 comments

5 participants

tags

participants (5)

Andreas Abel
Chris Wong
Edward Kmett
Ivan Lazar Miljenovic
박신환