#haskell
#haskell
Вопрос:
Я изо всех сил пытаюсь понять, почему этот код взят из haskell.org проверка типов страниц упражнений (и работает как функция разворота списка):
myReverse :: [a] -> [a]
myReverse xs = foldr (x fId empty -> fId (x : empty)) id xs []
Моя первая путаница заключается в том, что foldr принимает 3 аргумента, а не 4 :
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
итак, я предполагаю, что myReverse
это эквивалентно:
myReverse xs = foldr ((x fId empty -> fId (x : empty)) id) xs []
но тогда это тоже не должно работать, поскольку в лямбде x
это элемент списка, а не функция…
Комментарии:
1. Потому
foldr ... xs
что возвращает функцию, которая принимает список, а затем заполняет его элементами изxs
. Изначально эта функцияid
(что означает, что она не изменяет список). Затем каждаяfoldr
итерация изменяет функцию: она добавляет текущий элемент, а затем выполняет остальные (т. Е. Добавляет Уже видимые элементы).2. По сути, любая функция
f :: ... -> ... -> b
принимает сколь угодно большое количество аргументов. Это связано с тем, чтоb
canA1 -> ... -> An -> T
позволяет применять функцию «результатf
» кn
дополнительным аргументам. Например,id :: b -> b
позволяетid ( ) 3 4
. При этом я рассматриваю »foldr
с> 3 аргументами» как своего рода антипаттерн, поскольку явная рекурсия IMO была бы более понятной. Приведенный вышеempty
аргумент не всегда привязан к пустому списку, что создает еще большую путаницу.
Ответ №1:
Подумайте об этом так. Каждая функция принимает ровно один аргумент. Он может возвращать другую функцию (которая принимает один аргумент). То, что выглядит как вызов с несколькими аргументами
f a b c
на самом деле анализируется как
((f a) b) c
то есть цепочка приложений с одним аргументом. Тип функции
f :: a -> b -> c -> d
может быть разложен на
f :: a -> (b -> (c -> d))
т.е. функция, возвращающая функцию, возвращающую функцию. Обычно мы рассматриваем это как функцию от трех аргументов. Но может ли он принимать более трех? Да, если d
это другой тип функции.
Это именно то, что происходит с вашим fold
примером. Функция, которую вы передаете в качестве первого аргумента foldr
, принимает три аргумента, что в точности совпадает с принятием двух аргументов и возвратом другой функции. Теперь (упрощенный) тип foldr
(a -> b -> b) -> b -> [a] -> b
но если вы посмотрите на первый аргумент, вы увидите, что это функция из трех аргументов. Что, как мы видели, точно так же, как функция, которая получает два аргумента и возвращает функцию. Таким b
образом, это тип функции. Поскольку b
также является возвращаемым значением tuoe foldr
при применении к трем аргументам
foldr (x fId empty -> fId (x : empty)) id
и это функция, теперь ее можно применить к другому аргументу
(foldr (x fId empty -> fId (x : empty)) id xs) []
Я позволяю вам выяснить, что b
на самом деле есть.
Ответ №2:
Прежде всего, имена переменных ужасны. Я всегда использую r
для второго аргумента функцию-редуктор foldr в качестве мнемоники для «рекурсивного результата». « empty
» слишком перегружен значением; лучше использовать какое-то нейтральное имя, чтобы было легче понять, что это такое, без каких-либо предвзятых представлений:
myReverse :: [a] -> [a]
myReverse xs = foldr (x r n -> r (x : n)) id xs []
В силу определения foldr,
foldr f z (x:xs) === f x (foldr f z xs)
т.е.
myReverse [a,b,c,...,z]
= foldr (x r n -> r (x : n)) id [a,b,c,...,z] []
= (x r n -> r (x : n)) a (foldr (x r n -> r (x : n)) id [b,c,...,z]) []
= (x r n -> r (x : n))
a
(foldr (x r n -> r (x : n)) id [b,c,...,z])
[]
= let { x = a
; r = foldr (x r n -> r (x : n)) id [b,c,...,z]
; n = []
}
in r (x : n)
= foldr (x r n -> r (x : n)) id [b,c,...,z] (a : [])
= foldr (x r n -> r (x : n)) id [b,c,...,z] [a]
= ....
= foldr (x r n -> r (x : n)) id [c,...,z] (b : [a])
= foldr (x r n -> r (x : n)) id [c,...,z] [b,a]
= ....
= foldr (x r n -> r (x : n)) id [] [z,...,c,b,a]
= id [z,...,c,b,a]
Я надеюсь, что эта иллюстрация прояснит, что там происходит. Дополнительный аргумент ожидается функцией reducer, которая приводится в действие с помощью foldr
…, что приводит к операционному эквиваленту
= foldl (n x -> (x : n)) [] [a,b,c,...,z]
Как выясняется, myReverse
реализация использует эквивалентность
foldl (flip f) n xs === foldr (x r -> r . f x) id xs n