Состав функции Haskell, тип (.)(.) И способ ее представления.

Question

Итак, я знаю, что:

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

И это тип (B->C)->(A->B)->A->C Но как насчет:

(.)(.) = _? = _?

Как это представляется? Я думал о:

(.)(.) = (f.g)(f.g)x = f(g(f(g x))) // this
(.)(.) = (f.g.h)x = f(g(h x)) // or this

Но насколько я пытался получить тип этого, это не правильно к тому, что GHCi говорит мне. Так что же такое "_?"

Кроме того - что делает функция / оператор $?

Answer 1

Во-первых, вы неряшливы в своей записи.

(.) = (f.g) x = f (g x)  -- this isn't true

Что правда:

(.) f g x = (f.g) x = f (g x)
(.) = \f g x -> f (g x)

И его тип определяется

(.) :: (b -> c) -> (a -> b) -> a -> c
       -- n.b. lower case, because they're type *variables*

между тем

(.)(.) :: (a -> b -> d) -> a -> (c -> b) -> c -> d
          -- I renamed the variables ghci gave me

Теперь давайте работать

(.)(.) = (\f' g' x' -> f' (g' x')) (\f g x -> f (g x))
       = \g' x' -> (\f g x -> f (g x)) (g' x')
       = \g' x' -> \g x -> (g' x') (g x)
       = \f y -> \g x -> (f y) (g x)
       = \f y g x -> f y (g x)
       = \f y g x -> (f y . g) x
       = \f y g -> f y . g

---

А также ($)?

($) :: (a -> b) -> a -> b
f $ x = f x

($) это просто приложение функции. Но тогда как применение функции через сопоставление имеет высокий приоритет, применение функции через ($) низкий приоритет.

square $ 1 + 2 * 3 = square (1 + 2 * 3)
square 1 + 2 * 3 = (square 1) + 2 * 3  -- these lines are different

Answer 2

Как упоминает dave4420,

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

Так какой тип (.) (.)? dave4420 пропускает эту часть, вот она: (.) принимает значение типа b -> c в качестве первого аргумента, так

(.) :: (   b     ->       c             ) -> (a -> b) -> a -> c
(.) ::  (d -> e) -> ((f -> d) -> f -> e)

так что у нас есть b ~ d->e а также c ~ (f -> d) -> f -> eи результирующий тип (.)(.) является (a -> b) -> a -> c, Подставляя, получаем

(a -> d -> e) -> a -> (f -> d) -> f -> e

Переименовав, получаем (a -> b -> c) -> a -> (d -> b) -> d -> c, Это функция f что ожидает двоичную функцию g, ценность x, унарная функция h и другое значение y:

f g x h y = g x (h y)

Это единственный способ реализовать этот тип: g x :: b -> c, h y :: b так что g x (h y) :: c, по мере необходимости.

Конечно, в Haskell "унарная" функция такова, что ожидает один или несколько аргументов; аналогично "двоичная" функция такова, что ожидает два или более аргумента. Но не менее двух (так, используя, например, succ не может быть и речи).

---

Мы также можем решить эту проблему, написав уравнения, комбинаторы- стиль¹. Эквациональное рассуждение легко:

(.) (.) x y z w q = 
((.) . x) y z w q =
(.) (x y) z w q =
(x y . z) w q =
x y (z w) q 

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

_BB x y z w = x y (z w)

(По совпадению, (.) известен как B- комбинатор).

---

¹ a b c = (\x -> ... body ...) эквивалентно a b c x = ... body ...и наоборот, при условии, что x не появляется среди {a,b,c},