Как интерпретировать тип функции в Haskell?

Question

Мой код следующий

data Tree a = Leaf a | Node (Tree a) (Tree a) 
    deriving (Show)
f x = x + 1
myTree = Node (Node (Leaf 2) (Leaf 3)) (Leaf 4)
maptree f (Leaf a)= Leaf (f a)
maptree f (Node xl xr ) = Node (maptree f xl) (maptree f xr)

, который может добавить один элемент Leaf в дереве.

Далее я рассмотрю тип функции,

*Main> let maptree f (Leaf a)= Leaf (f a) 
maptree :: (t -> a) -> Tree t -> Tree a 

*Main> let maptree f (Node  xl xr ) = Node (maptree f xl) (maptree f xr) 
maptree :: t -> Tree t1 -> Tree a

Что здесь означают t, a и t1? Есть ли какие-либо ссылки, которые я могу прочитать для этих вещей?

Спасибо.

Answer 1

Идентификаторы, начинающиеся со строчной буквы, такие как t, a и t1, являются переменными типа при использовании в контексте типа.Они являются заполнителями, которые могут быть специализированы для любого типа.См. этот ответ для получения дополнительной информации о том, как читать сигнатуры типов.

Также обратите внимание, что в GHCi ваш пример сначала определит одну функцию, которая обрабатывает только случай Leaf, а затем заменитэто с другим, который обрабатывает только случай Node, в отличие от исходных файлов на Haskell, где они будут двумя случаями одной и той же функции.Чтобы указать несколько уравнений для функции в GHCi, разделите их точкой с запятой:

*Main> let maptree f (Leaf a) = Leaf (f a); maptree f (Node xl xr) = Node (maptree f xl) (maptree f xr)

или используйте многострочный режим:

*Main> :{
*Main| let maptree f (Leaf a) = Leaf (f a)
*Main|     maptree f (Node xl xr) = Node (maptree f xl) (maptree f xr)
*Main| :}

Answer 2

Начнем с первой подписи:

(t -> a) -> Tree t -> Tree a

Это, по сути, говорит: «Учитывая функцию, которая принимает что-то типа t и производит a, а также Tree содержащие элементы типа t, создает Tree содержащие элементы типа a.

t и a - совершенно произвольные имена, сгенерированные GHCi; мы могли бы легко сказать:

(originalType -> newType) -> Tree originalType -> Tree newType

Хотя большинство программистов пишут:

(a -> b) -> Tree a -> Tree b

Теперь вторая подпись:

t -> Tree t1 -> Tree a

Эта подпись странная, потому что, как указал Хаммар, два maptree определения, которые вы написали в GHCi, полностью независимы. Итак, давайте посмотрим на второе определение само по себе:

maptree f (Node xl xr) = Node (maptree f xl) (maptree f xr)

Здесь тип f не имеет значения, так как вы не применяете его к каким-либо аргументам и передаете его только maptree, который рекурсивно не заботится о том, какой тип f. Итак, давайте дадим f type t, так как это не имеет значения.

Теперь, аналогично, нет ограничений на xl и xr, поскольку они передаются только в maptree, который не знает их типы, за исключением того, что это должно быть Tree. Таким образом, мы могли бы также назвать их тип Tree t1.

Мы знаем, что эта функция вернет Tree из-за конструктора Node, но предыдущие два типа, на которые мы смотрели, не имеют отношения к типу элементов в дереве, поэтому мы можем также назвать его Tree a.

В качестве примера давайте посмотрим, что произойдет, когда мы расширим следующее:

maptree True (Node (Leaf 0) (Leaf 1))
= Node (maptree True (Leaf 0)) (maptree True (Leaf 1))

Что не получается, потому что maptree в этом случае не может расширить Leaf.

Однако, типы работают:

True                   :: t
Node (Leaf 0) (Leaf 1) :: Tree t1
0                      :: t1
1                      :: t1

Так что подпись была очень странной, но она имеет смысл. Думаю, не перезаписывайте определения.