Написание фолдла с использованием фолдра

В реальном мире Haskell, глава 4. Функциональное программирование

Напишите фолд с фолд:

-- 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)

Один парень, Джеф Г, тогда проделал отличную работу, шаг за шагом предоставив пример и продемонстрировав основной механизм:

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. Прототип foldr - это foldr:: (a -> b -> b) -> b -> [a] -> b , и первый параметр - это функция, для которой нужны два параметра, но в шаговой функции в реализации myFoldl используются 3 параметра Я совершенно сбит с толку!

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

Источник

10 ответов

Решение

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

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

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

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

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

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

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

5.1 foldl оператор

Теперь давайте обобщим из suml пример и рассмотрим стандартный оператор foldl который обрабатывает элементы списка в порядке слева направо, используя функцию f объединить значения и значение v в качестве начального значения:

foldl :: (β → α → β) → β → ([α] → β)
foldl f v [ ] = v
foldl f v (x : xs) = foldl f (f v x) xs

Используя этот оператор, suml может быть переопределено просто suml = foldl (+) 0, Многие другие функции могут быть определены простым способом, используя foldl, Например, стандартная функция reverse можно переопределить с помощью foldl следующее:

reverse :: [α] → [α]
reverse = foldl (λxs x → x : xs) [ ]

Это определение более эффективно, чем наше первоначальное определение с использованием сгиба, потому что оно избегает использования неэффективного оператора добавления (++) для списков.

Простое обобщение расчета в предыдущем разделе для функции suml показывает, как переопределить функцию foldl с точки зрения fold:

foldl f v xs = fold (λx g → (λa → g (f a x))) id xs v

В отличие от этого, невозможно переопределить fold с точки зрения foldl, благодаря тому факту, что foldl строг в хвосте своего аргумента списка, но fold не является. Существует ряд полезных "теорем двойственности", касающихся fold а также foldl а также некоторые руководящие принципы для определения того, какой оператор лучше всего подходит для конкретных приложений (Bird, 1998).

прототипом foldr является foldr:: (a -> b -> b) -> b -> [a] -> b

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

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

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

Грэм Хаттон объясняет хитрость 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!

2 оператор сгиба

fold оператор берет свое начало в теории рекурсии (Kleene, 1952), в то время как использование fold как центральная концепция языка программирования восходит к оператору редукции APL (Iverson, 1962), а позже к оператору вставки FP (Backus, 1978). В Хаскеле fold Оператор для списков может быть определен следующим образом:

fold :: (α → β → β) → β → ([α] → β)
fold f v [ ] = v
fold f v (x : xs) = f x (fold f v xs)

То есть, учитывая функцию f типа α → β → β и значение v типа β, функция fold f v обрабатывает список типов [α] дать значение типа β заменив нулевой конструктор [] в конце списка по значению v и каждый минус конструктор (:) в списке по функции f, Таким образом, fold Оператор инкапсулирует простой шаблон рекурсии для обработки списков, в котором два конструктора для списков просто заменяются другими значениями и функциями. Ряд знакомых функций в списках имеет простое определение, используя fold,

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

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

если и только если

g = fold f v

Итак, универсальное свойство складок гласит:

    g = foldr k v

где g должно быть эквивалентно двум уравнениям, для некоторых k а также v:

    g []     = v
    g (x:xs) = k x (g xs)

Из наших более ранних сгибов мы знаем v == id, Для второго уравнения, однако, нам нужно вычислить определение k:

    g (x:xs)         = k x (g xs)        
<=> g (x:xs) v       = k x (g xs) v      -- accumulator of functions
<=> g xs (f v x)     = k x (g xs) v      -- definition of foldl
<=  g' (f v x)       = k x g' v          -- generalize (g xs) to g'
<=> k = \x g' -> (\a -> g' (f v x))      -- expand k. recursion captured in g'

Который, подставляя наши расчетные определения k а также v дает определение foldl как:

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

Рекурсивный g заменяется комбинатором Foldr, и аккумулятор становится функцией, построенной через цепочку композиций f в каждом элементе списка в обратном порядке (чтобы мы свернули влево, а не вправо).

Это определенно несколько продвинуто, поэтому для глубокого понимания этого преобразования, универсального свойства сгибов, которое делает возможным преобразование, я рекомендую учебное пособие Хаттона, приведенное ниже.

