Что происходит, когда я пишу * с + в Haskell?

Question

Я пытаюсь понять результат

(*) . (+) 

в Хаскеле. Я знаю, что оператор композиции - это просто стандартная композиция математических функций, поэтому

(f . g) = f (g x)

Но:

(*) . (+) :: (Num (a -> a), Num a) => a -> (a -> a) -> a -> a

Я изо всех сил пытаюсь понять эту подпись типа. Я ожидал, что смогу делать такие вещи, как:

((*) . (+)) 1 2 :: Num a => a -> a
= (* (+ 1 2))

Каково значение (*) . (+) Тип подписи? Я попытался поиграть с ним что-то вроде (просто совпадая с его подписью):

((*) . (+)) 1 (\x -> x + 1) 1

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

Answer 1

Я понимаю что ты чувствуешь. Я обнаружил, что поначалу довольно сложно понять состав функций. Что помогло мне в этом вопросе, так это подписи типа. Рассматривать:

(*) :: Num x => x -> x -> x
(+) :: Num y => y -> y -> y
(.) :: (b -> c) -> (a -> b) -> a -> c

Теперь когда пишешь (*) . (+) это на самом деле так же, как (.) (*) (+) (т.е. (*) это первый аргумент (.) а также (+) это второй аргумент (.)):

(.) :: (b -> c) -> (a -> b) -> a -> c
       |______|    |______|
           |           |
          (*)         (+)

Отсюда тип подписи (*) (т.е. Num x => x -> x -> x) объединяется с b -> c:

(*) :: Num x => x -> x -> x -- remember that `x ->  x -> x`
                |    |____| -- is implicitly `x -> (x -> x)`
                |       |
                b ->    c

(.) (*) ::          (a -> b) -> a ->    c
                          |             |
                          |          |‾‾‾‾|
           Num x =>       x          x -> x

(.) (*) :: Num x => (a -> x) -> a -> x -> x

Отсюда тип подписи (+) (т.е. Num y => y -> y -> y) объединяется с Num x => a -> x:

(+) :: Num y => y -> y -> y -- remember that `y ->  y -> y`
                |    |____| -- is implicitly `y -> (y -> y)`
                |       |
       Num x => a ->    x

(.) (*) (+) ::  Num x                => a ->     x    ->    x
                                        |        |          |
                                        |     |‾‾‾‾|     |‾‾‾‾|
                              Num y  => y     y -> y     y -> y

(.) (*) (+) :: (Num (y -> y), Num y) => y -> (y -> y) -> y -> y

Я надеюсь, что это проясняет, где Num (y -> y) а также Num y родом из. Вы остались с очень странной функцией типа (Num (y -> y), Num y) => y -> (y -> y) -> y -> y,

Что делает его таким странным, так это то, что y а также y -> y быть примерами Num, Понятно что y должен быть примером Num, но как y -> y? Изготовление y -> y экземпляр Num кажется нелогичным. Это не может быть правильно.

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

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

((*) . (+)) = \z -> (*) ((+) z)

Итак, у вас есть функция \z -> (*) ((+) z), следовательно z явно должен быть примером Num так как (+) применяется к нему. Таким образом, тип \z -> (*) ((+) z) является Num t => t -> ... где ... это тип (*) ((+) z), который мы узнаем через мгновение.

Следовательно ((+) z) имеет тип Num t => t -> t потому что это требует еще один номер. Однако, прежде чем он применяется к другому номеру, (*) применяется к нему.

следовательно (*) надеется ((+) z) быть примером Num вот почему t -> t как ожидается, будет примером Num, Таким образом ... заменяется (t -> t) -> t -> t и ограничение Num (t -> t) добавляется, что приводит к типу (Num (t -> t), Num t) => t -> (t -> t) -> t -> t,

То, как вы действительно хотите объединить (*) а также (+) использует (.:):

