Аппликативный парсер застрял в бесконечном цикле - PullRequest
Новая
       143

Аппликативный парсер застрял в бесконечном цикле

2 голосов
/ 30 октября 2019

Я пытаюсь реализовать свой собственный анализатор Applicative, вот код, который я использую: 

{-# LANGUAGE ApplicativeDo, LambdaCase #-}

module Parser where

-- Implementation of an Applicative Parser

import Data.Char
import Control.Applicative (some, many, empty, (<*>), (<$>), (<|>), Alternative)

data Parser a = Parser { runParser :: String -> [(a, String)] }

instance Functor Parser where
  -- fmap :: (a -> b) -> (Parser a -> Parser b)
  fmap f (Parser p) = Parser (\s -> [(f a, s') | (a,s') <- p s])

instance Applicative Parser where
  -- pure :: a -> Parser a
  -- <*> :: Parser (a -> b) -> Parser a -> Parser b
  pure x = Parser $ \s -> [(x, s)]
  (Parser pf) <*> (Parser p) = Parser $ \s -> 
               [(f a, s'') | (f, s') <- pf s, (a, s'') <- p s']

instance Alternative Parser where
  -- empty :: Parser a
  -- <|> :: Parser a -> Parser a -> Parser a
  empty = Parser $ \_s -> []
  (Parser p1) <|> (Parser p2) = Parser $ \s ->
      case p1 s of [] -> p2 s
                   xs -> xs

char :: Char -> Parser Char
char c = Parser $ \case (c':cs) | c == c' -> [(c,cs)] ; _ -> []

main = print $ runParser (some $ char 'A') "AAA"

Когда я его запускаю, он застревает и никогда не возвращается. Разобравшись с проблемой, я определил причину моей реализации метода <|>. Если я использую следующую реализацию, то все пойдет так, как ожидалось: 

instance Alternative Parser where
  empty = Parser $ \_s -> []
  p1 <|> p2 = Parser $ \s ->
    case runParser p1 s of [] -> runParser p2 s
                           xs -> xs

Эти две реализации, на мой взгляд, вполне эквивалентны. Я предполагаю, что это может иметь отношение к ленивой схеме оценки Haskell. Может кто-нибудь объяснить, что происходит?

1 Ответ

6 голосов
/ 30 октября 2019

Факт "звезда": в вашей реализации (<*>): 

Parser p1 <*> Parser p2 = ...

... мы должны вычислить достаточно, чтобы знать, что оба аргумента на самом деле являются приложениями конструктора Parser к чему-то, прежде чем мыможет перейти к правой части уравнения.

Факт "труба строгая": в этой реализации: 

Parser p1 <|> Parser p2 = ...

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

Факт "труба ленивый": в этой реализации: 

p1 <|> p2 = Parser $ ...

... мы можем перейти к правой части знака равенства, не выполняя никаких вычислений для p1 или p2.

Это важно, потому что: 

some v = some_v where
    some_v = pure (:) <*> v <*> (some_v <|> pure [])

Давайте возьмем вашу первую реализацию, ту, о которой мы знаем факт «строго по трубам». Мы хотим знать, является ли some_v приложением Parser к чему-либо. Благодаря факту «звезда» мы должны знать, являются ли pure (:), v и some_v <|> pure [] приложениями Parser к чему-либо. Чтобы узнать это последнее, на самом деле «строго по трубе», мы должны знать, являются ли some_v и pure [] приложениями Parser к чему-либо. Упс! Мы только что показали, чтобы узнать, является ли some_v приложением Parser к чему-либо, нам нужно знать, является ли some_v приложением Parser к чему-то - бесконечному циклу!

Вкл. с другой стороны, в вашей второй реализации, чтобы проверить, является ли some_v Parser _, мы все равно должны проверить pure (:), v и some_v <|> pure [], но благодаря факту "труба ленивый", это все нам нужно проверить - мы можем быть уверены, что some_v <|> pure [] - это Parser _ без предварительной рекурсивной проверки, что some_v и pure [] - это.

(И затем вы будетеузнать о newtype - и еще раз запутаться, когда переход с data на newtype заставляет оба работать с реализацией!)

...