Пожалуйста, подтвердите или исправьте мою "английскую интерпретацию" этого фрагмента кода на Haskell

Question

Я разработчик C #, который работает с "Real World Haskell" , чтобы по-настоящему понять функциональное программирование, так что, когда я изучу F #, я действительно поймаю его, а не просто "напишу" C # код в F # ", так сказать.

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

Теперь я верю, что я действительно понимаю это, и я написал подробное «английское толкование» ниже. Не могли бы вы, гуру Хаскелла, подтвердить это понимание или указать, что я пропустил?

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

Фрагмент кода на Haskell

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

РЕДАКТИРОВАТЬ: После некоторых ответов я вижу одно недоразумение, которое я сделал, но не совсем ясно о правилах "разбора" в Haskell, которые исправили бы эту ошибку. Поэтому ниже я включил свое первоначальное (неправильное) толкование, за которым последовало исправление, за которым последовал вопрос, который мне до сих пор неясен.

РЕДАКТИРОВАТЬ: Вот мой оригинальный (неправильный) "английский перевод" фрагмента

1. Я определяю тип с именем «Список».
2. Тип списка параметризован. У него один параметр типа.
3. Существует 2 конструктора значений, которые можно использовать для создания экземпляров List. Один конструктор значений называется «Nil», а другой конструктор значений - «Cons».
4. Если вы используете конструктор значений "Nil", то полей нет.
5. Конструктор значения "Cons" имеет параметр одного типа.
6. Если вы используете конструктор значений "Cons", необходимо указать 2 поля. Первое обязательное поле - это экземпляр List. Второе обязательное поле - это экземпляр.
7. (Я намеренно пропустил что-либо об «определении Шоу», потому что это не часть того, на чем я хочу сейчас сосредоточиться).

Исправленная интерпретация будет выглядеть следующим образом (изменения выделены жирным шрифтом)

8. Я определяю тип с именем «Список».
9. Тип списка параметризован. Это имеет параметр одного типа.
10. Есть 2 конструктора значений которые могут быть использованы для создания экземпляров из списка. Один конструктор значения называется "ноль" и другое значение Конструктор называется "Минусы".

11. Если вы используете конструктор значений "Nil", то поля отсутствуют.

    5. (эта строка была удалена ... она не точная) Конструктор значения "Минусы" имеет параметр одного типа.

12. Если вы используете конструктор значений "Минусы", есть 2 поля который должен быть предоставлен. Первый Обязательное поле является экземпляром. Второе обязательное поле экземпляр "List-of-a".

13. (Я намеренно пропустил что-нибудь об «определении Шоу», потому что это не часть того, на чем я хочу сейчас сосредоточиться).

Вопрос, который до сих пор неясен

Первоначальная путаница касалась части фрагмента, которая гласит «Минусы a (Список а)». На самом деле, это та часть, которая мне до сих пор не ясна.

Люди отмечают, что каждый элемент в строке после жетона "Против" является типом , а не значением. Это означает, что в этой строке написано: «Конструктор значений« Cons »имеет 2 поля: одно типа« a », а другое типа list-of-a».

Это очень полезно знать. Однако что-то все еще неясно. Когда я создаю экземпляры, используя конструктор значений Cons, эти экземпляры «интерпретируют» первое «a» как означающее «поместите здесь переданное значение». Но они не интерпретируют второе «а» одинаково.

Например, рассмотрим этот сеанс GHCI:

*Main> Cons 0 Nil
Cons 0 Nil
*Main> Cons 1 it
Cons 1 (Cons 0 Nil)
*Main> 

Когда я набираю «Cons 0 Nil», он использует конструктор значения «Cons» для создания экземпляра List. Из 0 он узнает, что параметром типа является "Integer". Пока что нет путаницы.

Тем не менее, также определяет, что значение первого поля Cons равняется 0. Однако оно определяет ничто относительно значения второго поля ... оно только определяет, что второе поле имеет тип"List Integer".

Итак, мой вопрос: почему «a» в первом поле означает «тип этого поля -« a » и значение этого поля -« a », тогда как« a » во втором поле означает только"тип этого поля -" Список ""?

