Unknown - haskell-notes

рекурсией foldl. Но это не так просто. Всё же попробуем. Для этого вспомним определение:

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

foldl f s []

=s

foldl f s (a :as)

=foldl f (f s a) as

Нам нужно привести это определение к виду foldr, нам нужно выделить два метода воображаемого

класса списка cons и nil:

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

foldr cons nil =\x -> casex of

a :as

->a ‘cons‘ foldr cons nil as

[]

->nil

Перенесём два последних аргумента определения foldl в правую часть, воспользуемся лямбда-

функциями и case-выражением:

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

foldl f =\x -> casex of

[]

->\s ->s

a :as

->\s ->foldl f as (f s a)

Мы поменяли местами порядок следования аргументов (второго и третьего). Выделим тождественную

функцию в первом уравнении case-выражения и функцию композиции во втором.

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

foldl f =\x -> casex of

[]

->id

a :as

->foldl f as .(flip f a)

Теперь выделим функции cons и nil:

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

foldl f =\x -> casex of

[]

->nil

a :as

->a ‘cons‘ foldl f as

wherenil

=id

cons

=\a b ->b .flip f a

=\a

->( .flip f a)

Теперь запишем через foldr:

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

foldl f s xs =foldr (\a ->( .flip f a)) id xs s

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

foldr мы сворачиваем списки в функции, последний аргумент предназначен как раз для результирующей

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

flip.

Свёртка | 195

Вычислительные особенности foldl и foldr

Если посмотреть на выражение, которое получается в результате вычисления foldr и foldl можно понять

почему они так называются.

В левой свёртке foldl скобки группируются влево, поэтому на конце l (left):

foldl f s [a1, a2, a3, a4] =

(((s ‘f‘ a1) ‘f‘ a2) ‘f‘ a3) ‘f‘ a4

В правой свёртке foldr скобки группируются вправо, поэтому на конце r (right):

foldr f s [a1, a2, a3, a4]

a1 ‘f‘ (a2 ‘f‘ (a3 ‘f‘ (a4 ‘f‘ s)))

Кажется, что если функция f ассоциативна

(a ‘f‘ b) ‘f‘ c

=a ‘f‘ (b ‘f‘ c)

то нет разницы какую свёртку применять. Разницы нет по смыслу, но может быть существенная разница

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

concat

=foldl ( ++) []

concat

=foldr ( ++) []

Какое выбрать? Результат и в том и в другом случае одинаковый (функция ++ассоциативна). Стоит вы-

брать вариант с правой свёрткой. В первом варианте скобки будут группироваться влево, это чудовищно

скажется на производительности. Особенно если в конце небольшие списки:

Prelude> letconcatl

=foldl ( ++) []

Prelude> letconcatr

=foldr ( ++) []

Prelude> letx =[1 ..1000000]

Prelude> letxs =[x,x,x] ++map return x

Последним выражением мы создали список списков, в котором три списка по миллиону элементов, а в

конце миллион списков по одному элементу. Теперь попробуйте выполнить concatl и concatr на списке xs.

Вы заметите разницу по скорости печати. Также для сравнения можно установить флаг: :set +s.

Также интересной особенностью foldr является тот факт, что за счёт ленивых вычислений foldr не нужно

знать весь список, правая свёртка может работать и на бесконечных списках, в то время как foldl не вернёт

результат, пока не составит всё выражение. Например такое выражение будет вычислено:

Prelude>foldr ( &&) undefined $ True : True :repeat False

False

За счёт ленивых вычислений мы отбросили оставшуюся (бесконечную) часть списка. По этим примерам

может показаться, что левая свёртка такая не нужна совсем, но не все операции ассоциативны. Иногда полез-