Haskell transforming fuction использовать foldr или foldl

Question

Я борюсь за понимание foldr и foldl, какие основные преимущества использования либо, foldl должен быть хвостом рекурсивным, но тогда что такое foldr, обычно рекурсивный?

У меня есть простая функция, которая принимает список int и возвращает сумму квадратов между первым и последним элементом.

sumSquare :: [Int] -> Int 
sumSquare xs = if length xs == 2 then sum $ map (^2) [head xs..last xs] else error "bad input" 

То, что я хочу сделать, это реализовать эту функцию с помощью foldr или foldl, я просмотрел несколько примеров, но, к сожалению, ни к чему не с ним.

Если кто-то может показать, как превратить эту функцию в один, используя либо foldr или foldl и объяснить процесс, который я был бы признателен

Answer 1

@Luis Касильяс дал хороший совет, но для ваших sumSquares:

Если вы посмотрите на типе foldr :: (a -> b -> b) -> b -> [a] -> b вы видите, что он принимает функцию (которая берет элемент, аккумулятор и возвращает новый накопитель), начальный аккумулятор и список и возвращает результирующий аккумулятор. Для foldl :: (b -> a -> b) -> b -> [a] -> b порядок аргументов отменяется.

Так sumSquares можно записать (я взял на себя смелость изменить его немного, чтобы удалить проверку длины)

sumSquare' a b = foldl (\x y -> x + (y^2)) 0 [a..b] 

sumSquare'' a b = foldr (\y x -> x + (y^2)) 0 [a..b] 

