(\_ n -> 1 + n) просто означает функцию, которая принимает два аргумента и возвращает на один больше, чем ее второй аргумент.Подчеркивание просто означает, что параметр игнорируется.Для сравнения, в качестве объявления верхнего уровня без использования шаблона подстановки (подчеркивание) эта функция будет выглядеть следующим образом:
foo x n = 1 + n
Теперь вот пример списка:
[1, 2, 3, 4]
На самом деле это всего лишь синтаксический сахар для:
1 : 2 : 3 : 4 : []
То, что делает foldr, рекурсивно заменяет каждый (:) на данную функцию, а [] - на аргумент после функции (* ноль ).Таким образом, foldr f z [1, 2, 3, 4] для любых f и z выглядит следующим образом:
f 1 (f 2 (f 3 (f 4 z)))
(Вот почему foldr (:) [] просто возвращает тот же список, который вы ему дали, - в конечном итоге он восстанавливает исходныйСтруктура списка.)
В этом случае, используя функцию foo и ноль 0, она выглядит следующим образом:
foo 1 (foo 2 (foo 3 (foo 4 0)))
Мы знаем, что foo игнорирует свой первый аргумент, ивозвращает на один больше, чем его второй аргумент.Так что это то же самое, что и
1 + (1 + (1 + (1 + 0)))
, что равно 4, длина списка.По сути, сгиб игнорирует каждый элемент списка и просто добавляет один к аккумулятору для каждого элемента, давая длину.0 используется для завершения всего процесса, и поскольку длина пустого списка равна 0.
Чтобы увидеть это более подробно, мы можем постепенно расширять каждый вызов:
foldr foo 0 (1 : 2 : 3 : 4 : [])
foo 1 (foldr foo 0 (2 : 3 : 4 : []))
1 + foldr foo 0 (2 : 3 : 4 : [])
1 + foo 2 (foldr foo 0 (3 : 4 : []))
1 + 1 + foldr foo 0 (3 : 4 : [])
1 + 1 + foo 3 (foldr foo 0 (4 : []))
1 + 1 + 1 + foldr foo 0 (4 : [])
1 + 1 + 1 + foo 4 (foldr foo 0 [])
1 + 1 + 1 + 1 + foldr foo 0 []
1 + 1 + 1 + 1 + 0
1 + 1 + 1 + 1
1 + 1 + 2
1 + 3
4