解析为自由 Monad
Parsing to Free Monads
假设我有以下免费的 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 结尾
如果它以 bar 结尾，则输入 Example () 它是 Example Int.
类型
我不想为每个可能的排列编写解析器（这里很简单，因为只有两种可能性，但想象一下我们添加
Baz Int (String -> a), Doo (Int -> a), Moz Int a, Foz String a, ....这很乏味且容易出错。
也许我解决了错误的问题？
样板文件
要运行上面的例子，需要在文件开头加上：
{-# LANGUAGE DeriveFunctor #-}
import Control.Monad.Free
import Text.ParserCombinators.Parsec
所以，我担心这与您在 object-oriented 语言中看到的同一种过早抽象会妨碍事情的进行。例如，我不能 100% 确定您正在使用自由 monad 的结构——例如，您的助手似乎只是以一种相当无聊的方式使用 id 和 ()，事实上我我不确定你的 Int -> x 是否是 Pure :: Int -> Free ExampleF Int 或 const (something :: Free ExampleF Int) 以外的任何东西。
函子 F 的自由 monad 基本上可以描述为一棵树，其数据存储在叶子中，其分支因子由函子 F 的每个构造函数中的递归控制。例如 Free Identity没有分支，因此只有一片叶子，因此具有与 monad 相同的结构：
data MonoidalFree m x = MF m x deriving (Functor)
instance Monoid m => Monad (MonoidalFree m) where
return x = MF mempty x
MF m x >>= my_x = case my_x x of MF n y -> MF (mappend m n) y
实际上 Free Identity 与 MonoidalFree (Sum Integer) 同构，不同之处在于您看到 Free . Identity . Free . Identity . Free . Identity $ Pure "Hello" 而不是 MF (Sum 3) "Hello" 作为跟踪此整数的方法。另一方面，如果你有 data E x = L x | R x deriving (Functor) 那么在你击中这片叶子之前你会得到一种 "path" 的 Ls 和 Rs，Free E 将同构于 MonoidalFree [Bool] .
我这样做的原因是，当您将 Free 与 Integer -> x 仿函数组合时，您会得到一个 无限分支树 ，并且当我查看您的代码以了解您如何 实际使用 这棵树时，我所看到的只是您对它使用了 id 函数。据我所知，这将递归限制为具有 Free (Bar "string" Pure) 或 Free (Bar "string" (const subExpression)), 的形式，在这种情况下系统似乎完全减少为 MonoidalFree [Either Int String] monad.
（此时我应该停下来问：据您所知，这是否正确？这是故意的吗？）
无论如何。除了我对你过早抽象的问题之外，你用你的 monad 引用的具体问题（你无法区分 () 和 Int 有一堆非常复杂的解决方案，但是一个真的很简单。真正简单的解决方案是产生一个 Example (Either () Int) 类型的值，如果你有一个 () 你可以 fmap Left 它，如果你有一个 Int 你可以fmap Right到上面吗
如果不更好地理解如何你在TCP/IP上使用这个东西，我们不能为你推荐比通用的免费单子更好的结构您似乎发现了——特别是我们需要知道您打算如何在实践中使用 infinite-branching 或 Int -> x 选项。
如果不重新实现 Haskell 的某些部分，并非每个 Example 值都可以在页面上表示。例如，return putStrLn 的类型为 Example (String -> IO ())，但我认为尝试从文件中解析出那种 Example 值是没有意义的。
因此，让我们将自己限制在解析您给出的示例中，这些示例仅包含对 foo 和 bar 的调用，并按 >> 排序（即，没有变量绑定和没有任意计算）*。我们语法的 Backus-Naur 形式大致如下所示：
<program> ::= "" | <expr> "\n" <program>
<expr> ::= "foo " <integer> | "bar " <string>
解析我们的两种表达式很简单...
type Parser = Parsec String ()
int :: Parser Int
int = fmap read (many1 digit)
parseFoo :: Parser (Example ())
parseFoo = string "foo " *> fmap foo int
parseBar :: Parser (Example Int)
parseBar = string "bar " *> fmap bar (many1 alphaNum)
...但是我们怎样才能给这两个解析器的组合一个类型呢？
parseExpr :: Parser (Example ???)
parseExpr = parseFoo <|> parseBar
parseFoo和parseBar的类型不同，不能和<|> :: Alternative f => f a -> f a -> f a组合。此外，无法提前知道我们给出的程序是哪种类型：正如您所指出的，已解析程序的 type 取决于 输入字符串的值。 “类型取决于值”被称为依赖类型； Haskell 没有适当的依赖类型系统，但它足够接近我们让这个例子工作的尝试。
让我们首先强制 <|> 两边的表达式具有相同的类型。这涉及使用 existential quantification 擦除 Example 的类型参数。†
data Ex a = forall i. Wrap (a i)
parseExpr :: Parser (Ex Example)
parseExpr = fmap Wrap parseFoo <|> fmap Wrap parseBar
此类型检查，但解析器现在 return 是一个 Example 包含未知类型的值。未知类型的值当然是无用的 - 但我们确实知道 一些关于 Example 的参数：它必须是 () 或 Int因为它们是 parseFoo 和 parseBar 的 return 类型。编程就是将知识从你的大脑中提取出来并写到页面上，所以我们将用一些 GADT 证据来包装 Example 值，当展开时，它会告诉你是否 a 是 Int 或 ()。
data Ty a where
IntTy :: Ty Int
UnitTy :: Ty ()
data (a :*: b) i = a i :&: b i
type Sig a b = Ex (a :*: b)
pattern Sig x y = Wrap (x :&: y)
parseExpr :: Parser (Sig Ty Example)
parseExpr = fmap (\x -> Sig UnitTy x) parseFoo <|>
fmap (\x -> Sig IntTy x) parseBar
Ty 是（类似于）Example 类型参数的运行时“单例”代表。当您在 IntTy 上进行模式匹配时，您会了解到 a ~ Int；当您在 UnitTy 上进行模式匹配时，您会了解到 a ~ ()。 （可以使用 类 使信息以另一种方式流动，从类型到值。） :*:、functor product 将两个类型构造函数配对，确保它们的参数相等；因此，Ty 上的模式匹配告诉您它伴随的 Example.
Sig 因此称为 依赖对 或 sigma 类型 - type 对的第二个组件取决于第一个组件的 value。这是一种常见的技术：当您通过存在量化删除类型参数时，通常需要通过捆绑该参数的运行时代表来使其可恢复。
请注意，Sig 的这种用法等同于 Either (Example Int) (Example ()) - a sigma type is a sum，毕竟 - 但是当你对一个大的（或可能是无限的）求和时，这个版本的扩展性更好) 设置。
现在很容易将我们的表达式解析器构建到程序解析器中。我们只需要重复应用表达式解析器，然后操作列表中的依赖对即可。
parseProgram :: Parser (Sig Ty Example)
parseProgram = fmap (foldr1 combine) $ parseExpr `sepBy1` (char '\n')
where combine (Sig _ val) (Sig ty acc) = Sig ty (val >> acc)
我向您展示的代码并非典范。它没有将解析和类型检查的关注点分开。在生产代码中，我将通过首先将数据解析为非类型化语法树（一种不强制类型不变的单独数据类型）来模块化此设计，然后通过 type-checking 将其转换为类型化版本。依赖对技术仍然是为 type-checker 的输出提供类型所必需的，但它不会在解析器中纠缠在一起。
*如果不需要绑定，您是否考虑过使用 free applicative 来表示您的数据？
†Ex 和 :*: 是我从 Hasochism paper
中取出的可重复使用的机器部件
假设我有以下免费的 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 结尾
如果它以 bar 结尾，则输入 Example () 它是 Example Int.
我不想为每个可能的排列编写解析器（这里很简单，因为只有两种可能性，但想象一下我们添加
Baz Int (String -> a), Doo (Int -> a), Moz Int a, Foz String a, ....这很乏味且容易出错。
也许我解决了错误的问题？
样板文件
要运行上面的例子，需要在文件开头加上：
{-# LANGUAGE DeriveFunctor #-}
import Control.Monad.Free
import Text.ParserCombinators.Parsec
所以，我担心这与您在 object-oriented 语言中看到的同一种过早抽象会妨碍事情的进行。例如，我不能 100% 确定您正在使用自由 monad 的结构——例如，您的助手似乎只是以一种相当无聊的方式使用 id 和 ()，事实上我我不确定你的 Int -> x 是否是 Pure :: Int -> Free ExampleF Int 或 const (something :: Free ExampleF Int) 以外的任何东西。
函子 F 的自由 monad 基本上可以描述为一棵树，其数据存储在叶子中，其分支因子由函子 F 的每个构造函数中的递归控制。例如 Free Identity没有分支，因此只有一片叶子，因此具有与 monad 相同的结构：
data MonoidalFree m x = MF m x deriving (Functor)
instance Monoid m => Monad (MonoidalFree m) where
return x = MF mempty x
MF m x >>= my_x = case my_x x of MF n y -> MF (mappend m n) y
实际上 Free Identity 与 MonoidalFree (Sum Integer) 同构，不同之处在于您看到 Free . Identity . Free . Identity . Free . Identity $ Pure "Hello" 而不是 MF (Sum 3) "Hello" 作为跟踪此整数的方法。另一方面，如果你有 data E x = L x | R x deriving (Functor) 那么在你击中这片叶子之前你会得到一种 "path" 的 Ls 和 Rs，Free E 将同构于 MonoidalFree [Bool] .
我这样做的原因是，当您将 Free 与 Integer -> x 仿函数组合时，您会得到一个 无限分支树 ，并且当我查看您的代码以了解您如何 实际使用 这棵树时，我所看到的只是您对它使用了 id 函数。据我所知，这将递归限制为具有 Free (Bar "string" Pure) 或 Free (Bar "string" (const subExpression)), 的形式，在这种情况下系统似乎完全减少为 MonoidalFree [Either Int String] monad.
（此时我应该停下来问：据您所知，这是否正确？这是故意的吗？）
无论如何。除了我对你过早抽象的问题之外，你用你的 monad 引用的具体问题（你无法区分 () 和 Int 有一堆非常复杂的解决方案，但是一个真的很简单。真正简单的解决方案是产生一个 Example (Either () Int) 类型的值，如果你有一个 () 你可以 fmap Left 它，如果你有一个 Int 你可以fmap Right到上面吗
如果不更好地理解如何你在TCP/IP上使用这个东西，我们不能为你推荐比通用的免费单子更好的结构您似乎发现了——特别是我们需要知道您打算如何在实践中使用 infinite-branching 或 Int -> x 选项。
如果不重新实现 Haskell 的某些部分，并非每个 Example 值都可以在页面上表示。例如，return putStrLn 的类型为 Example (String -> IO ())，但我认为尝试从文件中解析出那种 Example 值是没有意义的。
因此，让我们将自己限制在解析您给出的示例中，这些示例仅包含对 foo 和 bar 的调用，并按 >> 排序（即，没有变量绑定和没有任意计算）*。我们语法的 Backus-Naur 形式大致如下所示：
<program> ::= "" | <expr> "\n" <program>
<expr> ::= "foo " <integer> | "bar " <string>
解析我们的两种表达式很简单...
type Parser = Parsec String ()
int :: Parser Int
int = fmap read (many1 digit)
parseFoo :: Parser (Example ())
parseFoo = string "foo " *> fmap foo int
parseBar :: Parser (Example Int)
parseBar = string "bar " *> fmap bar (many1 alphaNum)
...但是我们怎样才能给这两个解析器的组合一个类型呢？
parseExpr :: Parser (Example ???)
parseExpr = parseFoo <|> parseBar
parseFoo和parseBar的类型不同，不能和<|> :: Alternative f => f a -> f a -> f a组合。此外，无法提前知道我们给出的程序是哪种类型：正如您所指出的，已解析程序的 type 取决于 输入字符串的值。 “类型取决于值”被称为依赖类型； Haskell 没有适当的依赖类型系统，但它足够接近我们让这个例子工作的尝试。
让我们首先强制 <|> 两边的表达式具有相同的类型。这涉及使用 existential quantification 擦除 Example 的类型参数。†
data Ex a = forall i. Wrap (a i)
parseExpr :: Parser (Ex Example)
parseExpr = fmap Wrap parseFoo <|> fmap Wrap parseBar
此类型检查，但解析器现在 return 是一个 Example 包含未知类型的值。未知类型的值当然是无用的 - 但我们确实知道 一些关于 Example 的参数：它必须是 () 或 Int因为它们是 parseFoo 和 parseBar 的 return 类型。编程就是将知识从你的大脑中提取出来并写到页面上，所以我们将用一些 GADT 证据来包装 Example 值，当展开时，它会告诉你是否 a 是 Int 或 ()。
data Ty a where
IntTy :: Ty Int
UnitTy :: Ty ()
data (a :*: b) i = a i :&: b i
type Sig a b = Ex (a :*: b)
pattern Sig x y = Wrap (x :&: y)
parseExpr :: Parser (Sig Ty Example)
parseExpr = fmap (\x -> Sig UnitTy x) parseFoo <|>
fmap (\x -> Sig IntTy x) parseBar
Ty 是（类似于）Example 类型参数的运行时“单例”代表。当您在 IntTy 上进行模式匹配时，您会了解到 a ~ Int；当您在 UnitTy 上进行模式匹配时，您会了解到 a ~ ()。 （可以使用 类 使信息以另一种方式流动，从类型到值。） :*:、functor product 将两个类型构造函数配对，确保它们的参数相等；因此，Ty 上的模式匹配告诉您它伴随的 Example.
Sig 因此称为 依赖对 或 sigma 类型 - type 对的第二个组件取决于第一个组件的 value。这是一种常见的技术：当您通过存在量化删除类型参数时，通常需要通过捆绑该参数的运行时代表来使其可恢复。
请注意，Sig 的这种用法等同于 Either (Example Int) (Example ()) - a sigma type is a sum，毕竟 - 但是当你对一个大的（或可能是无限的）求和时，这个版本的扩展性更好) 设置。
现在很容易将我们的表达式解析器构建到程序解析器中。我们只需要重复应用表达式解析器，然后操作列表中的依赖对即可。
parseProgram :: Parser (Sig Ty Example)
parseProgram = fmap (foldr1 combine) $ parseExpr `sepBy1` (char '\n')
where combine (Sig _ val) (Sig ty acc) = Sig ty (val >> acc)
我向您展示的代码并非典范。它没有将解析和类型检查的关注点分开。在生产代码中，我将通过首先将数据解析为非类型化语法树（一种不强制类型不变的单独数据类型）来模块化此设计，然后通过 type-checking 将其转换为类型化版本。依赖对技术仍然是为 type-checker 的输出提供类型所必需的，但它不会在解析器中纠缠在一起。
*如果不需要绑定，您是否考虑过使用 free applicative 来表示您的数据？
†Ex 和 :*: 是我从 Hasochism paper