Помогите с возможными вопросами викторины вывода типа Haskell - PullRequest
Новая
       29

Помогите с возможными вопросами викторины вывода типа Haskell

1 голос
/ 12 мая 2010 
foldr:: (a -> b -> b) -> b -> [a] -> b
map :: (a -> b) -> [a] -> [b]
mys :: a -> a
(.) :: (a -> b) -> (c -> a) -> c -> b

что такое предполагаемый тип:
a.map mys ::
карта b.mys ::
карта c.foldr ::
d.foldr map.mys ::

Я пытался создать mys себе, используя mys n = n + 2, но тип это 

mys :: Num a => a -> a

В чем разница между 'Num a => a -> a'и просто «а -> а»?Или что означает «Num a =>»?Неужели mys принимает только тип Num?

Так или иначе,
a) Я получил [a] -> [a] Я думаю, потому что он просто взял бы список и вернул бы его + 2'dв соответствии с моим определением mys
b) (a -> b) -> [a] -> [b] я думаю, потому что map все еще нужно принять оба аргумента, такие как (* 3), и список затем возвращает [a], которыйпереходит в mys и возвращает [b]
c) я не уверен, как это сделать 1. 1. 1016 * d) я тоже не уверен, как это сделать 1, но map.mys означает сначала сделать mys, а затем mapверно?

Верны ли мои ответы и мысли?Если нет, то почему?

СПАСИБО!

1 Ответ

3 голосов
/ 12 мая 2010

(Обновление: по-видимому, мой оригинальный ответ не был очень полезен для ОП ... Приложение см. Ниже, второй HR).

В подобных ситуациях вы действительно хотите запустить ghci и использовать :t, чтобы выяснить тип различных выражений. Э.Г. 

:t foldr map
-- answer: foldr map :: [b] -> [b -> b] -> [b]

Если вам нужно сначала определить имя, используйте let (что не требуется в исходном файле на Haskell): 

let mys = undefined :: a -> a
:t map mys
-- answer: [a] -> [a]

Обратите внимание на использование undefined с явной сигнатурой типа. Он идеально подходит для определения типа выражений различных форм и может даже оказаться полезным в реальном коде в качестве заполнителя на ранних этапах планирования.

Num a => - это ограничение класса типа для a; см. например Типы классов и перегрузка из "A Gentle Введение в Haskell, версия 98" или Глава 6. Использование классов типов из "Real World Haskell" для получения дополнительной информации. (По сути, он делает то, что, как вы думаете, он делает.: -))

Вышеприведенное должно быть полезно для проверки ваших ответов (и ресурсы по классам типов хороши). Что касается того, как решать проблемы такого рода самостоятельно:

Вывод типа - это применение так называемого «алгоритма объединения». Google для «объединения» для ряда ресурсов; если вы добавите имя языка программирования в свой запрос, вы, вероятно, найдете примеры реализаций.

Что касается того, как подойти к примерам под рукой ...

а. map mys: map принимает функцию типа a -> b и возвращает функцию типа [a] -> [b]. Как правило, a может отличаться от b, но mys имеет тип a -> a, поэтому возвращаемая функция будет иметь тип [a] -> [a].

Вот некоторое объединение рук: 

(a -> b) -> [a] -> [b]`  
(a -> a)`
      ^-- at this point we unify a with b;
          when propagated to the return type,
          this produces [a] -> [a]

б. mys map: mys - это функция, которая принимает объект некоторого типа и возвращает объект того же типа. В частности, если вы передадите ему аргумент типа (a -> b) -> [a] -> [b], это будет тип возвращаемого значения.

Кстати, есть только одна "интересная" (не undefined) функция, сигнатура типа которой равна a -> a (без ограничений класса типа), а именно id. Смотрите статью Филиппа Вадлера "Теоремы бесплатно!" (которую вы можете скачать с на этой странице ) для расширенного обсуждения.

с. foldr map: Во-первых, обратите внимание, что a s и b s в подписи foldr не имеют ничего общего с подписью map. Может быть удобно переименовать map a в c и b в d и использовать подпись map :: (c -> d) -> [c] -> [d], чтобы сделать это более очевидным ниже. Также обратите внимание, что (a -> b -> b) - это просто более простой способ написания (a -> (b -> b)).

Больше ручного объединения (пояснение приведено ниже): 

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

Здесь происходит то, что foldr принимает аргумент функции типа (a -> (b -> b)). Если вы передадите map в качестве этого аргумента, a объединится с c -> d, b с [c], а затем снова с [d], что означает c равно d.

Возвращаемое значение foldr имеет тип b -> [a] -> b; заменив более конкретные типы, полученные в предыдущем абзаце, мы получим 

[c] -> [c -> c] -> [c]
             ^-- c equals d, right?

c происходит от нашей измененной подписи для map; с оригинальным b, это становится 

[b] -> [b -> b] -> [b]

д. foldr map . mys: Это на самом деле (foldr map) . mys, а не foldr (map . mys) - приложение функции («оператор-невидимка») связывает сильнейшего! Объединение и с. сверху, чтобы решить это оставлено в качестве упражнения для читателя. ; -)

...