РЕДАКТИРОВАТЬ: Я думаю, что я уже видел свет, благодаря нескольким ответам. Позвольте мне сформулировать это здесь. (И если каким-то образом все еще неверно каким-либо образом, пожалуйста, обязательно сообщите мне!)

Во фрагменте «Cons a (Список a)» мы говорим, что конструктор значения «Cons» имеет два поля, и что первое поле имеет тип «a», а второе поле имеет тип « Список ".

Это все, что мы говорим! В частности, мы говорим НИЧЕГО о ценностях! Это ключевой момент, который я упустил.

Позже мы хотим создать экземпляр, используя конструктор значений «Cons». Мы вводим это в интерпретатор: «Минусы 0 ноль». Это явно указывает конструктору значений Cons использовать 0 для значения первого поля и использовать Nil в качестве значения для второго поля.

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

Спасибо всем за полезные ответы. И, как я уже сказал, если что-то еще не работает, пожалуйста, обязательно расскажите мне об этом. Спасибо.

Answer 1

• Конструктор значения "Cons" имеет параметр одного типа.

Нет: вы уже параметризовали его, когда объявили data List a. Одним из эффективных свойств этого является то, что если у меня есть Nil :: List Int, я не могу поменять его на Nil :: List Char.

• Если вы используете конструктор значений «Минусы», необходимо указать 2 поля. Первое обязательное поле - это экземпляр List. Второе обязательное поле - это экземпляр.

Вы поменялись местами: первое обязательное поле - это экземпляр a, второе поле - это экземпляр List.

Эта глава из реального мира Haskell может представлять интерес.

Спасибо. Это глава, в которой я сейчас нахожусь. Итак ... когда в коде написано «Cons a (Список a)», я подумал, что часть «Cons a» указывает на то, что конструктор значения Cons был параметризован. Они еще не охватили синтаксис для параметризованных типов, поэтому я догадался, что синтаксис должен требовать повторения «a», если вы собираетесь использовать a. Но вы говорите, что это не нужно? И поэтому это не то, что означает «а»?

Неа. После того, как мы объявили параметр в нашем типе, мы можем использовать его повторно, чтобы сказать «этот тип должен использоваться там». Это немного похоже на сигнатуру типа a -> b -> a: a параметризует тип, но тогда я должен использовать то же самое, что и возвращаемое значение.

ОК, но это сбивает с толку. Кажется, что первое «а» означает «первое поле является экземпляром»,

Нет, это не правда. Это просто означает, что тип данных параметризуется по некоторому типу a.

и это ТАКЖЕ означает «первое поле имеет то же значение, что и значение, которое они передали для a». Другими словами, он указывает значение типа AND.

Нет, это тоже неправда.

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

foo :: Num a => a -> a

Это довольно стандартная подпись для функции, которая берет число, что-то с ним делает и дает вам другой номер. Что я на самом деле подразумеваю под «числом» в языке Haskell, тем не менее, это некоторый произвольный тип «a», который реализует класс «Num».

Таким образом, это разбирает на английский:

Пусть a указывает тип, реализующий класс типов Num, тогда сигнатурой этого метода является один параметр с типом a, а возвращаемое значение типа a

Нечто подобное происходит с данными.

Мне также кажется, что экземпляр List в спецификации Cons также сбивает вас с толку: будьте очень осторожны при разборе этого: тогда как Cons задает конструктор, который по сути является шаблоном, который Haskell собирается обернуть данные into (List a) выглядит как конструктор, но на самом деле это просто тип, такой как Int или Double. a - это тип, а не значение в каком-либо смысле этого термина.

Редактировать: В ответ на самое последнее редактирование.

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

Конструкторы данных на Haskell немного странные, потому что вы определяете сигнатуру конструктора, и вам не нужно создавать никаких других скаффолдингов. Типы данных в Haskell не имеют представления о переменной-члене. (Примечание: есть альтернативный синтаксис, к которому такой способ мышления более поддается, но давайте пока проигнорируем его).

Другое дело, что код на Haskell плотный; его тип подписи таковы. Поэтому ожидайте увидеть один и тот же символ, повторно используемый в разных контекстах. Вывод типа также играет здесь большую роль.

