, нуль – стартовое значение, и
>xs – список. В самом начале нуль используется как значение аккумулятора, а
>3 – как значение образца
>x (текущий элемент). Выражение
>(0+3) в результате даёт
>3; это становится новым значением аккумулятора. Далее,
>3 используется как значение аккумулятора и
>5 – как текущий элемент; новым значением аккумулятора становится
>8. На следующем шаге
>8 – значение аккумулятора,
>2 – текущий элемент, новое значение аккумулятора становится равным
>10. На последнем шаге
>10 из аккумулятора и
>1 как текущий элемент дают
>11. Поздравляю – вы только что выполнили свёртку списка!
Диаграмма на предыдущей странице иллюстрирует работу свёртки шаг за шагом, день за днём. Цифры слева от знака + представляют собой значения аккумулятора. Как вы можете видеть, аккумулятор будто бы «поедает» список, начиная с левой стороны. Ням-ням-ням! Если мы примем во внимание, что функции каррированы, то можем записать определение функции ещё более лаконично:
>sum' :: (Num a) => [a] –> a
>sum' = foldl (+) 0
Анонимная функция >(\acc x –> acc + x) – это то же самое, что и оператор >(+). Мы можем пропустить >xs в параметрах, потому что вызов >foldl (+) 0 вернёт функцию, которая принимает список. В общем, если у вас есть функция вида >foo a = bar b a, вы всегда можете переписать её как >foo = bar b, так как происходит каррирование.
Ну что ж, давайте реализуем ещё одну функцию с левой свёрткой перед тем, как перейти к правой. Уверен, все вы знаете, что функция >elem проверяет, является ли некоторое значение частью списка, так что я не буду этого повторять (тьфу ты – не хотел, а повторил!). Итак:
>elem' :: (Eq a) => a –> [a] –> Bool
>elem' y ys = foldl (\acc x –> if x == y then True else acc) False ys
Что мы имеем? Стартовое значение и аккумулятор – булевские значения. Тип аккумулятора и стартового значения в свёртках всегда совпадают. Запомните это правило: оно может подсказать вам, что следует использовать в качестве стартового значения, если вы затрудняетесь. В данном случае мы начинаем со значения >False. В этом есть смысл: предполагается, что в списке нет искомого элемента. Если мы вызовем функцию свёртки с пустым списком, то результатом будет стартовое значение. Затем мы проверяем текущий элемент на равенство искомому. Если это он – устанавливаем в >True. Если нет – не изменяем аккумулятор. Если он прежде был равен значению >False, то остаётся равным >False, так как текущий элемент – не искомый. Если же был равен >True, мы опять-таки оставляем его неизменным.