Композиция функций в примере Haskell

То, что вы заметили, называется каррированием, и это один из многих замечательных (или, возможно, нет) аспектов функций Haskell. . Это ваш код:

map (map (\a -> ((head a), (length a))) . group . sort) (transpose b)

Проверим тип первого map:

map (\a -> ((head a), (length a))) :: [[a]] -> [(a, Int)]

Мы делаем это, набирая это

:t map (\a -> ((head a), (length a)))

в ghci.

Итак, знайте, что мы знаем, что это функция. Он принимает элемент типа [[a]] и возвращает [(a, Int)]. Укажите тип функции карты:

map :: (a -> b) -> [a] -> [b]

Это прекрасно. Мы дали map это первый аргумент, теперь все, что ему нужно, это правильный список. То, что только что произошло с картой, называется каррированием.

Теперь посмотрим, у нас map "подключены" к sort и group через функцию (.).

(.) :: (b -> c) -> (a -> b) -> a -> c

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

map (\a -> ((head a), (length a))) . (group . sort)

Я просто разделил group и sort скобками. Но теперь мы ясно видим, какие элементы действуют как аргументы внешнего (.).

У нас есть рассматриваемая карта и другая функция, которая является результатом другой композиции. И снова у нас есть каррирование, когда мы опускаем последний аргумент:

map (\a -> ((head a), (length a))) . (group . sort)
:: Ord a => [a] -> [(a, Int)]

Наконец, внешний map принимает функцию сверху и список (transpose b).

Дается неявно. Если вы напишете:

map (\a -> ((head a), (length a))) . group . sort

на самом деле это сокращение от:

\b -> (map (\a -> ((head a), (length a))) . group . sort) b

что эквивалентно:

\b -> map (\a -> ((head a), (length a))) $ group $ sort b

or:

\b -> map (\a -> ((head a), (length a))) (group (sort b))

Таким образом, оператор (.) :: (b -> c) -> (a -> b) -> a -> c объединяет две функции в своего рода конвейер:

(.) f g x = f (g x)

Поскольку здесь мы пишем три функции, разделенные точками:

   map (\a -> ((head a), (length a))) . group . sort
-- \_________________ ______________/   \_ _/   \_ /
--                   v                    v       v
--                   f                    g       h

мы определили своего рода конвейер, в котором элемент сначала обрабатывается через h, затем результат обрабатывается через g, и, наконец, результат этого обрабатывается через f.

Точка сама по себе является функцией, которая определяется следующим образом:

(f . g) x = f (g x)

Давайте используем это уравнение в качестве первого аргумента внешней карты:

map (\a -> (head a, length a)) . group . sort
= { definition of (.), with map (\a -> ...) as f and group . sort as g }
\x -> map (\a -> (head a, length a)) ((group . sort) x)

Итак, map (\a -> ...) . group . sort - это функция, которая при применении к аргументу x предоставляет (group . sort) x в качестве аргумента для map (\a -> ...).