Хорошо, поскольку никто из наших постоянных экспертов по Хаскеллу еще не подошел, чтобы объяснить это, я подумал, что мне пора.Пожалуйста, всем, не стесняйтесь исправлять все, что вы видите неправильно, потому что я действительно просто чувствую свой путь к ответу здесь, и следующее по своей природе будет немного бессвязным.
Во-первых, как всегда вHaskell, неплохо бы взглянуть на типы:
Prelude> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
Так как нас интересуют только списки, а не общие Foldable s, давайте специализируемся на:
foldl :: (b -> a -> b) -> b -> [a] -> b
и сравните с функцией, которую вам дали:
foldlTest:: (b -> a -> b) -> [a] -> (b -> b)
Поскольку функции Haskell каррированы, это еще один способ сказать, что -> стрелки в сигнатурах типов ассоциативно справа, последняя парав скобках нет необходимости, так что это то же самое, что и:
foldlTest:: (b -> a -> b) -> [a] -> b -> b
По сравнению с foldl выше, мы видим, что они идентичны, за исключением того факта, что два последних параметра - [a] и b - перевернуты.
Таким образом, мы уже можем наблюдать, что библиотечная функция foldl принимает функцию сгиба, начальный аккумулятор и список длясложить, чтобы создать новый аккумулятор, версия foldlTest принимает функцию складывания, список, чтобы сложить, и стартовый аккумулятор, чтобы произвести новый аккумулятор.Это звучит как то же самое, что и есть, но если теперь мы снова введем пару скобок, которые я снял несколько шагов назад, мы увидим, что foldlTest в той форме, которую вы показали, можно рассматривать как:
взятие функции сгиба и списка и создание функции b -> b, которая описывает, как свертывание по списку превращает первоначальный аккумулятор в конечный результат .
Обратите внимание, в частности, что в этой формулировке она действительно является функцией.
Итак, теперь мы готовы взглянуть на фактическую реализацию, которую вы видели:
foldlTest f xs = foldr (\x r b -> r (f b x))
(\b -> b)
xs
Я буду первым, кто признает, что это довольно сложно, даже запутанно.Как всегда, давайте рассмотрим типы.
Типы ввода просты.Из приведенного выше обсуждения мы знаем, что f имеет тип b -> a -> b, а xs имеет тип [a].
ОК, а как насчет этой лямбды?Давайте рассмотрим это поэтапно:
- Требуется 3 аргумента,
x, r и b, в этом порядке. - Результат вызова функции равен
r (f b x).Это уже многое говорит нам, если мы сядем и подумаем об этом! - Для одного мы знаем, что
f имеет тип b -> a -> b, поэтому из f b x мы знаем, что b имеет тип b и x имеют тип a. - Что касается
r, мы видим, что это должна быть функция, потому что она применяется к f b x.И мы знаем, что последний имеет тип b (из сигнатуры типа f).Так что r имеет тип b -> c, для некоторого типа c. - Поэтому наша сложная лямбда-функция имеет тип
a -> (b -> c) -> b -> c, где c - это какой-то тип, который мы еще не определили. - Теперь наступает ключевой момент.Эта лямбда представляется как первый аргумент (функция сгиба) функции
foldr.Следовательно, он должен иметь тип d -> e -> e, для некоторых типов d и e. - Помните, что функции каррируются, и, хотя кажется, что сигнатура лямбды принимает 3 аргумента, мы можем уменьшить ее до2, переписав как
a -> (b -> c) -> (b -> c).Это точное соответствие для сигнатуры, которую мы знаем, foldr ищет, с d, равным a и e, равным b -> c.
И это мы специализируемся foldr подпись, так что он принимает этот тип функции, мы находим, что это:
foldr :: (a -> (b -> c) -> (b -> c)) -> (b -> c) -> [a] -> (b -> c)`
Мы до сих пор не знаем, что такое c, но нам не нужно долго удивляться.Выше приведена подпись для фолда, который просматривает список a с и выдает функцию от b до c.Следующий аргумент foldr, который имеет тип b -> c, задается (реализацией, которую мы пытаемся расшифровать) как \b -> b.Конечно, это просто функция тождества, и, что самое главное, это функция от типа к себе.Таким образом, тип b -> c на самом деле должен быть b -> b, или, другими словами, c всегда был таким же, как b!
Так что лямбда должна иметь следующий тип:
a -> (b -> b) -> (b -> b)
Он принимает a и эндоморфизм в b (это просто означает функцию из b в себя) и возвращает другой эндоморфизм в b.И с помощью этой функции мы свернем список a с, взяв в качестве отправной точки функцию тождественности, чтобы создать эндоморфизм b -> b, который будет реализовывать левый сгиб, за которым мы следуем.
Указанная выше сигнатура типа сама по себе не дает нам большого представления о том, как ее реализовать, учитывая, что a и b могут быть чем угодно.Тем не менее, у нас есть наша функция f, которая связывает их - напомним, что она принимает b и a и производит b.Учитывая, что (отменив карри снова), приведенная выше функция требует от нас, учитывая a, b -> b и b, чтобы создать еще один b, я могу видеть только два нетривиальных способачтобы сделать это:
- примените функцию к
b, затем примените f к a и результату. - примените
f к a и b, затем примените функцию b -> b к результату
Второе из этих двух - именно то, что делает та лямбда, о которой вы спрашиваете, как мы надеемся, теперь очевидно из рассмотренияЭто.(Первый вариант был бы написан \x r b -> f (r b) x. На самом деле я не уверен, какой общий эффект это даст, хотя я не особо задумывался об этом.)
Я прошел много времени,хотя мне кажется, что это больше, чем на самом деле, потому что я старался быть очень кропотливым.Напомним, что функция foldlTest, учитывая список a s и функцию f :: b -> a -> b, создает функцию b -> b, которая строится, начиная с функции тождества и проходя справа налево.вдоль списка, изменяя текущую функцию r :: b -> b на ту, которая отправляет b в r (f b x) - где x :: a - элемент списка, в котором мы находимся в данный момент.
Это довольно алгоритмическое описаниеиз того, что foldlTest делает.Давайте попробуем посмотреть, что он делает с реальным списком - не конкретным, но, скажем, трехэлементным списком [a1, a2, a3].Мы начинаем с функции идентификации \b -> b и последовательно преобразуем ее в:
b -> f b a3 (напомним, что r начинается как функция идентификации) b -> f (f b a2) a3 (это просто подстановка предыдущей функции как r в \b -> r (f b x), где a2 теперь играет роль x) b -> f (f (f b a1) a2) a3
Надеюсь, выТеперь я вижу, что это выглядит очень похоже на свертывание списка слева с той же функцией f.И под «выглядит очень похоже» я имею в виду, что он идентичен!(Если вы не видели или не пробовали это раньше, попробуйте записать последовательные этапы foldl f b [a1, a2, a3], и вы увидите идентичный шаблон.)
Итак, еще раз извиняюсь, что это было немного бессмысленно,но я надеюсь, что это дало вам достаточно информации, чтобы ответить на вопросы, которые вы задавали.И не волнуйтесь, если это немного повредит вашему мозгу - это тоже мое!:)