5

假设我有以下免费单子：

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 程序中使用它们等。

我一直遇到的问题是程序的类型取决于正在解析的程序。如果程序以 afoo它的类型Example ()结束，如果它以 abar它的类型结束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

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

4

2 回答 2

3

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

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

<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. 此外，没有办法提前知道我们给出的程序将是哪种类型：正如您所指出的，已解析程序的类型取决于输入字符串的值。“依赖于值的类型”称为依赖类型；Haskell 没有适当的依赖类型系统，但它已经足够接近我们可以尝试使这个示例工作。

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

data Ex a = forall i. Wrap (a i)

parseExpr :: Parser (Ex Example)
parseExpr = fmap Wrap parseFoo <|> fmap Wrap parseBar

此类型检查，但解析器现在返回一个Example包含未知类型的值。未知类型的值当然是无用的——但我们确实知道一些关于Example' 参数的信息：它必须是()or ，因为它们是andInt的返回类型。编程是将知识从你的大脑中提取出来并放到页面上，所以我们将用一些GADT证据来总结价值，当打开这些证据时，它会告诉你是还是.parseFooparseBarExampleaInt()

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's 类型参数的运行时“单例”。当您进行模式匹配时IntTy，您会了解到a ~ Int；当您进行模式匹配时，UnitTy您会了解到这一点a ~ ()。（信息可以以另一种方式流动，从类型到值，使用类。）:*:，仿函数产品，将两个类型构造函数配对，确保它们的参数相等；因此， 上的模式匹配会Ty告诉您其伴随的Example.

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

请注意，这种使用Sig相当于Either (Example Int) (Example ())-毕竟，sigma 类型是 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)

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

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

†<code>Ex 和:*:是我从Hasochism 论文中提取的可重复使用的机器

于 2016-01-06T21:23:25.757 回答
2

所以，我担心这与您在面向对象语言中看到的那种过早的抽象相同，会妨碍事情的发展。例如，我不能 100% 确定您使用的是 free monad 的结构 - 例如，您的助手似乎只是在使用id并且()以一种相当无聊的方式，实际上我不确定您Int -> x是否有任何其他东西要么Pure :: Int -> Free ExampleF Int要么const (something :: Free ExampleF Int)。

函子 F 的自由单子基本上可以描述为一棵树，其数据存储在叶中，其分支因子由函子 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)，不同之处只是MF (Sum 3) "Hello"你看到Free . Identity . Free . Identity . Free . Identity $ Pure "Hello"的不是跟踪这个整数的方法。另一方面，如果你有，data E x = L x | R x deriving (Functor)那么在你击中这片叶子之前，你会得到一种 Ls 和 Rs 的“路径”，Free E它将同构于MonoidalFree [Bool]。

我经历这个的原因是，当你Free与一个Integer -> x仿函数结合时，你会得到一个无限分支的树，当我查看你的代码以弄清楚你实际上是如何使用这棵树时，我所看到的只是你使用id它的功能。据我所知，这将递归限制为具有形式Free (Bar "string" Pure)，否则Free (Bar "string" (const subExpression)),在这种情况下，系统似乎完全简化为MonoidalFree [Either Int String]单子。

（此时我应该停下来问一句：就你所知，这是正确的吗？这是本意吗？）

反正。除了我对你的过早抽象的问题之外，你用你的 monad 引用的具体问题（你无法区分()并Int有一堆非常复杂的解决方案，但一个非常简单的解决方案。真正简单的解决方案是产生一个类型的值，Example (Either () Int)如果你有一个()你可以fmap Left进入它，如果你有一个Int你可以fmap Right进入它。

如果没有更好地了解您如何通过 TCP/IP 使用此东西，我们无法为您推荐比您似乎正在找到的通用免费 monad 更好的结构 - 特别是我们需要知道您是如何使用的'正计划Int -> x在实践中使用无限分支的选项。

于 2016-01-06T20:14:50.403 回答