Рекомендации

Источник

Рассмотрим тип 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

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

Источник

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

Универсальное свойство сгиба

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

По сути, если ваша рекурсивная функция работает со списками, похожими на левые, вы можете преобразовать ее, чтобы сложить одну вправо, подставив 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 функций в сложение в соответствии с формулой выше, то есть подставляя 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

Заключение

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

Источник

Нет никакой Королевской Дороги к Математике, ни даже через Haskell. Позволять

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 f z [x0, x1, x2]

Это Royal Road или что?

Источник

Прежде чем голосовать против, прочтите следующий абзац.

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

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

Мой долгий путь к пониманию этого простого упражнения

Легкая часть: что нам нужно определить?

Что происходит в следующем примере вызова

foldl f z [1,2,3,4]

можно визуализировать с помощью следующей диаграммы (которая есть в Википедии, но я впервые увидел ее в другом ответе):

          _____results in a number
         /
        f          f (f (f (f z 1) 2) 3) 4
       / \
      f   4        f (f (f z 1) 2) 3
     / \
    f   3          f (f z 1) 2
   / \
  f   2            f z 1
 / \
z   1

(В качестве примечания, при использовании foldl каждое приложение fне выполняется, и выражения обрабатываются так, как я написал их выше; в принципе, их можно вычислить, двигаясь снизу вверх, и это именно то, чтоfoldl' делает.)

По сути, это упражнение заставляет нас использовать foldr вместо того foldl соответствующим образом изменив ступенчатую функцию (поэтому мы используем s вместо того f) и начальный аккумулятор (поэтому мы используем ? вместо того z); список остается прежним, иначе о чем мы говорим?

Призыв к foldr должен выглядеть так:

foldr s ? [1,2,3,4]

и соответствующая диаграмма такова:

    _____what does the last call return?
   /
  s
 / \
1   s
   / \
  2   s
     / \
    3   s
       / \
      4   ? <--- what is the initial accumulator?

Звонок приводит к

s 1 (s 2 (s 3 (s 4 ?)))

Что s а также ?? А какие у них виды? Это выглядит какs это функция с двумя аргументами, очень похожая на f, но не будем торопиться с выводами. Также оставим? в сторону, и давайте заметим, что z должен вступить в игру, как только 1вступает в игру; однако как можноz вступить в игру в призыве к аргументу может быть два s функция, а именно в вызове s 1 (…)? Мы можем решить эту часть загадки, выбравs который принимает 3 аргумента, а не 2, о которых мы упоминали ранее, так что самый внешний вызов s 1 (…) приведет к функции, принимающей один аргумент, который мы можем передать z к!

Это означает, что нам нужен исходный вызов, который расширяется до

f (f (f (f z 1) 2) 3) 4

быть эквивалентным

s 1 (s 2 (s 3 (s 4 ?))) z

или, другими словами, мы хотим, чтобы частично примененная функция

s 1 (s 2 (s 3 (s 4 ?)))

быть эквивалентным следующей лямбда-функции

(\z -> f (f (f (f z 1) 2) 3) 4)

Опять же, "единственные" части, которые нам нужны, это s а также ?.

Поворотный момент: распознать состав функций

Давайте перерисуем предыдущую диаграмму и напишем справа, что мы хотим, чтобы каждый вызов s быть эквивалентным:

  s          s 1 (…) == (\z -> f (f (f (f z 1) 2) 3) 4)
 / \
1   s        s 2 (…) == (\z -> f (f (f    z    2) 3) 4)
   / \
  2   s      s 3 (…) == (\z -> f (f       z       3) 4)
     / \
    3   s    s 4  ?  == (\z -> f          z          4)
       / \
      4   ? <--- what is the initial accumulator?

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

Также должно быть ясно, что вызов s с аргументами x а также y является (полным) применением y к частичному применению f к единственному аргументу x. Поскольку частичное применениеf к x можно записать как лямбда (\z -> f z x), полностью применяя y к нему приводит лямбда (\z -> y (f z x)), который в этом случае я бы переписал как y . (\z -> f z x); перевод слов в выражение дляs мы получили

s x y = y . (\z -> f z x)

(Это то же самое, что и s x y z = y (f z x), который совпадает с книгой, если вы переименуете переменные.)

Последний бит: каково начальное "значение"?аккумулятора? Приведенную выше диаграмму можно переписать, расширив вложенные вызовы, чтобы сделать их композиционными цепочками:

  s          s 1 (…) == (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2) . (\z -> f z 1)
 / \
1   s        s 2 (…) == (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2)
   / \
  2   s      s 3 (…) == (\z -> f z 4) . (\z -> f z 3)
     / \
    3   s    s 4  ?  == (\z -> f z 4)
       / \
      4   ? <--- what is the initial accumulator?

Мы здесь видим, что s просто "нагромождает" последовательные частичные применения f, но y в s x y = y . (\z -> f z x) предполагает, что интерпретация s 4 ? (и, в свою очередь, все остальные) пропускает ведущую функцию, которая должна быть составлена ​​с самой левой лямбдой.

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

  s          s 1 (…) == id . (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2) . (\z -> f z 1)
 / \
1   s        s 2 (…) == id . (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2)
   / \
  2   s      s 3 (…) == id . (\z -> f z 4) . (\z -> f z 3)
     / \
    3   s    s 4 id  == id . (\z -> f z 4)
       / \
      4   id

Итак, искомая функция

myFoldl f z xs = foldr (\x g a -> g (f a x)) id xs z
Источник

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

Начав с небольшого примера, ключевой вывод состоит в том, чтобы заметить, что и действия в коротком списке можно соответственно переписать как

      foldr f z [a, b, c]
    == a `f` (b `f` (c `f` z))
    == (a `f`) . (b `f`) . (c `f`) $ z
    == (f a) . (f b) . (f c) $ z

и

      foldl f z [a, b, c]
    == ((z `f` a) `f` b) `f` c
    == (`f` c) . (`f` b) . (`f` a) $ z
    == ((flip f) c) . ((flip f) b) . ((flip f) a) $ z

Обратите внимание, что основное отличие состоит в том, чтоfперевернут, и порядок композиции обратный.

Обычно мы думаем о сворачивании как о «обработке списка»; изменение точки зрения, за которое я выступаю, заключается в том, что вместо этого мы рассматриваем их как построение композиции функций, параметризованной списком .

Начнем с кажущегося отступления.

Простая композиция

Если у нас есть список функций, мы можем скомпоновать их все вместе и получить новую функцию. Реализация достаточно проста с точки зрения:

      compose :: [a -> a] -> (a -> a)
compose = foldr (.) id

Если мы когда-нибудь захотим скомпоновать их в обратном порядке, мы, конечно, можем связать их в цепочку.compose . reverse, но в качестве альтернативы мы можем напрямую определить операцию с, перевернув(.):

      composeRev :: [a -> a] -> (a -> a)
composeRev = foldr (flip (.)) id

Параметризованная композиция

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

      compMap :: (b -> (a -> a)) -> [b] -> (a -> a)
compMap f = compose . map f

Опять же, это можно реализовать напрямую с помощью as

      compMap f = foldr (\x chain -> f x . chain) id
          = foldr ((.) . f) id

Аналогично, чтобы составить обратную композицию, мы можем либо сделать

      compMapRev :: (b -> (a -> a)) -> [b] -> (a -> a)
compMapRev f = composeRev . map f
             = compose . map f . reverse
             = compMap f . reverse

или напишите это с нуля в терминах as

      compMapRev f = foldr (\x chain -> chain . f x) id
             = foldr ((flip (.)) . f) id

Вернуться к складыванию

Оглядываясь назад на наши первоначальные небольшие примеры, мы можем почувствовать, что между / и / существует сильная связь.

Сходство между и станет более очевидным, если мы выровняем их сигнатуры типов:

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

Мы сразу понимаем, чтоfoldrиcompMapпросто поменяйте местами второй и третий аргументы, т.е.foldr f == flip (compMap f), то естьfoldr == flip . compMap.

Давайте посмотрим, сможем ли мы сделать то же самое сfoldl. На этот раз мы должны не забыть сравнить его сcompMapRevвместо этого, потому что порядок композиции должен быть таким же:

      foldl      :: (a ->  b -> a)  ->  a  -> [b] -> a
compMapRev :: (b -> (a -> a)) -> [b] ->  a  -> a

Помимо замены второго и третьего аргументов, на этот раз также переворачивается первый аргумент функции, т.е.foldl f == flip (compMapRev (flip f)), то естьfoldl == flip . compMapRev . flip.

Из предыдущих наблюдений следует, что выполняются следующие тождества:

      foldr f z list =  compMap f list z
               == foldr ((.) . f) id list z -- does not work as a recursive definition

      foldl f z list = compMapRev (flip f) list z
               = foldr ((flip (.)) . (flip f)) id list z

Это последнее, что мы искали все время.

Мы также можем упростить и согласовать две идентичности, чтобы подчеркнуть сходство:

      foldr f == flip $ foldr (      (.)  .       f ) id -- does not work as a definition
foldl f =  flip $ foldr ((flip (.)) . (flip f)) id
Источник

Это может помочь, я попытался расширить по-другому.

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 = ...
Источник 
foldr step zero (x:xs) = step x (foldr step zero xs)
foldr _ zero []        = zero

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

myFold (+) 0 [1, 2, 3] =
  foldr step id [1, 2, 3] 0
  -- Expanding foldr function
  step 1 (foldr step id [2, 3]) 0
  step 1 (step 2 (foldr step id [3])) 0
  step 1 (step 2 (step 3 (foldr step id []))) 0
  -- Expanding step function if it is possible
  step 1 (step 2 (step 3 id)) 0
  step 2 (step 3 id) (0 + 1)
  step 3 id ((0 + 1) + 2)
  id (((0 + 1) + 2) + 3)

Ну, по крайней мере, это помогло мне. Даже это не совсем верно.

Источник

Этот ответ позволяет легко понять приведенное ниже определение за три шага.

-- 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)