Итак, вернемся к вашему типу:

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

Я разбил это на несколько частей:

data <b>List a</b>

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

<b>Cons</b> a (List a) |
<b>Nil</b>

Это имя конструктора данных. Это НЕ тип . Мы можем, однако, сопоставить шаблон с этим, ала:

foo :: List a -> Bool
foo Nil = True

Обратите внимание, что List a является типом в сигнатуре, а Nil является и конструктором данных, и "вещью", для которой мы сопоставляем шаблон.

Cons <b>a (List a)</b>

Это типы значений, которые мы вставляем в конструктор. Минусы имеет две записи, одна из которых имеет тип a, а другая имеет тип List a.

Итак, мой вопрос: почему «а» в первом поле означает «тип этого поля -« а », а значение этого поля -« а », тогда как« а »во втором поле означает только "тип этого поля 'Список' '?

Простой: не думайте, что мы указываем тип; думаю, что Haskell выводит тип из этого. Таким образом, для наших целей мы просто вставляем 0, а Nil - во второй раздел. Затем Хаскелл смотрит на наш код и думает:

• Хм, интересно, какой тип минусов 0, ноль
• Ну, Cons это конструктор данных для List a. Интересно, что это за тип List a
• Что ж, в первом параметре используется a, так как первый параметр - это Int (еще одно упрощение; 0 на самом деле странная вещь, типизированная как Num), так что это означает, что a - это Num
• Эй, ну, это также означает, что типом Nil является List Int, хотя там нет ничего, что могло бы сказать, что

(Обратите внимание, что на самом деле это не так, как это реализовано. Haskell может делать много странных вещей при выводе типов, что частично объясняет, почему сообщения об ошибках отстой.)

Answer 2

Аналогии обычно отсутствуют во всех отношениях, но, поскольку вы знаете C #, я подумал, что это может быть полезно.

Вот как я бы описал определение List a в C #, может быть, это проясняет некоторые вещи (или, скорее, еще больше сбивает вас с толку).

class List<A>
{
}

class Nil<A> : List<A>
{
    public Nil() {}
}

class Cons<A> : List<A>
{
    public A Head;
    public List<A> Tail;

    public Cons(A head, List<A> tail)
    {
        this.Head = head;
        this.Tail = tail;
    }
}

Как видите,

• тип List имеет параметр одного типа (<A>),
• конструктор Nil не имеет параметров,
• и конструктор Cons имеет два параметра: значение head типа A и значение tail типа List<A>.

Теперь в Haskell Nil и Cons - это просто конструкторы для типа данных List a, в C # они также являются типами сами по себе, поэтому аналогия не удалась.

Но я надеюсь, что это даст вам некоторое интуитивное представление о том, что представляют различные A.

(И, пожалуйста, прокомментируйте, как это ужасное сравнение не оправдывает типы данных Haskell.)

Answer 3

Да, синтаксис данных немного сбивает с толку, потому что он наказывает имена и типы и на самом деле не делает синтаксическое различие между ними. В частности, в определении конструктора, например:

Cons a (List a)

Первое слово - это имя конструктора; любое другое слово - это имя некоторого предварительно объявленного типа. Таким образом, a и List a уже находятся в области видимости (a был введен в область действия a в "data List a"), и вы говорите, что это типы параметров. Их роль можно лучше продемонстрировать, заявив то же самое, используя синтаксис записи :

Cons { headL :: a, tailL :: List a }

т.е. значение типа List Int, , если оно было построено с помощью конструктора Cons, имеет два поля: Int и List Int. Если он был построен с Nil, у него нет полей.

Answer 4

5 неверно, и я бы сказал 6 следующим образом, чтобы заменить оба:

Cons {1} a {2} (List a) {3} - это конструктор с именем Cons (часть перед {1}) для значения типа List a (данные List часть), для которого требуется два значения: одно типа a (часть между {1} ​​и {2}) и один из типов List a (часть между {2} и {3}).

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

Answer 5

Cons a (List a)

