Чисто прикладной анализатор с использованием альтернативы

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

{-# LANGUAGE Rank2Types #-}

import Control.Applicative (Alternative(..))
import Data.Foldable (asum, traverse_)

Тип:

newtype Parser a = Parser {run :: forall f. Alternative f => (Char -> f ()) -> f a}

Экземпляры:

instance Functor Parser where
    fmap f (Parser cont) = Parser $ \char -> f <$> cont char

instance Applicative Parser where
    pure a = Parser $ \char -> pure a
    (Parser contf) <*> (Parser cont) = Parser $ \char -> (contf char) <*> (cont char)

instance Alternative Parser where
    empty = Parser $ \char -> empty
    (Parser cont) <|> (Parser cont') = Parser $ \char -> (cont char) <|> (cont' char)
    some (Parser cont) = Parser $ \char -> some $ cont char
    many (Parser cont) = Parser $ \char -> many $ cont char

Некоторые примеры парсеров:

item = Parser $ \char -> asum $ map (\c -> c <$ char c) ['A'..'z']
digit = Parser $ \char -> asum $ map (\c -> c <$ char (head $ show c)) [0..9]
string s = Parser $ \char -> traverse_ char s

К сожалению, мне трудно понять, как я могу использовать эту реализацию парсера. В частности, я не понимаю, что должно/могло быть Char -> f () и как я мог бы использовать это для простого разбора, например. чтобы добавить цифру из входной строки. Я хотел бы конкретный пример, если это возможно. Может ли кто-нибудь пролить свет?


parsing haskell higher-rank-types applicative alternative-functor
person Ana    schedule 26.02.2016    source источник
comment
Разве конец ссылки, которую вы связали, не дает два примера того, чем может быть f?   -  person Daniel Wagner    schedule 27.02.2016
comment
В частности, я не понимаю, каким должен/может быть Char -› f() - это не просто Char -> f (), это forall f . Alternative f => (Char -> f ()) -> f a. Вы не можете рассматривать здесь что-то типа Char -> f() изолированно — вы должны рассматривать всю функцию сразу (из-за универсальной квантификации). Вы можете рассматривать этот Parser как наименьшую верхнюю границу всех (альтернативных) синтаксических анализаторов - он не реализует никаких функций, вместо этого он полагается на семантику любого типа f, для которого в конечном итоге создается экземпляр.   -  person user2407038    schedule 27.02.2016

Ответы (2)


arrow_upward
2
arrow_downward

В forall f. Alternative f => (Char -> f ()) -> f a Char -> f () – это то, что вам предоставляется. Ваша миссия, если вы решите принять это, состоит в том, чтобы затем превратить это в f a, используя только эти два бита:

  • Функция Char -> f () (т. е. способ анализа одного символа: если следующий символ соответствует аргументу, анализ завершается успешно, иначе — нет.)
  • Alternative экземпляр f

Итак, как бы вы разобрали одну цифру в Int? Он должен быть в форме

digit :: Parser Int
digit = Parser $ \parseChar -> _

В _ нам нужно создать f Int, используя комплект parseChar :: Char -> f () и Alternative f. Мы знаем, как анализировать один символ '0': parseChar '0' завершается успешно, если следующим символом является '0'. Мы можем преобразовать его в значение Int через экземпляр Functor f, получив

digit0 :: Parser Int
digit0 = Parser $ \parseChar -> fmap (const 0) (parseChar '0')

Но f — это не просто Functor, это также Alternative, поэтому мы можем написать digit в длинной форме как

digit :: Parser Int
digit = Parser $ \parseChar -> fmap (const 0) (parseChar '0') <|>
                               fmap (const 1) (parseChar '1') <|>  
                               fmap (const 2) (parseChar '2') <|>  
                               fmap (const 3) (parseChar '3') <|>  
                               fmap (const 4) (parseChar '4') <|>  
                               fmap (const 5) (parseChar '5') <|>  
                               fmap (const 6) (parseChar '6') <|>  
                               fmap (const 7) (parseChar '7') <|>  
                               fmap (const 8) (parseChar '8') <|>  
                               fmap (const 9) (parseChar '9')

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

digit :: Parser Int
digit = Parser $ \parseChar -> asum [fmap (const d) (parseChar c) | d <- [0..9], let [c] = show d]

который мы можем упростить, заметив, что fmap (const x) f можно записать как x <$ f, что дает

digit :: Parser Int
digit = Parser $ \parseChar -> asum [d <$ parseChar c | d <- [0..9], let [c] = show d]
person Cactus    schedule 29.02.2016

arrow_upward
-1
arrow_downward

Часть Char -> f () представляет собой сопоставление одного символа. А именно, если вы сделаете char 'c', он совпадет с 'c' и потерпит неудачу во всем остальном.

Чтобы использовать его, вы можете преобразовать его, скажем, в Parsec:

convert :: Parser a -> Parsec a
convert p = run p anyChar

p по существу относится к типу forall f. Alternative f => (Char -> f ()) -> f a, который специализируется на (Char -> Parsec ()) -> Parsec a. Мы передаем anyChar, и оно создаст значение Parsec a, используя anyChar и любые операции Alternative.

По сути, Parser a — это функция, которая при задании соответствия одному символу и экземпляру Alternative выдает значение Alternative.

person PyRulez    schedule 26.02.2016