неділя, 31 березня 2013 р.

Легко и непринужденно пишем Regex

Итак мы уже поняли зачем Эрик использует список и ничто нам не мешает двигаться дальше. Как вы уже знаете парсер имеет тип Parser a, где a – это тип значения, которое может вернуть парсер, если ему скормить строку, а что если a – это Parser 'a, то есть все целиком имеет тип Parser (Parser a)?

Ниже пример того, как это может выглядеть. Пока что используем Dynamic, так как еще не ясно, что это будет.

import Data.Dynamic

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

regex :: Parser (Parser Dynamic)
regex = undefined

parser :: String -> Parser Dynamic
parser s = case parse regex s of
             (p, _):_ -> p
             _ -> error "Failed to parse 'regex'"

Дело за малым: остается вместо undefined вставить что-то полезное и получим реализацию мотора регулярных выражений. А это действительно просто. Тут доказательство. Всего 170 строк, никаких дополнительных библиотек. Я думаю это очень хороший показатель выразительной мощи Хаскеля: не тьюринг полнотой единой.

З.Ы. Я думаю гуру могут еще предложить идеи как можно сократить код без потери читабельности. Высказывайте пожалуйста. parsec не предлагать – эксперимент утратит чистоту.

Немає коментарів:

Дописати коментар