Что такое [] (конструктор списков) в Haskell?

У меня возникают проблемы с пониманием функторов, в частности, конкретного типа в LYAH. Я считаю, что это потому, что я не понимаю, что такое [].

fmap :: (a -> b) -> f a -> f b
  • Является [], конструктором типа? Или это конструктор значений?
  • Что значит иметь тип: [] :: [a]?
  • Это как конструктор типа Maybe или конструктор значений Just?
    • Если это похоже на Just, то как получилось, что Just имеет подпись типа Just :: a -> Maybe a, а не Just :: Maybe a, иными словами, почему не [] typed [] :: a -> [a]
  • LYAH говорит об этом, поскольку он применим к функторам: Обратите внимание, что мы не пишем экземпляр Functor [a] где, потому что из fmap:: (a → b) → fa → fb, мы видим, что f должен быть конструктором типа, который принимает один тип. [a] уже является конкретным типом (из списка с любым типом внутри него), а [] - это конструктор типа, который принимает один тип и может создавать такие типы, как [Int], [String] или даже [[String] ]. Я смущен, хотя тип [] означает, что он похож на литерал для [a], к чему стремится LYAH?

Ответы

Ответ 1

Тип описан (в сеансе GHCI) как:

$ ghci
Prelude> :info []
data [] a = [] | a : [a] -- Defined

Мы также можем думать об этом, как если бы он был определен как:

data List a = Nil
            | Cons a (List a)

или

data List a = EmptyList
            | ListElement a (List a)

Конструктор типов

[a] - это тип полиморфных данных, который также можно записать [] a, как указано выше. Об этом можно подумать, как будто это было List a

В этом случае [] является конструктором типа, принимающим один аргумент типа a и возвращающим тип [] a, который также разрешен для записи как [a].

Можно написать тип функции, например:

sum :: (Num a) => [a] -> a

Конструктор данных

[] - это конструктор данных, который по существу означает "пустой список". Этот конструктор данных не принимает аргументов значения.

Существует еще один конструктор данных :, который добавляет элемент в начало другого списка. Подпись для этого конструктора данных a : [a] - он принимает элемент и другой список элементов и возвращает результирующий список элементов.

Обозначение [] также может использоваться в качестве сокращения для построения списка. Обычно мы строили бы список как:

myNums = 3 : 2 : 4 : 7 : 12 : 8 : []

который интерпретируется как

myNums = 3 : (2 : (4 : (7 : (12 : (8 : [])))))

но Haskell разрешает нам также использовать сокращенное

myNums = [ 3, 2, 4, 7, 12, 8 ]

как эквивалентный по смыслу, но немного приятный внешний вид, обозначение.

Неоднозначный случай

Существует неоднозначный случай, который обычно встречается: [a]. В зависимости от контекста это обозначение может означать либо "список a 's", либо "список с одним элементом, а именно a". Первое значение - это предполагаемое значение, когда [a] появляется внутри типа, тогда как второе значение является предполагаемым значением, когда [a] появляется внутри значения.

Ответ 2

  • Это (путающе, я вам даю) синтаксически перегружено, чтобы быть как конструктором типа, так и конструктором значений.

  • Это означает, что (конструктор значений) [] имеет тип, который для всех типов a является списком a (который записывается [a]). Это связано с тем, что в каждом типе есть пустой список.

  • Конструктор значений [] не набирается a -> [a], потому что в пустом списке нет элементов, и поэтому ему не нужно a, чтобы создать пустой список a. Сравните вместо Nothing :: Maybe a.

  • LYAH говорит о конструкторе типа [] с видом * -> *, в отличие от конструктора значений [] с типом [a].

Ответ 3

  • это конструктор типа (например, [Int] - это тип), а конструктор данных ([2] - структура списка).
  • Пустым списком является список, содержащий любой тип
  • [a] подобен, возможно, a, [2] похож на Just 2.
  • [] - это нулевая функция (константа), поэтому она не имеет типа функции.

Ответ 4

Чтобы сделать вещи более явными, этот тип данных:

data List a = Cons a (List a) 
            | Nil

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

  • List= [], введите конструкторы с видом * -> *
  • List a= [a], типы с видом *
  • Nil= [], значения с полиморфными типами List a и [a] соответственно
  • Cons= :, конструкторы данных с типами a -> List a -> List a и a -> [a] -> [a] соответственно
  • Cons 5 Nil= [5] или 5:[], списки отдельных элементов
  • f Nil = ...= f [] = ..., сопоставление пустых списков шаблонов
  • f (Cons x Nil) = ...= f [x] =... `, сопоставление одноуровневых списков с образцами
  • f (Cons x xs) = ...= f (x:xs) = ..., соответствие шаблону непустым спискам

В самом деле, если вы спросите ghci о [], он говорит вам почти то же определение:

> :i []
data [] a = [] | a : [a]           -- Defined in GHC.Types

Но вы не можете сами написать такое определение, потому что синтаксис списка и его конструктор типа "outfix" - это особый случай, определенный в спецификации языка.