о том, как они являются рекурсивными, давайте посмотрим на то, как они определены: (для получения дополнительной информации это, есть хорошие объяснения на http://en.wikibooks.org/wiki/Haskell/List_processing и https://wiki.haskell.org/Foldr_Foldl_Foldl «)

foldl   :: (a -> b -> a) -> a -> [b] -> a 
foldl f acc []  = acc 
foldl f acc (x:xs) = foldl f (f acc x) xs 

foldr   :: (a -> b -> b) -> b -> [a] -> b 
foldr f acc []  = acc 
foldr f acc (x:xs) = f x (foldr f acc xs) 

Таким образом, оценка sumSquare' 1 3 будет (с f обозначая лямбда)

foldl f 0 [1,2,3] 
foldl f (f 0 1) [2,3] 
foldl f (f (f 0 1) 2) [3] 
foldl f (f (f (f 0 1) 2) 3) [] 
f (f (f 0 1) 2) 3 

и sumSquare'' 1 3:

foldr f 0 [1,2,3] 
f 1 (foldr f 0 [2,3]) 
f 1 (f 2 (foldr f 0 [3])) 
f 1 (f 2 (f 3 (foldr f 0 [])) 
f 1 (f 2 (f 3 0)) 

Answer 2

Несколько несовершенные правила большого пальца:

1. Не используйте foldl.
2. Если вы строите результат, который можно построить лениво, используйте foldr.
3. Если вы строите результат не может быть построено лениво, используйте foldl' с модуля Data.List.
4. Не пытайтесь использовать напрямую. Подумайте о складках как относительно низкоуровневых функциях, которые вы используете для создания многократно используемых функций, которые легче понять.

Пример точки № 4: что легче понять? Пример 1:

example1 = foldr step [] [0..] 
    where step n ns = if even n then n:ns else ns 

Пример 2:

filter :: (a -> Bool) -> [a] -> [a] 
filter p = foldr step [] 
    where step a as = if p a then a:as else as 

example2 = filter even [0..] 

Второй, конечно! Вы хотите решать проблемы, разбивая их на более мелкие проблемы и разбивая их на более мелкие проблемы. Этот процесс легче всего понять, когда складки возникают в нижней части расщепления.

Баллы №2 и №3: подумайте о разнице между sum :: Num a => [a] -> a и filter :: (a -> Bool) -> [a] -> [a]. Результатом sum является число, а результат filter - это список. В Haskell списки могут производиться и потребляться лениво, но стандартные числовые типы не могут.

Если результат, который вы создаете, это список, вы хотите использовать foldr, потому что на самом деле произойдет то, что результат будет создан лениво, поскольку список требуется. Это, например, справедливо для определения filter выше; список, составленный filter, будет производиться лениво по мере того, как его потребительские требования. Пример (с step, как в приведенном выше определении):

head (filter even [0..]) 
    = head (foldr step [] [0..]) 
    = head (step 0 (foldr step [] [1..])) 
    = head (if even 0 then 0 : foldr step [] [1..] else foldr step [] [1..]) 
    = head (if True then 0 : foldr step [] [1..] else foldr step [] [1..]) 
    = head (0 : foldr step [] [1..]) 
    = 0 

Laziness здесь означает, что оценка foldr прекращается, как только достаточно его результата производится, чтобы выяснить результат head.

Но если вы делаете sum, скорее всего, вы хотите хотите использовать foldl':

import Data.List (foldl') 

sum :: Num a => [a] -> a 
sum = foldl' (+) 0 

Поскольку нет никакого способа, чтобы потреблять несколько лениво, вы хотите использовать хвостовую рекурсию foldl' вместо. Пример:

sum [1..3] * 2 
    = foldl' (+) 0 [1..3] * 2 
    = foldl' (+) 1 [2..3] * 2 
    = foldl' (+) 3 [3..3] * 2 
    = foldl' (+) 6 [] * 2 
    = 6 * 2 
    = 12 

Но оборотная сторона, foldl' не может использовать лени как foldr может. foldl' должен пройти весь список сразу.

---

Ответить на комментарий: ну, попробуем еще раз. Первое, что я хотел бы сделать, это то, что вы пытаетесь сделать, - это плохая идея . Вы не хотите делать «3-4 вещи» в один раз. Он создает код, который трудно читать и трудно модифицировать.

Но есть способ превратить его в хороший пример. Давайте напишем вашу функцию следующим образом:

sumSquares (lo, hi) = sum $ map (^2) [lo..hi] 

Обратите внимание, что я сменил аргумент на пару. Ваш оригинал ожидает, что в списке будет ровно ровно два, что действительно говорит о том, что вы не должны использовать список, а пару (или только два аргумента).

Итак, как превратить это в набор сгибов? Первый шаг: давайте напишем sum и map в терминах складок:

sum = foldr (+) 0 
map f = foldr (\a bs -> f a : bs) [] 

Так что теперь мы можем вручную встраивать их в определение:

sumSquares (lo, hi) = foldr (+) 0 $ foldr (\a bs -> a^2 : bs) [] [lo..hi] 

Теперь вот очень полезный факт: если foldr потребляет список, произведенный другим foldr, часто бывает предохранитель два раза в один. В этом случае они сливаются с этим:

sumSquares (lo, hi) = foldr (\a bs -> a^2 + bs) 0 [lo..hi] 

Так, например:

sumSquares (1, 3) 
    = foldr (\a bs -> a^2 + bs) 0 [1..3] 
    = 1^2 + foldr (\a bs -> a^2 + bs) 0 [2..3] 
    = 1^2 + 2^2 + foldr (\a bs -> a^2 + bs) 0 [3..3] 
    = 1^2 + 2^2 + + 3^2 + foldr (\a bs -> a^2 + bs) 0 [] 
    = 1^2 + 2^2 + + 3^2 + 0 
    = 1 + 4 + 9 + 0 
    = 14 

В боковой точке, вы используете head и last в вашем коде, обратите внимание, что они также могут быть записаны в виде складок:

safeHead, safeLast :: [a] -> Maybe a 

safeHead = foldr step Nothing 
    where step a _ = Just a 

safeLast = foldr step Nothing 
    where step a Nothing = Just a 
      step _ justA = justA 

Так, чтобы решить эти проблемы в грязном, все в одной функции, как вы хотите, чтобы выписать чистые, многофункциональное решение, переводить отдельные части в складки, а затем выяснить, если и как вы можете сплавить эти складки вместе.

Но это не стоит того, чтобы заниматься новичком. Прежде всего, GHC has list fusion optimizations built in already.Таким образом, компилятор уже знает, как плавить этот код и превратить его в хорошую, тугую петлю:

foldr (+) 0 $ map (^2) [lo..hi]