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

StackOverflow https://stackoverflow.com/questions/775730

Вопрос

Я разработчик C #, который работает через "Реальный мир Хаскелла" чтобы по-настоящему понять функциональное программирование, чтобы, когда я выучу 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.Второе обязательное поле - это экземпляр a.
  7. (Я намеренно опустил что-либо об "определении шоу", потому что это не является частью того, на чем я хочу сосредоточиться прямо сейчас).

Исправленная интерпретация была бы следующей (изменения выделены ЖИРНЫМ шрифтом)

  1. Я определяю тип под названием "Список".
  2. Тип списка является параметризованным.Он имеет параметр единственного типа.
  3. Существует 2 конструктора значений которые могут быть использованы для создания экземпляров списка.Один конструктор значений называется "Nil", а другой конструктор значений называется "Cons".

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

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

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

  6. (Я намеренно опустил что-либо об "определении шоу", потому что это не является частью того, на чем я хочу сосредоточиться прямо сейчас).

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

Первоначальная путаница была связана с частью фрагмента, которая гласит "Минусы a (список a)".На самом деле, это та часть, которая для меня все еще неясна.

Люди указывали, что каждый элемент в строке после знака "Против" является Тип, не является значением.Таким образом, это означает, что в этой строке говорится: "Конструктор значений Cons имеет 2 поля:один типа "а", а другой типа "список а"."

Это очень полезно знать.Однако кое-что все еще неясно.Когда я создаю экземпляры с помощью конструктора значений 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.И все же это определяет ничего о том , что значение из второго поля ...это только определяет, что второе поле имеет Тип из "Целого списка".

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

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

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

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

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

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

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

Это было полезно?

Решение

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

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

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

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

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

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

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

Хорошо, но это сбивает с толку.Похоже, что первое "a" означает "первое поле является экземпляром a".,

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

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

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

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

foo :: Num a => a -> a

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

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

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

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

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

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

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

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

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

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

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

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

data Список а

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

Минусы a (List a) |
Ноль

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

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

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

Cons a (Список a)

Это типы значений, которые мы вводим в конструктор.Cons содержит две записи, одна относится к типу a, а другая - к списку типов a.

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

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

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

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

Другие советы

Аналогий обычно не хватает во всех отношениях, но поскольку вы знаете 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.)

Cons a (List a)

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

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

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

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

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

Cons a (List a)

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

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

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

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

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

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

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

Когда я создаю экземпляры с помощью конструктора Cons value, эти экземпляры "интерпретируют" первую букву "a" как означающую "поместите переданное здесь значение.

В "Cons a (список a)" и "a", и "List a" являются типами.Я не понимаю, какое отношение к этому имеет "ценность".

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top