Явные подписи типов для полиморфных типов.Часть II

Question

Это продолжение до предыдущего вопроса;Я получил ответ, которого я действительно не понял , но принял.Поэтому я спрошу это снова.

Я все еще не понимаю, как это имеет смысл:

type Parse a b = [a] -> [(b,[a])]
build :: Parse a b -> ( b -> c ) -> Parse a c
build p f inp = [ (f x, rem) | (x, rem) <- p inp ]

Теперь, очевидно, p связывается с первым аргументом типа Parse a b.И, опять же, очевидно, f связывается со вторым аргументом (b -> c).У меня остается вопрос: что связывает inp с

Если Parse a b является синонимом типа для [a] -> [(b,[a])] Я подумал, что из последнего вопроса я могу просто заменить его:

build :: [a] -> [(b,[a])] -> ( b -> c ) -> [a] -> [(c,[a])]

Однако я не вижу в этом смысла и с определением:

build p f inp = [ (f x, rem) | (x, rem) <- p inp ]

Кто-то может помочь объяснить синонимы типов.

Answer 1

Теперь, очевидно, p связывается с первым аргументом типа Parse a b. И, опять же, очевидно, что f связывается со вторым аргументом (b -> c). У меня остается вопрос, с чем связывается inp?

Аргумент типа [a]

Если Parse a b является синонимом типа [a] -> [(b, [a])], я подумал, что из последнего вопроса я мог бы просто заменить его:

build :: [a] -> [(b,[a])] -> ( b -> c ) -> [a] -> [(c,[a])]

Почти; вам нужно заключить в скобки замены:

build :: ([a] -> [(b,[a])]) -> ( b -> c ) -> ([a] -> [(c,[a])])

Поскольку -> является ассоциативным справа, вы можете удалить скобки в конце, но не в начале, так что вы получите:

build :: ([a] -> [(b,[a])]) -> ( b -> c ) -> [a] -> [(c,[a])]

Это должно прояснить, почему inp имеет тип [a].

Answer 2

Вы можете заменить - но не забудьте заключить в скобки! Это должно быть:

build :: ( [a] -> [(b,[a])] ) -> ( b -> c ) -> ( [a] -> [(c,[a])] )

Поскольку стрелка функции является ассоциативной справа, вы можете выбросить правый набор скобок, но, что важно, вы не можете сбросить новые слева:

build :: ( [a] -> [(b,[a])] ) -> ( b -> c ) -> [a] -> [(c,[a])]

Итак, теперь, когда у вас есть строка build p f inp, вы можете увидеть, что:

p :: ( [a] -> [(b,[a])] )
f :: ( b -> c )
inp :: [a]

Итак, мы можем видеть, что:

p inp :: [(b, [a])]

И, таким образом:

x :: b
rem :: [a]

И

f x :: c
(f x, rem) :: (c, [a])

И, следовательно, понимание всего списка имеет тип [(c, [a])] - который точно соответствует тому, что должен возвращать build. Надеюсь, это поможет!

Answer 3

Если вы подставите

type Parse a b = [a] -> [(b,[a])]

в

build :: Parse a b -> ( b -> c ) -> Parse a c

, вы получите

build :: ([a] -> [(b,[a])]) -> (b -> c) -> [a] -> [(c,[a])]

Помните, что x -> y -> z - это сокращение от x -> (y -> z), которое оченьотличается от (x -> y) -> z.Первая - это функция, которая принимает два аргумента x, y и возвращает z [именно она принимает один аргумент x и возвращает функцию, которая принимает y и возвращает z];вторая - это то, что принимает функцию x -> y и возвращает z.

Answer 4

Важно помнить, что стрелка -> в сигнатурах типов является ассоциативной справа. Тип a -> (b -> c) совпадает с типом a -> b -> c.

Так типа

Parse a b -> ( b -> c ) -> Parse a c

разрешается до

([a] -> [(b,[a])]) -> ( b -> c ) -> ([a] -> [(c,[a])])

С помощью ассоциативности вы можете удалить последние символы, но не первые. Это дает вам

([a] -> [(b,[a])]) -> ( b -> c ) -> [a] -> [(c,[a])]

, который позволяет написать формулу для build с 3 аргументами.