ZipRev.hs

zipRev :: [a] -> [b] -> [(a,b)]
zipRev xs ys = fr where
  (fr, allbs) = go [] allbs xs ys
  
  go acc ~(b':bs') (a:as) (b:bs) = ((a,b') : res, bss)
    where
      (res, bss) = go (b:acc) bs' as bs
  go acc _ _ _ = ([], acc)

This is the re-write that I was able to track / understand what's going on:

zipRev :: [a] -> [b] -> [(a,b)]
zipRev xs ys = z where
  (z, rys) = go [] rys xs ys
  
  go acc ~(p:ps) (a:as) (b:bs) = 
      ((a,p) : res, rbs)
    where
      (        res, rbs) = go (b:acc) ps as bs
  go acc _ _ _ = ([], acc)

But, since you cut off at the first shortest xs or ys, the semantics are different: the original did

reverse $ zip (reverse xs) ys      -- edited to fix the error

while your version does

zip as (reverse bs)
  where
  (as, bs) = unzip $ zip xs ys

if I'm not mistaken. the swapping of the args is not important, but the different way of cutting them is -- when the lengths are different, that is.

@WillNess, that's almost right, but mine does

zipL as (reverse bs)
  where
  (as, bs) = unzip $ zip xs ys

zipL (x:xs) ~(y:ys) = (x,y) : zipL xs ys
zipL [] _ = []

So it can produce an infinite result (whose second components are all bottom).

it still cuts from the wrong end though. besides, if a user calls reverse, don't they want to reverse something? it's hard for me to see what could be the use case scenario... Ok, so

*Main> (as,bs) = unzip $ zip [1..] (reverse [1..]) in take 10 as

hangs, and your code wouldn't. Without being disrespectful (really), -- "so what"? I don't think I'd ever write something like that.

(edit: if reverse is there, perhaps laziness is already gone...)

Maybe as a library writer you want it to work in the most possible number of cases though, so you strive for perfection........ but yeah, it twists one's mind in all kinds of knots!

The linked Haskell Wiki article claims to aim for laziness in "cancelling" the continuations, but the result doesn't strike me as very lazy. And I think they cut it off the wrong way (relative to zipWith) and I do it right!

as always, both ways are right! as long as the user knows which way they want, they can choose. :)

Wait, what do you mean by wrong end? Look at what each one produces...

I never tried, but AFAICS, foo [1..3] [1..4] would produce two different results with your code and the one in the question. According to the high level rewrites in my first(?) comment.

yours would produce [(1,3),(2,2),(3,1)] (up to swapping) but theirs -- [(4,1),(3,2),(2,3)]. isn't it? or am I completely wrong there?

Looks like I was completely wrong there. My answer is wrong then, too. hmm. (edit: not!)

FWIW, I think you're right as a practical matter--laziness isn't a useful goal here.

wrong test case, huh! compare the results for zipRev [1..4] [10..12] with your code and theirs -- I tested my re-write, at the top of my answer, with the added clause

    .... g x c ([],t) = t

Yours produces [(1,12),(2,11),(3,10)] but the augmented theirs -- [(2,12),(3,11),(4,10)].

Not wrong then. :)

I'm too tired to think about this now. Have you tried the puzzle I set a couple months ago, to write an optimal incremental (<*) for Data.Sequence?

…

On Tue, May 14, 2019, 11:33 AM WillNess ***@***.***> wrote: wrong test case, huh. compare results for zipRev [1..4] [10..12] with your code and theirs -- I tested my re-write, at the top of my answer, with the added clause .... g x c ([],t) = t Yours produces [(1,12),(2,11),(3,10)] but the augmented theirs -- [(2,12),(3,11),(4,10)]. Not wrong then. :) — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <https://gist.github.com/3e149df5a03c3ae2e51c51277919e189?email_source=notifications&email_token=AAOOF7KUH4XVIVFD5RQIXBDPVLLUBA5CNFSM4HM2VFKKYY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAFSBIW#gistcomment-2917003>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAOOF7J6JI55YSSEHHCCRIDPVLLUBANCNFSM4HM2VFKA> .

It just aligns the lists at the wrong end:

   1   2   3   4
       12  11  10  -- OP's code
   12  11  10      -- your code

About that, could you remind me, with the link to the SO entry? I remembered something vaguely about this, recently, but couldn't remember exactly what it was...

I don't know about the SO comment, but here's the GitHub issue. Remember: the function must be incremental/lazy the way liftA2 is, and must be time and space-optimal. You will almost certainly need to mash up ideas from the internal functions aptyMiddle (which I created to implement (<*>) and later liftA2) and applicativeTree (which was created, I believe by Wasserman, to implement replicateA and thereby replicate) to accomplish this mission.

thanks, will try to see what I can do.