Шаг 1. Преобразуйте кратность оценки функции в комбинацию функций

foldl f z [x1 .. xn] = z & f1 & .. & fn = fn . .. . f1 z. в которомfi = \z -> f z xi.

(Используя z & f1 & f2 & .. & fn это означает fn ( .. (f2 (f1 z)) .. ).)

Шаг 2. выразите комбинацию функций в виде foldr манера

foldr (.) id [f1 .. fn] = (.) f1 (foldr (.) id [f2 .. fn]) = f1 . (foldr (.) id [f2 .. fn]). Разверните остальное, чтобы получитьfoldr (.) id [f1 .. fn] = f1 . .. . fn.

Заметив, что последовательность обратная, мы должны использовать обратную форму (.). Определитьrc f1 f2 = (.) f2 f1 = f2 . f1, тогда foldr rc id [f1 .. fn] = rc f1 (foldr (.) id [f2 .. fn]) = (foldr (.) id [f2 .. fn]) . f1. Разверните остальное, чтобы получитьfoldr rc id [f1 .. fn] = fn . .. . f1.

Шаг 3. Преобразуйте свертку в списке функций в свертку в списке операндов.

найти step что делает foldr step id [x1 .. xn] = foldr rc id [f1 .. fn]. Легко найтиstep = \x g z -> g (f z x).

