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?

Aldoaldol

Answer 1

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.

Wellknit

Answer 2

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.

Negotiate

"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. – Indention

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

@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 steps 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. – Bibbie

Answer 3

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

Indention