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


на Реальный Мир Хаскелл Глава 4. Функциональное Программирование

написать foldl с foldr:

-- file: ch04/Fold.hs
myFoldl :: (a -> b -> a) -> a -> [b] -> a

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

приведенный выше код меня очень смутил, и какой-то парень позвонил dps переписал его с некоторым значимым именем, чтобы сделать его немного яснее:

myFoldl stepL zeroL xs = (foldr stepR id xs) zeroL
where stepR lastL accR accInitL = accR (stepL accInitL lastL)

один парень Jef G тогда сделал отличную работу, предоставив пример и showint основной шаг machanism шаг:

myFoldl (+) 0 [1, 2, 3]
= (foldR step id [1, 2, 3]) 0
= (step 1 (step 2 (step 3 id))) 0
= (step 1 (step 2 (a3 -> id ((+) a3 3)))) 0
= (step 1 (a2 -> (a3 -> id ((+) a3 3)) ((+) a2 2))) 0
= (a1 -> (a2 -> (a3 -> id ((+) a3 3)) ((+) a2 2)) ((+) a1 1)) 0
= (a1 -> (a2 -> (a3 -> (+) a3 3) ((+) a2 2)) ((+) a1 1)) 0
= (a1 -> (a2 -> (+) ((+) a2 2) 3) ((+) a1 1)) 0
= (a1 -> (+) ((+) ((+) a1 1) 2) 3) 0
= (+) ((+) ((+) 0 1) 2) 3
= ((0 + 1) + 2) + 3

но я все еще не могу полностью понять это, вот мои вопросы:

  1. для чего предназначена функция id? В чем заключается эта роль? Зачем он нам здесь нужен?
  2. в приведенном выше примере функция id является аккумулятором в лямбда-функции?
  3. выражения производится составляет выражения производится :: (А -> Б -> Б) -> Б -> [А] -> Б, и первый параметр-это функция для чего нужны два параметра, но функция шага в реализации myFoldl использует 3 параметра, я совершенно запутался!

кто-нибудь может мне помочь? Большое спасибо!

6 67

6 ответов:

некоторые объяснения в порядке!

для чего предназначена функция id? В чем заключается эта роль? Зачем он нам здесь нужен?

id - это функция удостоверение,id x = x, и используется как эквивалент нуля при построении цепочки функций с состав функции,(.). Вы можете найти его определено в прелюдии.

в приведенном выше примере функция id аккумулятор в лямбда-функции?

аккумулятор-это функция, которая создается с помощью повторного применения функции. Нет явной лямбды, так как мы называем аккумулятор,step. Вы можете написать его с лямбда, если вы хотите:

foldl f a bs = foldr (\b g x -> g (f x b)) id bs a

или Грэм Хаттон написал бы:


enter image description here


выражения производится по выражения производится :: (а -> б -> б) -> б -> [а] -> b

программист Haskell сказал бы, что тип на foldr и (a -> b -> b) -> b -> [a] -> b.

и первый параметр-это функция, которая нуждается в двух параметрах, но функция шага в реализации myFoldl использует 3 параметра, я полностью запутался

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

Грэм Хаттон объясняет трюк, чтобы повернуть foldl на foldr в приведенной выше статье. Начнем с записи рекурсивного определения foldl:

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

а затем рефакторинг его с помощью статического преобразования аргументов на f:

foldl :: (a -> b -> a) -> a -> [b] -> a    
foldl f v xs = g xs v
    where
        g []     v = v
        g (x:xs) v = g xs (f v x)

Давайте теперь перепишем g чтобы плавать v внутрь:

foldl f v xs = g xs v
    where
        g []     = \v -> v
        g (x:xs) = \v -> g xs (f v x)

это то же самое, что думать о g как функция одного аргумента, которая возвращает функция:

foldl f v xs = g xs v
    where
        g []     = id
        g (x:xs) = \v -> g xs (f v x)

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

но, у нас есть удобная уже очень похожая рекурсивная функция на списках,foldr!


enter image description here


это выглядит как очень похожая рекурсивная схема на наш

учитывать тип 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 = ...