За 3 шага определение foldl с помощью foldr чисто:

  foldl f z xs
= fn . .. . f1 z
= foldr rc id fs z
= foldr step id xs z

Докажите правильность:

foldl f z xs = foldr (\x g z -> g (f z x)) id xs z
             = step x1 (foldr step id [x2 .. xn]) z
             = s1 (foldr step id [x2 .. xn]) z
             = s1 (step x2 (foldr step id [x3 .. xn])) z
             = s1 (s2 (foldr step id [x3 .. xn])) z
             = ..
             = s1 (s2 (.. (sn (foldr step id [])) .. )) z
             = s1 (s2 (.. (sn id) .. )) z
             = (s2 (.. (sn id) .. )) (f z x1)
             = s2 (s3 (.. (sn id) .. )) (f z x1)
             = (s3 (.. (sn id) .. )) (f (f z x1) x2)
             = ..
             = sn id (f (.. (f (f z x1) x2) .. ) xn-1)
             = id (f (.. (f (f z x1) x2) .. ) xn)
             = f (.. (f (f z x1) x2) .. ) xn

in which xs = [x1 .. xn], si = step xi = \g z -> g (f z xi)

Если вы обнаружите, что что-то неясно, добавьте комментарий.:)

Источник
Другие вопросы по тегам