Начало и
продолжение.
Как обычно, этот пост - литературный модуль. Его можно скопировать в .lhs файл и поэкспериментировать. Однако, нового кода здесь будет мало.
Нам понадобятся:
>-- мы автоматически выведем стандартные типы для нашего нового разборщика.
>{-# LANGUAGE GeneralizedNewtypeDeriving #-}
>-- MonadState - get/set не создаются обычным методом.
>{-# LANGUAGE StandaloneDeriving #-}
>-- использование String (type String = [Char]) в качестве аргумента реализации класса.
>{-# LANGUAGE TypeSynonymInstances -#}
>-- MonadState имеет два параметра.
>{-# LANGUAGE MultiParamTypeClasses #-}
>-- ghc требует. ;)
>{-# LANGUAGE FlexibleInstances #-}
>
>import Control.Applicative -- Applicative и Alternative для списков.
>import Control.Monad
>import Control.Monad.List -- ListT.
>import Control.Monad.State -- State и StateT.
Напомню тип разборщиков из первой главы:
[(a,String)]
Обычно, монада состояния (state monad) имеет тип
type State s a = s -> (a,s). То есть, преобразование состояния есть функция от состояния в результат и (возможно, изменённое) состояние.
Если мы обобщим наш разборщик на произвольные структуры данных, то получится вот такой тип:
>type GenInputParser i a = i -> [(a,i)]
>type Parser1 a = GenInputParser String a
Итак, наш обобщённый разборщик имеет структуру, напоминающую структуру преобразований состояния, мешается только список пар. Что приятно, мы получили возможность выполнять разбор по данным, отличным от списка, например, по деревьям или множествам. Или, даже, графам.
Мы можем сделать наш разборщик ещё более обобщённым, сделав выбор (список) более общим:
>type GenParser ch i a = i -> ch (a,i)
>type Parser a = GenParser [] String a
Посмотрите на определение списка:
*Main> :i []
data [] a = [] | a : [a] -- Defined in ‘GHC.Types’
Конструктор типа списка [] имеет один аргумент. После подстановки в параметр ch он раскроется в [(a,i)]. Параметр i преобразуется в String и, в результате, мы получим наш тип из самого начала:
type Parser a = String -> [(a, String)].
Позволю себе обратить внимание, что здесь мы обобщили методы разбора и пересоздали старый тип из более общего.
Теперь посмотрим на определение преобразователя монад StateT:
newtype StateT s (m :: * -> *) a
= StateT {runStateT :: s -> m (a, s)}
Отлично видно, как похожи GenParser и StateT. newtype здесь используется для указания компилятору, что StateT новый тип, для него будут использованы свои реализации классов типов.
Попробуем собрать разборщик из предыдущей главы, но используя преобразователи. Это очень просто:
>-- NX добавлено, чтобы 1) отличать от других типов и 2) для молодёжности.
>newtype ParserNX a = ParserNX { runParserNX :: StateT String [] a}
> -- GeneralizedNewtypeDeriving
> deriving (Functor, Monad, Applicative, Alternative)
>-- standalone deriving:
>deriving instance MonadState String ParserNX
Вот такая магия. При создании сего текста я просто следовал указаниям компилятора в виде ошибок типов.
На данный момент мы уже имеем кучу определённых примитивов - many, some, <$>, <*>, <|> и тому подобное. Всё определено так, как мы делали в предыдущих главах.
Определим недостающие примитивы и метод разбора:
>item :: ParserNX Char
>item = do
> (c:cs) <- get
> put cs
> return c
>char :: Char -> ParserNX Char
>char c = check (==c) item
>check :: (a -> Bool) -> ParserNX a -> ParserNX a
>check pred p = do
> a <- p
> if pred a then return a else empty
>parse :: String -> ParserNX a -> Either String a
>parse text (ParserNX p) = case runStateT p text of
> [] -> Left "no parse"
> ((a,""):_) -> Right a
> ((_,rest):_) -> Left $ "error somewhere near "++take 20 rest++"..."
Вот результат запусков:
*Main Control.Applicative> parse "aabbabba" (many (char 'a' <|> char 'b'))
Loading package transformers-0.4.1.0 ... linking ... done.
Loading package mtl-2.2.1 ... linking ... done.
Right "aabbabba"
*Main Control.Applicative> parse "aabbabbac" (many (char 'a' <|> char 'b'))
Left "error somewhere near c..."
Позволю себе подвести итог.
Итак, синтаксический разбор - преобразование состояния (текста, в данном конкретном случае) с вычислением промежуточного результата, обрамлённое в тип, поддерживающий недетерминированный выбор (список в нашем конкретном случае).
Мы выяснили это, обобщив конкретный тип.
По структуре типа (и необходимым операциям, определяющим его) можно выяснить вложение комбинаторов монад, что приводит к уменьшению кода программы.
