Skip to content

Instantly share code, notes, and snippets.

@treeowl
Created May 14, 2019 05:06
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save treeowl/3e149df5a03c3ae2e51c51277919e189 to your computer and use it in GitHub Desktop.
Save treeowl/3e149df5a03c3ae2e51c51277919e189 to your computer and use it in GitHub Desktop.
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)
@WillNess
Copy link

WillNess commented May 14, 2019

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.

@treeowl
Copy link
Author

treeowl commented May 14, 2019

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

@WillNess
Copy link

WillNess commented May 14, 2019

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!

@treeowl
Copy link
Author

treeowl commented May 14, 2019

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!

@WillNess
Copy link

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

@treeowl
Copy link
Author

treeowl commented May 14, 2019

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

@WillNess
Copy link

WillNess commented May 14, 2019

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.

@WillNess
Copy link

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?

@WillNess
Copy link

WillNess commented May 14, 2019

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

@treeowl
Copy link
Author

treeowl commented May 14, 2019

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

@WillNess
Copy link

WillNess commented May 14, 2019

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

@treeowl
Copy link
Author

treeowl commented May 14, 2019 via email

@WillNess
Copy link

WillNess commented May 14, 2019

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

@treeowl
Copy link
Author

treeowl commented May 14, 2019

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.

@WillNess
Copy link

thanks, will try to see what I can do.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment