Как я могу написать более общую (но эффективную) версию takeWhile1 от attoparsec?

Data.Attoparsec.Text экспортирует takeWhile и takeWhile1:

takeWhile :: (Char -> Bool) -> Parser Text

Потребляйте ввод, пока предикат возвращает True, и возвращайте потребляемый ввод.

Этот парсер не дает сбоев. Он вернет пустую строку, если предикат возвращает False для первого введенного символа.

[...]

takeWhile1 :: (Char -> Bool) -> Parser Text

Потребляйте ввод, пока предикат возвращает True, и возвращайте потребляемый ввод.

Этот синтаксический анализатор требует, чтобы предикат был успешным по крайней мере для одного символа ввода: он потерпит неудачу, если предикат никогда не вернет True или если не осталось ввода.

Документация attoparsec рекомендует пользователю

По возможности используйте парсеры, ориентированные на Text, например. takeWhile1 вместо many1 anyChar. Существует примерно 100-кратная разница в производительности между двумя типами синтаксических анализаторов.

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

takeWhileLo :: (Char -> Bool) -> Int -> Parser Text
takeWhileLo f lo = undefined

который проанализирует минимум lo символов, удовлетворяющих предикату f, где lo – произвольное неотрицательное целое число.

Я просмотрел takeWhile1, но он использует набор функций, закрытых для Data.Attoparsec.Text.Internal, и не кажется легко обобщаемым.

Я придумал следующую аппликативную реализацию:

{-# LANGUAGE OverloadedStrings #-}

import           Prelude                  hiding ( takeWhile )

import           Control.Applicative             ( (<*>) )
import           Data.Text                       ( Text )
import qualified Data.Text           as T

import           Data.Attoparsec.Text

takeWhileLo :: (Char -> Bool) -> Int -> Parser Text
takeWhileLo f lo =
  T.append . T.pack <$> count lo (satisfy f) <*> takeWhile f

Он работает как рекламируется,

λ> parseOnly (takeWhileLo (== 'a') 4) "aaa"
Left "not enough input"
λ> parseOnly (takeWhileLo (== 'a') 4) "aaaa"
Right "aaaa"
λ> parseOnly (takeWhileLo (== 'a') 4) "aaaaaaaaaaaaa"
Right "aaaaaaaaaaaaa"

но необходимость упаковки промежуточного списка результатов, возвращаемых count, меня беспокоит, особенно для случаев, когда lo велико... Кажется, это противоречит рекомендации

используйте парсеры, ориентированные на Text, когда это возможно [...]

Я что-то упускаю? Есть ли более эффективный/идиоматический способ реализации такого комбинатора takeWhileLo?


haskell parser-combinators attoparsec
person jub0bs    schedule 30.06.2015    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Parser — это монада, поэтому вы можете просто проверить возвращаемое значение и потерпеть неудачу, если длина неверна:

takeWhileLo :: (Char -> Bool) -> Int -> Parser Text
takeWhileLo f lo = do
  text <- takeWhile f
  case T.compareLength text lo of
    LT -> empty
    _  -> return text

compareLength из пакета text. Это более эффективно, чем сравнивать длину text, потому что compareLength может вызвать короткое замыкание.

person András Kovács    schedule 30.06.2015
comment
Думаю, я был слишком сосредоточен на реализации takeWhileLo в качестве комбинатора приложений. Ваше предложение имеет смысл. Спасибо. - person jub0bs; 30.06.2015
comment
Вы имели в виду mempty вместо empty? - person jub0bs; 01.07.2015
comment
Это также работает. У нас есть экземпляры Monoid, Alternative и MonadPlus для Parser, а mempty, empty и mzero — все явные сбои. - person András Kovács; 01.07.2015
comment
В этом есть смысл. Еще раз спасибо. - person jub0bs; 01.07.2015