Написание складок с использованием foldr

Ответ 1

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

Для чего предназначена функция 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) [ ]

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

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

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

Напротив, невозможно переопределить fold в терминах foldl, из-за того, что foldl является строгим в хвосте аргумента списка, но fold is not. Существует ряд полезных "теорем двойственности" относительно 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). В Haskell оператор fold для списков может быть определен следующим образом:

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

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

Это похоже на очень похожую рекурсивную схему нашей g функции. Теперь трюк: используя всю доступную магию под рукой (так же, как Bird, Meertens и Malcolm), мы применяем специальное правило, универсальное свойство fold, которое является эквивалентом двух определений для функции 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)

Из наших ранних конструкций foldl мы знаем 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 для каждого элемента списка, в обратном порядке (поэтому мы складываем левый, а не правый).

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

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

• Haskell Wiki: Foldl as foldr
• Учебник по универсальности и выразительности складок, Грэм Хаттон, Дж. Функциональное программирование 9 (4): 355-372, июль 1999 г.
• Малкольм, Г. Алгебраические типы данных и преобразование программ. , Кандидатская диссертация, Университет Гронингена.

Ответ 2

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

Ответ 3

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

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

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

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

Упражнение:

• Решите map, filter, reverse, concat и concatMap рекурсивно, как и приведенные выше функции с левой стороны.

• Преобразуйте эти 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

Заключение

Теперь читайте Graham Hutton Учебник по универсальности и выразительности fold. Возьмите ручку и бумагу, попытайтесь понять все, что он пишет, до тех пор, пока вы не получите большую часть складок самостоятельно. Не потейте, если вы что-то не понимаете, вы всегда можете вернуться позже, но не откладывайте много.

Ответ 4

Здесь мое доказательство того, что 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:

• Базовый регистр: пустой список

    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)
  

• Непустой список

    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.

Ответ 5

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

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]

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

Ответ 6

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

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 = ...

Ответ 7

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)

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