карта. состав функции фолдра-Хаскелл

Итак, давайте прямо к делу.

:t (map.foldr)
(map.foldr) :: (a1 -> a -> a) -> [a] -> [[a1] -> a]

Что такое [[a1] - > a]? Я действительно пытаюсь понять эту композицию, поэтому я делал это: 

-- map.foldr

    map.foldr :: (a1 -> a -> a) -> [a] -> [[a1] -> a]

    map :: (a1 -> b1) -> [a1] -> [b1]
    (.) :: (y -> w) -> (x -> y) -> x -> w
    foldr :: (a -> b -> b) -> b -> [a] -> b

    y = (a1 -> b1)      w = ([a1] -> [b1])
    x = (a -> b -> b)   y = (b -> [a] -> b)

    y = (a1 -> b1)  
    y = (b -> [a] -> b)
_________________________

Что происходит в этой точке? Спасибо!

3 5
haskell function-composition

3 ответа:

Чтобы ответить на этот вопрос, полезно вспомнить, что делают foldr и map.

Более сложным из них является foldr, который имеет тип 

--              list to be folded
--                              v
foldr :: (a -> b -> b) -> b -> [a] -> b
--             ^          ^
--folding function        terminal value

Список, который нужно сложить, на самом деле представляет собой цепочку консов (:) и терминальный пустой список: 

1 : 2 : 3 : []

Действие foldr заключается в замене конструкторов : и [] функцией свертки и терминальным значением соответственно: 

foldr (+) 0 (1 : 2 : 3 : []) == 1 + 2 + 3 + 0

Функция map проще. Один из способов думать об этом таков: принимая функцию и список, и применяя функцию к каждому аргументу списка: 

map :: (a -> b) -> [a] -> [b]
--        ^         ^
-- function         list

Однако вы также можете думать об этом как о взятии функции и поднятии ее, чтобы она была функцией, которая действует на списки вместо этого: 

map :: (a -> b) -> ( [a] -> [b] )
--        ^              ^
-- function              function on lists
Что значит составить эти две функции, map . foldr? Обратите внимание, что это просто применение функций одна за другой - в частности, 
(map . foldr) f == map (foldr f)

Поскольку вы применяете foldr Сначала, вы должны применить его к функции f :: a -> b -> b, и вы получите назад еще одна функция: 

foldr f :: b -> [a] -> b
--         ^     ^
--terminal val   list to be folded

Теперь вы применяете map, который поднимает функцию, чтобы действовать на списках: 

map (foldr f) :: [b] -> [[a] -> b]
--                ^          ^
--list of terminal vals      functions that fold lists

Этот тип выглядит странно, но он действителен. Теперь вместо одного терминального значения вы даете ему список терминальных значений, и вы получаете список функций сворачивания обратно - по одному для каждого терминального значения, которое вы предоставили.

Чтобы было понятнее, мы могли бы рассмотреть конкретную функцию (+), которая имеет тип 

(+) :: Num a => a -> a -> a

Если мы подставим это в уравнение выше мы получаем 

(map . foldr) (+) :: Num a => [a] -> [[a] -> a]
--                             ^          ^
--         list of terminal vals          functions that fold lists
Если мы теперь применим его к списку [0, 1, 2], то получим список из трех функций: 
(map . foldr) (+) [0,1,2] :: Num a => [[a] -> a]
Мы можем использовать идиому map ($x), чтобы применить каждую из функций в списке к определенному аргументу. Это должен быть список чисел, и я выберу [3,4,5]. Смотрите внимательно: 
> map ($[3,4,5]) ((map.foldr) (+) [0,1,2])
[12, 13, 14]

Список [3,4,5] был сложен три раза, используя (+) в качестве функции складывания, и каждый раз с различным терминальным значением: 

3 + 4 + 5 + 0 == 12
3 + 4 + 5 + 1 == 13
3 + 4 + 5 + 2 == 14

Когда конечное значение равно 0, мы просто получаем сумму значений: 3 + 4 + 5 == 12. Когда терминальное значение равно 1, мы получаем на один больше суммы значений (13), а когда терминальное значение равно 2, мы получаем на два больше суммы значений (14).

14

Чтобы продолжить с того места, где вы остановились, два определения y должны быть равны: 

y = (a1 -> b1) = (b ->  [a] -> b)
               = (b -> ([a] -> b))
Таким образом, мы можем заключить, что: 
a1 = b
b1 = [a] -> b

Составу функции были предоставлены два аргумента функции, поэтому результирующий тип просто: 

x -> w

Но мы знаем: 

x = a -> b -> b
w = [a1] -> [b1] = [b] -> [[a] -> b]

Итак, тип результата: 

(x -> w) = ((a -> b -> b) -> ([b] -> [[a] -> b]))
         =  (a -> b -> b) ->  [b] -> [[a] -> b]

, что соответствует: 

(a1 -> a -> a) -> [a] -> [[a1] -> a]
2
map.foldr :: (a1 -> a -> a) -> [a] -> [[a1] -> a]

map :: (a1 -> b1) -> [a1] -> [b1]
(.) :: (y -> w) -> (x -> y) -> x -> w
foldr :: (a -> b -> b) -> b -> [a] -> b

-- if you substitute: x = (a -> b -> b)   y = (b -> [a] -> b)
-- then you get for map :: (b -> ([a] -> b)) -> [b] -> [[a] -> b]
-- so if composition operator applied:
map . foldr :: (a -> b -> b) -> [b] -> [[a] -> b]
1