Что (f.). g означает в Haskell?

Ответ 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 (f.). g это просто \xy → f (gxy). Эта концепция действительно может быть повторена:

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

Интересно, что вы могли бы написать (.:) в стиле free point:

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

Да, это немного некрасиво, но это также действительно потрясающая ошеломляющая концепция. Теперь вы можете написать любую функцию вида \xyz → fx (gyz) как compose fg и это очень удобно.

Ответ 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 и, возможно, в других местах.)