4

我正在尝试编写一个带有常规函数的箭头转换器，并将它们转换为抽象值的计算。如果我们有一个“源”箭头，

f :: Int -> Int
f x = x + 1

那么目标是让f处理提升的 [原文如此？] 抽象值类型，在这个例子中

f' :: AV Int -> AV Int
f' (Const x) = Const (f x)
-- pass along errors, since AV computation isn't always defined
-- or computable in the case of errors
f' (Error s) = Error s
-- avRep = "abstract representation". Think of symbolic math manipulation or ASTs.
f' (Abstract avRep) = AVRepPlus avRep (AVRepConst 1)

然而，为了成功地实现这个箭头，需要提升一些类型，以便在任意深度拥有具有一些具体值和一些抽象值的异构数据结构。我最终做的是为常规的 haskell 构造函数添加特殊类型，例如，如果

g = uncurry (+) -- i.e. g (x, y) = x + y

然后我为元组构造函数 (,) 添加一个抽象表示，

AVTuple :: AV a -> AV b -> AV (a, b)

并且g的代码被提升到 [展开一点]，

g' (AVTuple (AVConst a) (AVConst b)) = (AVConst (g (a, b)))
g' (AVTuple (AVError e) _) = (AVError e)
-- symmetric case here, i.e. AVTuple _ (AVError e)
g' (AVTuple a@(AVTuple _ _) b) = -- recursive code here

AVEither 也需要这样做。这最终会成为很多案例。有没有一个很好的方法来解决这个问题？

我是 Haskell 新手，所以请给我发参考资料或半详细的解释；可能我读过的最接近的东西是 SYBR 论文（废弃你的样板革命）第 1-3 节。

非常非常感谢你！

4

2 回答 2

1

让我看看我是否明白你在这里的目的。您有一个类型，该类型AV a描述产生某种类型的计算a，其中该计算的结构可以以允许检查的方式保留。您想要一种将任意函数提升到 上AV的操作，保留结构，而不必为每个操作创建特殊情况的方法。

通常，为了将功能提升到某种结构中，人们会使用Functor和Applicative。但是，这样做的直接方法涉及转换结构并直接应用提升的功能，而不是将功能应用保留为结构的一部分。

你想要的更尴尬，原因如下：

假设我们有一些我们想要提升的函数，以及两个适当类型的抽象值来应用它：

x :: AV A
x = ...

y :: AV B
y = ...

f :: A -> B -> C
f = ...

假设存在一个功能liftAV2可以满足您的需求。我们希望类型为lift2 f，AV A -> AV B -> AV C就像liftAfor一样Applicative。

稍后，我们希望lift2 f通过恢复 、 和 的值来检查使用 、f产生x的计算y。假设现在我们只想提取第一个参数。假设存在一个extractArg1执行此操作的函数，例如extractArg1 (liftAV2 f x y)= x。是什么类型的extractArg1？在这里，在context 中，我们知道它应该有 type AV C -> AV A。但它一般有什么类型？像AV c -> AV a什么？这是错误的，因为结果不仅仅是任何类型a，它是用于构造AV c值的任何类型。假设我们正在操作的值是使用 的结果构造的liftAV2 f，我们知道存在问题的类型，但我们一般无法找到它。

这就是我们进入存在主义类型领域的地方。诚实地使用它们，而不是像通常那样将它们与类型类一起滥用。

你也许可以通过一些努力来完成你所追求的，但这已经进入了相当先进的领域。您将希望使用GADT作为初学者，尽管我认为您可能已经在这样做了。使用存在类型也往往非常笨拙，因为您只能在有限的上下文中知道它们是什么。

AV 在您的特定情况下，提供两个类型参数可能更容易：一个代表计算的最终类型，一个代表计算的结构，例如：

data f :$ x = ...

data AV structure result where
    ...
    AVApply :: AV f (a -> b) -> AV x a -> AV (f :$ x) b

然后，为了检查计算，您可以查看第一种类型以了解您拥有什么；为了构建计算，您可以查看第二个以确保类型匹配。评估函数将具有类似的类型AV t a -> a，丢弃结构。你也可以使用结构类型“解包”计算，丢弃结果类型，如果你需要拆开结构以便漂亮地打印它。

于 2011-05-25T18:30:53.087 回答
0

我喜欢思考它的方式，Functor当我想谈论一些“带有一点额外的数据”时，我会使用一个实例（取决于“一点额外”是什么，我实际上可能在谈论Applicativeor Monad）。

另一方面，我用一个Arrow实例来谈论“少一点的函数”：箭头可以让你定义可以像函数一样组合在一起的东西，但是你可以添加额外的结构或限制来禁止某些结构（例如没有ArrowChoice或的箭头ArrowLoop）。

您希望完成什么并不完全清楚，但听起来您实际上是在将数据包装在AV类型构造函数中。在这种情况下，您可能想要创建AV一个 的实例，并为环绕的和类似地Functor添加Functor实例。(AV a, AV b) => AV (a, b)AVEither

于 2011-05-25T16:42:51.350 回答