Написание foldl с помощью foldr

учитывать тип foldr:

foldr :: (b -> a -> a) -> a -> [b] -> a

тогда как тип step - Это что-то вроде b -> (a -> a) -> a -> a. Так как шаг передается в foldr, можно сделать вывод, что в этом случае складка имеет вид (b -> (a -> a) -> (a -> a)) -> (a -> a) -> [b] -> (a -> a).

не путайте различные значения a в разных сигнатурах; это просто переменная типа. Кроме того, имейте в виду, что стрелка функции является правой ассоциативной, поэтому a -> b -> c это то же самое как a -> (b -> c).

так, да, значение аккумулятора для foldr это функции типа a -> a, и начальное значение id. Это имеет некоторый смысл, потому что id это функция, которая ничего не делает-это та же причина, по которой вы начинаете с нуля в качестве начального значения при добавлении всех значений в список.

как step взяв три аргумента, попробуйте переписать его так:

step :: b -> (a -> a) -> (a -> a)
step x g = \a -> g (f a x)

это делает его легче увидеть, что происходит? Это занимает дополнительное время параметр, потому что он возвращает функцию, и два способа ее записи эквивалентны. Обратите внимание также на дополнительный параметр после foldr:(foldr step id xs) z. Часть в скобках-это сама складка, которая возвращает функцию, которая затем применяется к z.

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

утверждение, что foldl f z xs эквивалентно

myfoldl f z xs = foldr step_f id xs z
        where step_f x g a = g (f a x)

первое, что важно заметить здесь, это то, что правая сторона первой строки фактически оценивается как

(foldr step_f id xs) z

С foldr принимает только три параметра. Это уже намекает на то, что foldr будет вычислите не значение, а функцию карри, которая затем применяется к z. Есть два случая, чтобы исследовать, чтобы узнать, является ли myfoldl и foldl:

1. базовый случай: пустой список

     myfoldl f z []
   = foldr step_f id [] z    (by definition of myfoldl)
   = id z                    (by definition of foldr)
   = z
   
     foldl f z []
   = z                       (by definition of foldl)
   

2. непустой список

     myfoldl f z (x:xs)
   = foldr step_f id (x:xs) z          (by definition of myfoldl)
   = step_f x (foldr step_f id xs) z   (-> apply step_f)
   = (foldr step_f id xs) (f z x)      (-> remove parentheses)
   = foldr step_f id xs (f z x)
   = myfoldl f (f z x) xs              (definition of myfoldl)
   
     foldl f z (x:xs)
   = foldl f (f z x) xs
   

так как в 2. первая и последняя строка имеют одинаковую форму в обоих случаях, ее можно использовать для сворачивания списка вниз до xs == [] в случае 1. гарантирует то же самое результат. Так что по индукции,myfoldl == foldl.

^{(быстро пролистайте мои ответы [1],[2],[3],[4] чтобы убедиться, что вы понимаете синтаксис Haskell, функции более высокого порядка, каррирование, композицию функций, $ operator, операторы infix / prefix, разделы и лямбды)}

универсальное свойство fold

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

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

g []     = v              ⇒
g (x:xs) = f x (g xs)     ⇒     g = foldr f v

например:

sum []     = 0   {- recursion becomes fold -}
sum (x:xs) = x + sum xs   ⇒     sum = foldr 0 (+)

здесь v = 0 и sum (x:xs) = x + sum xs эквивалентно sum (x:xs) = (+) x (sum xs), поэтому f = (+). 2 дополнительные примеры

product []     = 1
product (x:xs) = x * product xs  ⇒  product = foldr 1 (*)

length []     = 0
length (x:xs) = 1 + length xs    ⇒  length = foldr (\_ a -> 1 + a) 0

упражнения:

1. реализовать map,filter,reverse,concat и concatMap рекурсивно, так же, как и вышеуказанные функции на левый стороне.

2. преобразуйте эти 5 функций в foldr согласно формуле выше, то есть, заменяя f и v в Формуле сгиба на право.

Foldl через foldr

Как написать рекурсивную функцию, которая суммирует цифры слева направо?

sum [] = 0     -- given `sum [1,2,3]` expands into `(1 + (2 + 3))`
sum (x:xs) = x + sum xs

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

suml :: [a] -> a
suml xs = suml' xs 0
  where suml' [] n = n   -- auxiliary function
        suml' (x:xs) n = suml' xs (n+x)

Так, стоп! Запустите этот код в GHCi и убедитесь, что вы понимаете, как он работает, а затем тщательно и вдумчиво продолжайте. suml не может быть переопределен с помощью сгиба, но suml' может быть.

suml' []       = v    -- equivalent: v n = n
suml' (x:xs) n = f x (suml' xs) n

suml' [] n = n из определения функции, правильно? И v = suml' [] из Формулы универсального свойства. Вместе это дает v n = n функция, которая сразу возвращает все, что она получает: v = id. Давайте посчитаем f:

suml' (x:xs) n = f x (suml' xs) n
-- expand suml' definition
suml' xs (n+x) = f x (suml' xs) n
-- replace `suml' xs` with `g`
g (n+x)        = f x g n

таким образом, suml' = foldr (\x g n -> g (n+x)) id и, таким образом, suml = foldr (\x g n -> g (n+x)) id xs 0.

foldr (\x g n -> g (n + x)) id [1..10] 0 -- return 55

теперь нам просто нужно обобщить, заменить + С помощью переменной функции:

foldl f a xs = foldr (\x g n -> g (n `f` x)) id xs a
foldl (-) 10 [1..5] -- returns -5

вывод

теперь читайте Грэм Хаттона учебник по универсальности и выразительности fold. Возьмите ручку и бумагу, постарайтесь понять все, что он пишет, Пока вы не получите большую часть складок самостоятельно. Не волнуйтесь, если вы чего-то не понимаете, вы всегда можете вернуться позже, но и не откладывайте много времени.

нет никакой Королевской дороги к математике, ни даже через Хаскелл. Пусть

h z = (foldr step id xs) z where   
     step x g =  \a -> g (f a x)

что это h z? Предположим, что xs = [x0, x1, x2].
Примените определение foldr:

h z = (step x0 (step x1 (step x2 id))) z 

применить определение шага:

= (\a0 -> (\a1 -> (\a2 -> id (f a2 x2)) (f a1 x1)) (f a0 x0)) z

подставить в лямбда-функции:

= (\a1 -> (\a2 -> id (f a2 x2)) (f a1 x1)) (f z x0)

= (\a2 -> id (f a2 x2)) (f (f z x0) x1)

= id (f (f (f z x0) x1) x2)

применить определение id:

= f (f (f z x0) x1) x2

применить определение foldl :

= foldl f z [x0, x1, x2]

это королевская дорога или что?

Это может помочь, я попытался расширить различными способами.

myFoldl (+) 0 [1,2,3] = 
foldr step id [1,2,3] 0 = 
foldr step (\a -> id (a+3)) [1,2] 0 = 
foldr step (\b -> (\a -> id (a+3)) (b+2)) [1] 0 = 
foldr step (\b -> id ((b+2)+3)) [1] 0 = 
foldr step (\c -> (\b -> id ((b+2)+3)) (c+1)) [] 0 = 
foldr step (\c -> id (((c+1)+2)+3)) [] 0 = 
(\c -> id (((c+1)+2)+3)) 0 = ...