Первое поле Cons является значением типа "a". Второе - это значение типа "List a", то есть список, параметризованный с тем же типом, что и параметр текущего списка.

Answer 6

Когда я набираю «Cons 0 Nil», он использует конструктор значений «Cons» для создания экземпляра List. Из 0 он узнает, что параметром типа является «Integer». Пока что нет путаницы.

Тем не менее, он также определяет, что значение первого поля Cons равно 0. И все же ничего не определяет значение второго поля ... он только определяет, что второе поле имеет тип «List Integer» .

Нет, он определяет, что значение второго поля равно Nil. Учитывая ваше определение, Nil является значением типа List a. Поэтому так же Cons 0 Nil. А в Cons 1 it значение второго поля равно it; то есть Cons 0 Nil. Это именно то, что показывает REPL: Cons 1 (Cons 0 Nil).

Answer 7

Я посмотрел на ваш отредактированный вопрос.

Когда я создаю экземпляры с использованием минусов конструктор значения, эти экземпляры «интерпретировать» первое «а» как значение msgstr "поместить переданное здесь значение.

В "Cons a (Список a)" оба типа "a" и "List a" являются типами. Я не понимаю, какое значение имеет «ценность».

Когда я набираю "Минусы 0 ноль", он использует Значение конструктора "Минусы" для создания экземпляр списка. С 0 он учится что тип параметра "Целое число". Пока что нет путаницы.

Однако это также определяет, что Значение первого поля минусов равно 0. Но это ничего не определяет о значение второго поля ... это только определяет, что второе поле имеет тип "Список целых чисел".

Значение второго поля: Nil.

Итак, мой вопрос: почему "а" в первое поле означает "тип этого поле является «а» и значение этого поле «а», а «а» во втором поле означает только «тип этого поле 'Список' '?

«a» в первом поле означает «тип этого поля -« a »». «Список a» во втором поле означает «тип этого поля -« Список a »». В случае «Минусы 0 ноль» выше, «а» подразумевается как «целое число». Таким образом, "Cons a (List a)" становится "Cons Integer (List Integer)". 0 является значением типа Integer. Nil - это значение типа «List Integer».

значение этого поля 'a'

Я не понимаю, что вы подразумеваете под этим. «а» - переменная типа; какое это имеет отношение к значениям?

Answer 8

Просто чтобы дать вам дополнительную «помощь», если вы все еще смотрите эту ветку. У Haskell есть несколько соглашений, которые путают представления других людей о том, как все должно быть сделано - в Haskell параметризованный тип настолько общепринят, что его обычно считают функцией уровня типа. Аналогично, конструкторы значений рассматриваются как «специальные» функции, которые также допускают сопоставление с образцом, в дополнение к их «принимают значение (или больше) и создают значение в результате».

Еще одна «забавная» характеристика Haskell заключается в том, что он не (явно или неявно) оценивает аргументы функции, , даже если этот аргумент указан в скобках . Позвольте мне заявить, что это немного иначе: функции Haskell не оценивают аргументы в скобках перед другими аргументами. Аргументы помещаются в скобки только для целей группировки, а не для того, чтобы они оценивались «первыми». Haskell назначает аргументы («применяет») функцию с более высоким приоритетом, чем любая другая операция - даже выше, чем неявное применение функции одного из своих собственных аргументов. Вот почему у конструктора Cons есть второй знак аргумента вокруг второго аргумента, (List a) - чтобы сообщить компилятору, что у Cons есть два аргумента, а не three . Скобки предназначены только для группировки, а не для старшинства!

Как дополнительная тема, будьте осторожны с типами в F #. Поскольку F # имеет свои корни в ML, его параметризованные типы имеют параметры впереди - int list, а не (List Int) сзади! Haskell делает это по-другому, потому что Haskell выполняет те же функции - сначала функцию, затем аргументы функции. Это поощряет шаблон общего использования и объясняет, почему типы и конструкторы значений Haskell пишутся с заглавной буквы, чтобы напомнить вам, что вы имеете дело с типом / классом.

Хорошо, я закончил; спасибо, что позволили мне поместить эту огромную Стену О 'Текст в вашу собственность ...