Co (f.). g oznacza w Haskell?

Question

Widziałem wiele funkcji zdefiniowanych zgodnie ze wzorcem (f .) . g. Na przykład:

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

Co to oznacza?

Answer 1

Operator kropki (tj. (.)) jest operatorem function composition. Jest ona zdefiniowana w następujący sposób:

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

Jak widać to wykonuje funkcję typu b -> c i inną funkcję typu a -> b i zwraca funkcję typu a -> c (tj którego stosuje się wynik drugiej funkcji z pierwszym funkcjonować).

Operator składu funkcji jest bardzo użyteczny. Pozwala to potokować wyjście jednej funkcji do wejścia innej funkcji. Na przykład można napisać program w Haskell tac następująco:

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

Nie bardzo czytelny. Korzystanie złożenie funkcji jednak można napisać go w następujący sposób:

main = interact (unlines . reverse . lines) 

Jak widać złożenie funkcji jest bardzo przydatne, ale nie można go używać wszędzie. Na przykład nie można rura wyjściowa filter w length użyciu kompozycji funkcję:

countWhere = length . filter -- this is not allowed 

Powodem nie może, ponieważ filter jest typu (a -> Bool) -> [a] -> [a]. Porównując go z a -> b, stwierdziliśmy, że a jest typu (a -> Bool), a b jest typu [a] -> [a]. Powoduje to niedopasowanie typu, ponieważ Haskell oczekuje, że length będzie typu b -> c (tj. ([a] -> [a]) -> c). Jednak w rzeczywistości jest to typ [a] -> Int.

Rozwiązanie jest dość proste:

countWhere f = length . filter f 

Jednak niektórzy ludzie nie lubią tego dodatkowego zwisające f. Wolą pisać countWhere w pointfree stylu następująco:

countWhere = (length .) . filter 

Jak oni otrzymać? Rozważmy:

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 

Jak widać (f .) . g jest po prostu \x y -> f (g x y). Ta koncepcja może być w rzeczywistości powtarzana:

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) 

Nie jest ładna, ale wykonuje swoją pracę.Biorąc pod uwagę dwóch funkcji można również pisać własne operatorów złożenie funkcji:

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

pomocą operatora (.:) można napisać countWhere następująco zamiast:

countWhere = length .: filter 

Co ciekawe, choć można napisać (.:) w punkcie swobodnego stylu jak dobrze:

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: 

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

Podobnie otrzymujemy:

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

Jak widać (.:), (.::) i (.:::) są tylko uprawnienia (.) (tj są one iterated functions z (.)). Dla liczb matematyki:

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

podobnie dla funkcji w matematyce

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

Jeśli f jest (.) następnie:

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

To prowadzi nas blisko końca tego artykułu. Do ostatecznego wyzwania niech napisać następującą funkcję w stylu 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 

Możemy dodatkowo uprościć to w następujący sposób:

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 (.)) 

Korzystanie compose można teraz napisać mf jak:

mf = compose map filter 

Tak, to jest trochę brzydkie, ale jest to także niesamowita koncepcja, która zadziwia. Teraz możesz napisać dowolną funkcję w postaci \x y z -> f x (g y z) jako compose f g i jest to bardzo miłe.

Answer 2

To kwestia gustu, ale uważam, że taki styl jest nieprzyjemny. Najpierw opiszę, co to znaczy, a następnie proponuję alternatywę, którą preferuję.

Musisz wiedzieć, że (f . g) x = f (g x) i (f ?) x = f ? x dla dowolnego operatora ?. Z tego możemy wywnioskować, że

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

tak

countWhere p xs = length (filter p xs) 

wolę używać funkcji o nazwie .:

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

Następnie countWhere = length .: filter. Osobiście uważam to za dużo jaśniejsze.

(.: jest zdefiniowana w Data.Composition i prawdopodobnie innych miejscach).