Это моя take версия с использованием 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]
Вывод не тот, что я ожидаю:
[3,4]
Затем я попытался отладить, вставив длину y в себя, и результат был таким:
[3,2,1,0]
Я не понимаю, почему длины вставляются в порядке убывания. Может быть, я пропустил что-то очевидное?
Если вы хотите реализовать take с помощью foldr, вам нужно имитировать обход списка слева направо. Смысл в том, чтобы заставить функцию складывания зависеть от дополнительного аргумента, который кодирует нужную вам логику, а не только от свернутого хвоста списка.
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)
Здесь foldr возвращает функцию, которая принимает числовой аргумент и проходит по списку слева направо, беря из него требуемую сумму. Это также будет работать с бесконечными списками из-за лени. Как только дополнительный аргумент достигнет нуля, foldr замкнется и вернет пустой список.
foldr применит функцию step, начиная с *последних элементов**. То есть,
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]
Длины «вставляются» в порядке убывания, поскольку : является операцией в начале. Длины большей длины добавляются в начало списка.
(Изображение взято с http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29)
*: Для простоты мы предполагаем, что каждая операция является строгой, что верно в реализации OP step.
foldr применит функцию step, начиная с последних элементов. Это утверждение в лучшем случае вводит в заблуждение перед лицом ленивой оценки. На самом деле Haskell оценивает ваше второе дерево слева направо, и если функция step не является строгой для своего второго аргумента, она может преждевременно прервать вычисления. Простейшим примером этого является safeHead = foldr (\x _ -> Just x) Nothing.
- person Luis Casillas; 08.04.2013
step, тот, у которого 1 является первым аргументом. Если step не нуждается во втором аргументе, то вычисления на этом заканчиваются до того, как будут просмотрены остальные элементы списка. Если step x _ = Just x, то foldr step Nothing [1,2,3,4] == step 1 (foldr step Nothing [2,3,4]) == Just 1.
- person Luis Casillas; 08.04.2013
step из вопроса является строгим во втором аргументе, поэтому в этом случае foldr не имеет другого выбора, кроме как работать с конца списка вперед, и для оценки самых внешних step сначала должны быть внутренние step оценивается. В ответе было бы полезно пояснить, что это особая ситуация, но описание верно для данного кода.
- person Daniel Fischer; 08.04.2013
Другие ответы до сих пор делают это слишком сложным, потому что они кажутся чрезмерно привязанными к понятию, что foldr работает «справа налево». В каком-то смысле это так, но Haskell — ленивый язык, поэтому вычисление «справа налево», использующее шаг ленивой кратности, будет фактически выполняться слева направо по мере использования результата.
Изучите этот код:
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..]
