解析为免费Monad

Question

说我有以下免费monad：

data ExampleF a
  = Foo Int a
  | Bar String (Int -> a)
  deriving Functor

type Example = Free ExampleF  -- this is the free monad want to discuss

我知道如何使用此monad。我可以写一些不错的助手：

foo :: Int -> Example ()
foo i = liftF $ Foo i ()

bar :: String -> Example Int
bar s = liftF $ Bar s id

所以我可以用haskell编写程序，例如：

fooThenBar :: Example Int
fooThenBar =
  do
    foo 10
    bar "nice"

我知道如何打印，解释等。但是如何解析呢？

是否有可能编写一个解析器来解析任意程序，例如：

foo 12
bar nice
foo 11
foo 42

所以我可以存储它们，序列化它们，在cli程序中使用它们，等等。

我一直遇到的问题是程序的类型取决于要解析的程序。如果一个程序结束foo它的类型Example ()，如果它有结束bar它的类型Example Int。

我不喜欢写解析器每一种可能的置换（这里很简单，因为只有两种可能，但是想象一下我们添加 Baz Int (String -> a)，Doo (Int -> a)，Moz Int a，Foz String a，... GET操作的繁琐，而且容易出错）。

也许我正在解决错误的问题？

样板

要运行上述示例，您需要将其添加到文件的开头：

{-# LANGUAGE DeriveFunctor #-}

import Control.Monad.Free
import Text.ParserCombinators.Parsec

注意：我提出了包含此代码的要点。

Answer 1

如果不重新实现 Haskell 的某些部分，并非每个Example值都可以在页面上表示。例如，return putStrLn具有 的类型，但我认为尝试从文件中Example (String -> IO ())解析此类值是没有意义的。Example

\n

因此，让我们限制自己解析您给出的示例，这些示例仅包含对 * 的调用foo和bar排序>>（即，没有变量绑定，也没有任意计算）*。我们语法的巴科斯-诺尔形式大致如下所示：

\n

<program> ::= "" | <expr> "\\n" <program>\n<expr> ::= "foo " <integer> | "bar " <string>\n

\n

解析我们的两种类型的表达式非常简单......

\n

type Parser = Parsec String ()\n\nint :: Parser Int\nint = fmap read (many1 digit)\n\nparseFoo :: Parser (Example ())\nparseFoo = string "foo " *> fmap foo int\n\nparseBar :: Parser (Example Int)\nparseBar = string "bar " *> fmap bar (many1 alphaNum)\n

\n

...但是我们如何为这两个解析器的组合指定类型？

\n

parseExpr :: Parser (Example ???)\nparseExpr = parseFoo <|> parseBar\n

\n

parseFoo并且parseBar有不同的类型，所以我们不能用 来组合它们<|> :: Alternative f => f a -> f a -> f a。此外，无法提前知道我们给出的程序是什么类型：正如您所指出的，解析的程序的类型取决于输入字符串的值。“类型依赖于值”称为依赖类型；Haskell 没有提供适当的依赖类型系统，但它足够接近，足以让我们尝试使这个示例发挥作用。

\n\n

让我们首先强制两侧的表达式<|>具有相同的类型。这涉及使用存在量化擦除Example\ 的类型参数。\xe2\x80\xa0

\n

data Ex a = forall i. Wrap (a i)\n\nparseExpr :: Parser (Ex Example)\nparseExpr = fmap Wrap parseFoo <|> fmap Wrap parseBar\n

\n

此类型检查，但解析器现在返回Example包含未知类型的值。未知类型的值当然是无用的 - 但我们确实了解\的参数：它必须是or因为它们是and的返回类型。编程就是将知识从你的大脑中提取出来并呈现在页面上，因此我们将用一些GADT证据来包装该值，当打开包装时，它会告诉你是否是或。Example()IntparseFooparseBarExampleaInt()

\n

data Ty a where\n    IntTy :: Ty Int\n    UnitTy :: Ty ()\n\ndata (a :*: b) i = a i :&: b i\n\ntype Sig a b = Ex (a :*: b)\npattern Sig x y = Wrap (x :&: y)\n\nparseExpr :: Parser (Sig Ty Example)\nparseExpr = fmap (\\x -> Sig UnitTy x) parseFoo <|>\n            fmap (\\x -> Sig IntTy x) parseBar\n

\n

Ty是（类似于）运行时“单例”代表Example\的类型参数。当您进行模式匹配时IntTy，您会了解到a ~ Int；当你进行模式匹配时，UnitTy你就会了解到这一点a ~ ()。（可以使用类使信息以另一种方式流动，从类型到值。）:*:，函子积，将两个类型构造函数配对，确保它们的参数相等；因此， 上的模式匹配会Ty告诉您其附带的Example.

\n

Sig因此称为依赖对或sigma类型 - 该对的第二个组件的类型取决于第一个组件的值。这是一种常见的技术：当您通过存在量化删除类型参数时，通常可以通过捆绑该参数的运行时代表来使其可恢复。

\n

请注意，这种用法Sig相当于Either (Example Int) (Example ())-毕竟sigma 类型是 sum - 但当您对一个大（或可能无限）集求和时，此版本可以更好地扩展。

\n

现在很容易将我们的表达式解析器构建成程序解析器。我们只需重复应用表达式解析器，然后操作列表中的依赖对。

\n

parseProgram :: Parser (Sig Ty Example)\nparseProgram = fmap (foldr1 combine) $ parseExpr `sepBy1` (char \'\\n\')\n    where combine (Sig _ val) (Sig ty acc) = Sig ty (val >> acc)\n

\n

我向您展示的代码并不具有示范性。它没有分离解析和类型检查的关注点。在生产代码中，我将通过首先将数据解析为非类型化语法树（一种不强制类型不变的单独数据类型）来模块化此设计，然后通过类型检查将其转换为类型化版本。依赖对技术仍然需要为类型检查器的输出提供类型，但它不会在解析器中纠缠在一起。

\n

_{*如果不需要绑定，您是否考虑过使用免费的应用程序来表示您的数据？}

\n

_{\xe2\x80\xa0Ex是我从Hasochism 论文:*:中提取的可重复使用的机器}

\n