Implementing take using foldr

Question

This is my take version using foldr:

myTake n list = foldr step [] list
                where step x y | (length y) < n = x : y
                               | otherwise = y

main = do print $ myTake 2 [1,2,3,4]

The output is not what I expect:

[3,4]

I then tried to debug by inserting the length of y into itself and the result was:

[3,2,1,0]

I don't understand why the lengths are inserted in decreasing order. Perhaps something obvious I missed?

is7s · Accepted Answer · 2013-04-09T08:02:26.630

If you want to implement take using foldr you need to simulate traversing the list from left to right. The point is to make the folding function depend on an extra argument which encodes the logic you want and not only depend on the folded tail of the list.

take :: Int -> [a] -> [a]
take n xs = foldr step (const []) xs n
  where
    step x g 0 = []
    step x g n = x:g (n-1)

Here, foldr returns a function which takes a numeric argument and traverses the list from left to right taking from it the amount required. This will also work on infinite lists due to laziness. As soon as the extra argument reaches zero, foldr will short-circuit and return an empty list.

kennytm · Answer 2 · 2013-04-09T07:50:48.003

12

Visualization of <code>foldr</code>

foldr will apply the function step starting from the *last elements**. That is,

foldr step [] [1,2,3,4] == 1 `step` (2 `step` (3 `step` (4 `step` [])))
                        == 1 `step` (2 `step` (3 `step` (4:[])))
                        == 1 `step` (2 `step (3:4:[]))   -- length y == 2 here
                        == 1 `step` (3:4:[])
                        == 3:4:[]
                        == [3, 4]

The lengths are "inserted" in decreasing order because : is a prepending operation. The longer lengths are added to the beginning of the list.

_{(Image taken from http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29)}

*: For simplicity, we assume every operation is strict, which is true in OP's step implementation.

edited Apr 09 '13 at 07:50

answered Apr 08 '13 at 13:20

kennytm

510,854
105
1,084
1,005

"`foldr` will apply the function `step` starting from the *last elements*." This statement is, at best, very misleading in the face of lazy evaluation. Haskell in fact evaluates your second tree from left to right, and if the `step` function is not-strict on its second argument, it may abort computation early. The simplest example of this is `safeHead = foldr (\x _ -> Just x) Nothing`. – Luis Casillas Apr 08 '13 at 17:22
I should add that your sequence of evaluation steps is going from inner function applications to outer ones, which is the *opposite* order from what Haskell does. The outermost `step` is evaluated first, the one with `1` as its first argument. If `step` doesn't need its second argument, then computation ends there, before it looks at the rest of the list's elements. If `step x _ = Just x`, then `foldr step Nothing [1,2,3,4] == step 1 (foldr step Nothing [2,3,4]) == Just 1`. – Luis Casillas Apr 08 '13 at 17:36
3

@sacundim But the `step` from the question is strict in its second argument, so in this case `foldr` has no choice but to work from the end of the list to the front, and to evaluate the outermost `step`, first the inner `step`s have to be evaluated. The answer would benefit from making it clear that it's a special situation, but the description is correct for the given code. – Daniel Fischer Apr 08 '13 at 19:11

score 9 · Answer 3 · edited Jun 22 '13 at 19:33

The other answers so far are making it much too complicated, because they seem excessively wedded to the notion that foldr works "from right to left." There is a sense in which it does, but Haskell is a lazy language, so a "right to left" computation that uses a lazy fold step will actually be executed from left to right, as the result is consumed.

Study this code:

take :: Int -> [a] -> [a]
take n xs = foldr step [] (tagFrom 1 xs)
    where step (a, i) rest
               | i > n     = []
               | otherwise = a:rest

tagFrom :: Enum i => i -> [a] -> [(a, i)]
tagFrom i xs = zip xs [i..]

Implementing take using foldr

3 Answers3

Linked