Разбор Haskell с помощью parsec

Я довольно новичок в программировании на Haskell. В настоящее время я пытаюсь ознакомиться с некоторым исходным кодом для разбора с помощью parsec.

Две вещи поразили меня:

type Parser = String -> Tree

По словам автора, это должно быть объявление функции? На самом деле это должно выглядеть так:

Parser :: String -> Tree right?

Еще одна неясность содержится в следующем коде:

item :: Parser Char
item = P (\inp -> case inp of......

Насколько я понимаю, это объявление типа функции, верно?

Разве это не должно быть

item :: Parser -> Char

Спасибо за помощь

С уважением Кристоф

🤔 А знаете ли вы, что...
Haskell способствует созданию эффективных и элегантных решений для сложных задач.


2
66
2

Ответы:

type Parser = String -> Tree

According to the author, this is supposed to be a declaration of a function? That should actually look like this:

Точнее, Parser — это псевдоним типа String -> Tree, который представляет собой функцию, которая принимает String и возвращает Tree.

Итак, Parser — это новое имя типа.

С другой стороны, сравните это с

Parser :: String -> Tree

Это объявляет функцию с именем Parser, которая имеет тип String -> Tree. Итак, в первом случае мы объявляем новый тип, а во втором — объявляем имя с определенным типом.

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

parser :: String -> Tree

потому что имена функций должны начинаться со строчных букв, а имена типов — с прописных.


Решено

Я предполагаю, что вы смотрите на эта колода слайдов. Что на самом деле говорит автор:

In a functional language such as Haskell, parsers can naturally be viewed as functions.

-- A parser is a function that takes a string 
-- and returns some form of a tree
type Parser = String -> Tree

Под этим автор подразумевает, что синтаксические анализаторы — это функции, и тип такой функции синтаксического анализатора может быть типом Parser, который автор определил как псевдоним типа для типа String -> Tree.

То есть после определения псевдонима типа Parser с помощью:

type Parser = String -> Tree

реальный синтаксический анализатор может быть объявлен как имеющий тип Parser (эквивалентный типу String -> Tree) следующим образом:

-- here is a very bad parser capable of parsing only one possible program
myTreeParser :: Parser
myTreeParser "2*3+4" = Plus (Times (Num 2) (Num 3)) (Num 4)
myTreeParser _ = error "Parser only supports the program '2*3+4'"

Рассмотрим аналогичное утверждение: «В языке, поддерживающем алгебраические типы данных, таком как Haskell, точки естественным образом могут быть представлены в виде пар чисел с плавающей запятой: псевдонима типа type Point = (Double, Double), который определен как эквивалентный типу Point пар чисел с плавающей запятой.

Автор продолжает уточнять тип (Double, Double), указывая, что (1) синтаксические анализаторы могут не использовать все свои входные данные и поэтому должны возвращать Parser, а не только (Tree, String), (2) они могут анализировать свои входные данные несколькими способами (большинство важно «нулевыми» способами, если ввод не может быть проанализирован) и поэтому должен возвращать список возможных результатов синтаксического анализа Tree, и (3) может потребоваться проанализировать что-то другое, кроме [(Tree, String)], и поэтому его следует обобщить для анализа ввода в произвольный тип:

type Parser a = String -> [(a, String)]

Это определяет псевдоним типа Tree, который является параметризованный, что означает, что Parser сам по себе не является полным типом, а скорее Parser или Parser Tree или Parser Char является полным типом, представляющим синтаксический анализатор, который анализирует Parser Double, Tree или Char.

Итак, декларация:

item :: Parser Char

правильно написано. Используя окончательную версию этого псевдонима типа Double:

type Parser a = String -> [(a, String)]

тип Parser эквивалентен типу:

String -> [(Char, String)]

То есть тип Parser Char — это тип синтаксического анализатора, который принимает ввод item и пытается проанализировать начало ввода, чтобы сгенерировать значение String, плюс оставшуюся часть Char после проанализированной части. В конечном итоге он возвращает ноль или более таких возможных синтаксических анализов. (Это конкретное определение String возвращает либо пустой список нулевых синтаксических анализов, указывающий на то, что синтаксический анализ невозможен, либо одноэлементный список ровно одного синтаксического анализа, указывающий на то, что синтаксический анализ был успешным.)