1

The task is to use just one passthrough using foldr or foldl. I use this decision: 

evenOnly = fst . foldr (\x (y1, y2) -> (y2, x:y1)) ([],[])

Pretty good for finite lists. If I try evenOnly [1,2..] I'll got a fail. I know it's because of suspended caclulations, but how can I otherwise split the list or how to pass additional information about list positions or something to the calculations which begin at the end of the list?

Bakuriu
  • 98,325
  • 22
  • 197
  • 231
BarbedWire
  • 189
  • 2
  • 11
  • Possible duplicate of [foldl versus foldr behavior with infinite lists](http://stackoverflow.com/questions/3082324/foldl-versus-foldr-behavior-with-infinite-lists) – Bakuriu Mar 17 '16 at 11:16
  • Well, `foldr` works on infinite lists **provided** that the function it is applying is lazy enough. Clearly explained in [this answer](http://stackoverflow.com/a/3085516/510937). Quote: "**If** `f` is lazy in its second argument--a data constructor, for instance--the result will be incrementally lazy, with each step of the fold computed only when some part of the result that needs it is evaluated." The function you are using always uses its second argument, so it behaves "like `foldl`". – Bakuriu Mar 17 '16 at 11:19
  • Of course. I don't mean that this is the only possible solution with 'foldr'. Anyway, at the moment cannot invent something more advanced. – BarbedWire Mar 17 '16 at 11:34
  • You just have to add one character: `evenOnly = fst . foldr (\x ~(y1, y2) -> (y2, x:y1)) ([],[])`. Check this for detailed explanation:[Unzip in one pass?](http://stackoverflow.com/questions/18287848/unzip-in-one-pass) – zakyggaps Mar 17 '16 at 12:29
  • No words. Unbelievable. Thank you a lot. – BarbedWire Mar 17 '16 at 12:40

1 Answers1

2

You can use a lazy pattern ~(x1, y2):

> let evenOnly = fst . foldr (\x ~(y1, y2) -> (y2, x:y1)) ([],[])
> take 20 $ evenOnly [1..]
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40]

This is essentially the same as

> let evenOnly = fst . foldr (\x y -> (snd y, x:fst y)) ([],[])

which has the advantage of not forcing the pair constructor too early. That is, the lambda above will produce the (,) constructor in its output before it demands y (the "recursive" result).

chi
  • 111,837
  • 3
  • 133
  • 218