Что делает (ф.) . значит в Хаскеле?

Question

Я видел много функций, определяемых в соответствии с шаблоном (f .) . g, Например:

countWhere = (length .) . filter
duplicate  = (concat .) . replicate
concatMap  = (concat .) . map

Что это значит?

Answer 1

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

infixr 9 .
(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)

Как вы можете видеть, это принимает функцию типа b -> c и другая функция типа a -> b и возвращает функцию типа a -> c (т.е. который применяет результат второй функции к первой функции).

Оператор композиции функций очень полезен. Это позволяет направить вывод одной функции на вход другой функции. Например, вы можете написать программу Tac на Хаскеле следующим образом:

main = interact (\x -> unlines (reverse (lines x)))

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

main = interact (unlines . reverse . lines)

Как видите, составление функций очень полезно, но вы не можете использовать его везде. Например, вы не можете передать вывод filter в length используя состав функции:

countWhere = length . filter -- this is not allowed

Причина, по которой это не разрешено, заключается в том, что filter имеет тип (a -> Bool) -> [a] -> [a], Сравнивая это с a -> b мы находим, что a имеет тип (a -> Bool) а также b имеет тип [a] -> [a], Это приводит к несоответствию типов, потому что Haskell ожидает length быть типом b -> c (т.е. ([a] -> [a]) -> c). Однако это на самом деле типа [a] -> Int,

Решение довольно простое:

countWhere f = length . filter f

Однако некоторые люди не любят этот дополнительный висячий f, Они предпочитают писать countWhere в стиле pointfree:

countWhere = (length .) . filter

Как они это получают? Рассматривать:

countWhere f xs = length (filter f xs)

-- But `f x y` is `(f x) y`. Hence:

countWhere f xs = length ((filter f) xs)

-- But `\x -> f (g x)` is `f . g`. Hence:

countWhere f = length . (filter f)

-- But `f . g` is `(f .) g`. Hence:

countWhere f = (length .) (filter f)

-- But `\x -> f (g x)` is `f . g`. Hence:

countWhere = (length .) . filter

Как вы видете (f .) . g это просто \x y -> f (g x y), Эта концепция действительно может быть повторена:

f . g             --> \x -> f (g x)
(f .) . g         --> \x y -> f (g x y)
((f .) .) . g     --> \x y z -> f (g x y z)
(((f .) .) .) . g --> \w x y z -> f (g w x y z)

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

f .: g = (f .) . g
f .:: g = ((f .) .) . g
f .::: g = (((f .) .) .) . g

С использованием (.:) оператор вы могли бы написать countWhere вместо этого:

countWhere = length .: filter

Интересно хоть ты мог написать (.:) в произвольном стиле:

f .: g = (f .) . g

-- But `f . g` is `(.) f g`. Hence:

f .: g = (.) (f .) g

-- But `\x -> f x` is `f`. Hence:

(f .:) = (.) (f .)

-- But `(f .)` is `((.) f)`. Hence:

(f .:) = (.) ((.) f)

-- But `\x -> f (g x)` is `f . g`. Hence:

(.:) = (.) . (.)

Аналогично получаем:

(.::)  = (.) . (.) . (.)
(.:::) = (.) . (.) . (.) . (.)

Как вы видете (.:), (.::) а также (.:::) просто силы (.) (т.е. они являются итеративными функциями (.)). Для чисел в математике:

x ^ 0 = 1
x ^ n = x * x ^ (n - 1)

Аналогично для функций в математике:

f .^ 0 = id
f .^ n = f . (f .^ (n - 1))

Если f является (.) затем:

(.) .^ 1 = (.)
(.) .^ 2 = (.:)
(.) .^ 3 = (.::)
(.) .^ 4 = (.:::)

Это приближает нас к концу этой статьи. Для финального испытания напишем следующую функцию в стиле pointfree:

mf a b c = filter a (map b c)

mf a b c = filter a ((map b) c)

mf a b = filter a . (map b)

mf a b = (filter a .) (map b)

mf a = (filter a .) . map

mf a = (. map) (filter a .)

mf a = (. map) ((filter a) .)

mf a = (. map) ((.) (filter a))

mf a = ((. map) . (.)) (filter a)

mf = ((. map) . (.)) . filter

mf = (. map) . (.) . filter

Мы можем еще больше упростить это следующим образом:

compose f g = (. f) . (.) . g

compose f g = ((. f) . (.)) . g

compose f g = (.) ((. f) . (.)) g

compose f = (.) ((. f) . (.))

compose f = (.) ((. (.)) (. f))

compose f = ((.) . (. (.))) (. f)

compose f = ((.) . (. (.))) (flip (.) f)

compose f = ((.) . (. (.))) ((flip (.)) f)

compose = ((.) . (. (.))) . (flip (.))

С помощью compose теперь вы можете написать mf как:

mf = compose map filter

Да, это немного уродливо, но это также действительно потрясающая концепция. Теперь вы можете написать любую функцию вида \x y z -> f x (g y z) как compose f g и это очень аккуратно.

Answer 2

Это дело вкуса, но я нахожу такой стиль неприятным. Сначала я опишу, что это значит, а затем я предложу альтернативу, которую я предпочитаю.

Вы должны знать, что (f . g) x = f (g x) а также (f ?) x = f ? x для любого оператора ?, Из этого мы можем сделать вывод, что

countWhere p = ((length .) . filter) p
              = (length .) (filter p)
              = length . filter p

так

countWhere p xs = length (filter p xs)

Я предпочитаю использовать функцию под названием .:

(.:) :: (r -> z) -> (a -> b -> r) -> a -> b -> z
(f .: g) x y = f (g x y)

затем countWhere = length .: filter, Лично я нахожу это намного яснее.

(.: определяется в Data.Composition и, вероятно, другие места тоже.)