Make <|> for ZipLists lazy for infinite lists

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Make <|> for ZipLists lazy for infinite lists

박신환

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

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Make <|> for ZipLists lazy for infinite lists

Ivan Lazar Miljenovic
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, 박신환 <[hidden email]> wrote:

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

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




--

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Make <|> for ZipLists lazy for infinite lists

Chris Wong-2
In reply to this post by 박신환
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 박신환 <[hidden email]> wrote:

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))
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Make <|> for ZipLists lazy for infinite lists

Andreas Abel-2
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 박신환 <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Current definion of (<|>) for ZipLists:
>
>     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>)
>
>     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
>     [hidden email] <mailto:[hidden email]>
>     http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> 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

[hidden email]
http://www.cse.chalmers.se/~abela/
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Make <|> for ZipLists lazy for infinite lists

Edward Kmett-2
In reply to this post by Chris Wong-2
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 <[hidden email]> 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 박신환 <[hidden email]> wrote:

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))
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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



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