有没有办法在 idris lightyear 库中编写 chainl 函数？

Question

我正在尝试在 Idris 中形式化基于正则表达式的字符串搜索工具（当前状态 here). But I'm fighting with the problem of parsing regular expressions. I've tried to build a small parsing library but gave up on this in favor to use Lightyear，一个用于 Idris 的解析组合器库。

因为我习惯了 Haskell，所以我尝试使用与使用 Parsec 时类似的策略。我的主要问题是如何处理 Lightyear 解析器的左递归？我已经尝试了几种编码，但几乎所有解析器最终都会循环并导致生成的代码出现分段错误。

Answer 1

我不了解 Lightyear，但我成功地将 Parsec 移植到 Idris：

module Parser

data Parser : Type -> Type where
     P : (String -> List (a, String)) -> Parser a

unP : Parser a -> String -> List (a, String)
unP (P f) = f

total stripPrefix : (Eq a) => List a -> List a -> Maybe (List a)
stripPrefix [] ys = Just ys
stripPrefix (x::xs) (y::ys) = if (x == y) then stripPrefix xs ys else Nothing
stripPrefix _ _  = Nothing

total token : String -> Parser ()
token tk = P $ \s => case stripPrefix (unpack tk) (unpack s) of
      Just s' => [((), pack s')]
      Nothing => []

total skip : Parser ()
skip = P $ \s => case unpack s of
     [] => []
     (_::s') => [((), pack s')]

instance Functor Parser where
  map f p = P $ \s => map (\(x, s') => (f x, s')) (unP p s)

instance Applicative Parser where
  pure x = P $ \s => [(x, s)]
  (P pf) <*> (P px) = P $ \s => concat (map (\(f, s') => map (\(x, s'') => (f x, s'')) (px s')) (pf s))

instance Alternative Parser where
  empty = P $ \s => []
  (P p1) <|> (P p2) = P $ \s => case p1 s of
     [] => p2 s
     results => results

instance Monad Parser where
  px >>= f = P $ \s => concat (map (\(x, s') => unP (f x) s') (unP px s))

total runParser : Parser a -> String -> Maybe a
runParser (P p) s = case p s of
  [(x, "")] => Just x
  _         => Nothing

这允许直接复制粘贴实现 chainl:

chainl1 : Parser a -> Parser (a -> a -> a) -> Parser a
chainl1 p op = p >>= rest
  where
    rest x = do { f <- op; y <- p; rest $ f x y } <|> return x

chainl : Parser a -> Parser (a -> a -> a) -> a -> Parser a
chainl p op x = chainl1 p op <|> return x

然后我们可以从 chainl 文档中直接音译表达式解析器（我懒得实现一个合适的 integer 解析器所以我们只使用一元）：

parens : Parser a -> Parser a
parens p = token "(" *> p <* token ")"

symbol : String -> Parser ()
symbol = token

integer : Parser Nat
integer = P $ \s => case unpack s of
     ('Z'::s') => [(Z, pack s')]
     ('S'::s') => map (\(n, s'') => (S n, s'')) $ unP integer (pack s')
     _ => []

mutual
    expr : Parser Nat
    expr = term   `chainl1` addop

    term : Parser Nat
    term = factor `chainl1` mulop

    factor : Parser Nat
    factor  = parens expr <|> integer

    mulop : Parser (Nat -> Nat -> Nat)
    mulop = (symbol "*" *> pure (*)) <|>
            (symbol "/" *> pure div)

    addop : Parser (Nat -> Nat -> Nat)
    addop = (symbol "+" *> pure (+)) <|>
            (symbol "-" *> pure (-))

现在，如果你试试这个：

main : IO ()
main = do
  s <- getLine
  printLn $ runParser expr s

那么它将具有与您观察到的相同的发散行为。不过，我们可以做两个小改动：

引入一个懒惰的替代组合器：

orElse : Parser a -> Lazy (Parser a) -> Parser a
orElse p1 p2 = P $ \s => case unP p1 s of
   [] => unP p2 s
   results => results

通过翻转两个备选方案，确保 factor 的递归部分，即 parens expr 部分处于惰性位置：
```
factor = integer `orElse`  parens expr
```

这会按预期工作：

13:06:07 [cactus@galaxy brainfuck]$ idris Expr.idr -o Expr
13:06:27 [cactus@galaxy brainfuck]$ echo "SZ+(SSZ*SSSZ)" | ./Expr
Just 7

Answer 2

chainl 和 chainl1 组合器可以与 Lightyear 包一起使用。但是，它们是默认提供的。我已将组合器添加到我自己需要的模块中：

chainl1 : Parser a -> Parser (a -> a -> a) -> Parser a
chainl1 p op = p >>= rest
  where rest a1 = (do f <- op
                      a2 <- p
                      rest (f a1 a2)) <|> pure a1

chainl : Parser a -> Parser (a -> a -> a) -> a -> Parser a
chainl p op a = (p `chainl1` op) <|> pure a

似乎工作正常。希望对您有所帮助。

有没有办法在 idris lightyear 库中编写 chainl 函数？

Is there a way to code a chainl function in idris lightyear library?

regex

recursion

haskell

idris

lightyear