(.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
f .: g = \x y -> f (g x y)

следовательно (*) .: (+) такой же как \x y -> (*) ((+) x y), Теперь два аргумента приведены (+) обеспечение того, чтобы ((+) x y) это действительно просто Num t => t и не Num t => t -> t,

следовательно ((*) .: (+)) 2 3 5 является (*) ((+) 2 3) 5 который (*) 5 5 который 25 Я считаю, что вы хотите.

Обратите внимание, что f .: g также может быть написано как (f .) . g, а также (.:) также может быть определен как (.:) = (.) . (.), Вы можете прочитать больше об этом здесь:

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

Надеюсь, это поможет.

Answer 2

(*) а также (+) оба имеют тип подписи Num a => a -> a -> aТеперь, если вы их составите, вы получите что-то интересное.

(*) . (+) :: (Num (a -> a), Num a) => a -> (a -> a) -> a -> a

Это потому что (*) а также (+) ожидают два "аргумента".

(+) с одним аргументом возвращает вам функцию. . оператор ожидает, что функция (a -> a что ты видишь).

Вот смысл (*) . (+)

                                       x     f          y
 (*) . (+) :: (Num (a -> a), Num a) => a -> (a -> a) -> a -> a

(*) . (+) карты x f y в ((x +) * f) y где f это функция от a в a Это также номер. Причина (*) ожидает, что функция должна привести типы в соответствие, в то время как она ожидает два аргумента, но эта функция должна быть числом, потому что (*) работает только на числах.

Действительно, эта функция вообще не имеет смысла.

Answer 3

Сначала несколько расширений:

{-# LANGUAGE FlexibleContexts, FlexibleInstances, TypeSynonymInstances #-}

Как показывают другие ответы, ваша функция

weird :: (Num (a -> a), Num a) => a -> (a -> a) -> a -> a
weird x g = (x +) * g

Но эта функция имеет странную семантику.

Существует понятие списков различий. Соответственно, существует понятие разности целых чисел. Я видел, как они используются только в настройках с зависимой типизацией (например, здесь, но это не единственный случай). Соответствующая часть определения

instance Enum DiffInt where
    toEnum   n = (n +)
    fromEnum n = n 0

instance Num DiffInt where
    n + m = n . m
    n * m = foldr (+) id $ replicate (fromEnum n) m

Это не имеет большого смысла в Haskell, но может быть полезно с зависимыми типами.

Теперь мы можем написать

test :: DiffInt
test = toEnum 3 * toEnum 4

Или же

test :: DiffInt
test = weird 3 (toEnum 4)

В обоих случаях fromEnum test == 12,

РЕДАКТИРОВАТЬ

Можно избежать использования TypeSynonymInstances расширение:

{-# LANGUAGE FlexibleContexts, FlexibleInstances #-}

weird :: (Num (a -> a), Num a) => a -> (a -> a) -> a -> a
weird x g = (x +) * g

instance (Enum a, Num a) => Enum (a -> a) where
    toEnum   n = (toEnum n +)
    fromEnum n = fromEnum $ n (toEnum 0)

instance (Enum a, Num a) => Num (a -> a) where
    n + m = n . m
    n * m = foldr (+) id $ replicate (fromEnum n) m

type DiffInt = Int -> Int

Как и прежде, мы можем написать

test' :: DiffInt
test' = weird 3 (toEnum 4)

Но теперь мы можем также написать

-- difference ints over difference ints
type DiffDiffInt = DiffInt -> DiffInt

test'' :: DiffDiffInt
test'' = weird (toEnum 3) (toEnum (toEnum 4))

А также

main = print $ fromEnum $ fromEnum test'

печать 12,

РЕДАКТИРОВАТЬ2 Добавлены лучшие ссылки.

Answer 4

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

Во-первых, правильное определение состава функции

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

вы пропустили x на LHS. Далее следует помнить, что в Хаскеле h x y такой же как (h x) y, Итак, вопреки тому, что вы ожидали,

((*) . (+)) 1 2 = (((*) . (+)) 1) 2 = ((*) ((+) 1)) 2 = ((+) 1) * 2,

и теперь вы видите, почему это не удается. Также,

((*) . (+)) 1 (\x -> x + 1) 1

не работает, потому что ограничение Num (Int -> Int) не устраивает.

Answer 5

Позволять:

m = (*)
a = (+)

затем

(m.a) x = (m (a x)) = m (a x) 

Сейчас m ожидает Num a в качестве параметра, с другой стороны (a x) т.е. (x +) это унарная функция (a -> a) по определению (+), Я предполагаю, что произошло то, что GHC пытается объединить эти два типа так, что если у вас есть тип, который является и числом, и унарной функцией, m может принимать число и унарную функцию и возвращать унарную функцию, поскольку они считаются однотипными.

Как указывал @Syd, это объединение не имело бы смысла для любых типов обычных чисел, таких как целые числа и числа с плавающей запятой.