Блог

Я изо всех сил пытаюсь понять, почему этот код взят из 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 это элемент списка, а не функция…

Подумайте об этом так. Каждая функция принимает ровно один аргумент. Он может возвращать другую функцию (которая принимает один аргумент). То, что выглядит как вызов с несколькими аргументами

 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 на самом деле есть.

Прежде всего, имена переменных ужасны. Я всегда использую 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