如何根据运行时值创建有界实例？

Question

我一直在玩O'Connor 基于*-semirings 的矩阵实现,为图算法提供了非常巧妙的解决方案:

import Data.Array
newtype Matrix i e = Matrix (Array (i,i) e)

matrix :: (Ix i, Bounded i) => ((i,i) -> e) -> Matrix i e
matrix f = Matrix . listArray (minBound, maxBound) . map f $ entireRange

但是,我想从外部世界的文件中读取任意大小的邻接矩阵,因此使用枚举类型矩阵被索引(如同Matrix Node :: Matrix Node2 (Maybe Integer)一篇论文)并不适合我.

我的第一个想法就像是

toMatrix :: [[a]] -> Matrix Int a
toMatrix list = Matrix (listArray ((0,0),(l-1,l-1)) $ concat list)
  where l = length list

但是当然这也不起作用:当各种类型类实例尝试访问索引时,尝试实际使用此矩阵会爆炸(minBound :: Int, minBound :: Int).

参数化矩阵类型的大小如

newtype Matrix i e = Matrix i (Array (i,i) e)

不完全奏效:虽然我可以改变matrix,以建立矩阵这样的功能,现在我有麻烦写作pure的Applicative (Matrix i e)实例或one为Semiring (Matrix i e)实例,如正确的one :: Matrix i e依赖于上下文中的矩阵的大小.

从概念上讲,我可以想出两种方法:

1. BoundedInt使用Bounded可在运行时设置的实例定义一个新类型, 当我们知道数组的大小时,或
2. 找到一种方法来声明Applicative (Matrix i e)在矩阵大小上参数化的实例.

但我不知道如何实现其中任何一个,围绕这个主题的搜索似乎变得非常复杂.这个问题看起来也很相关,但我不认为它解决了这个问题(尽管它会让我Bounded i在固定Int大小的矩阵上使用构造函数).

这里最简单的解决方案是什么？有没有必须学习如何使用单例库/某种依赖类型？

Answer 1

我写了一个关于Hasochism实例Matrix的长答案Applicative，使用有限集作为索引类型，但这可能对你想要的东西来说有点过分了，更不用说比Array博客文章中基于 - 的代码效率低了。

您的问题源于这样一个事实：博客文章代码中的各种操作都假设矩阵Bounded索引类型的实例是Coverage，从某种意义上说，边界内的每个值都将在矩阵中具有相应的元素。核心假设似乎是矩阵的大小是静态已知的。

解决此问题的最简单方法是调整类型Matrix，使其保持其尺寸。您仍然必须动态地进行所有边界检查，但我认为与 Hasochism 方法的重要性相比，这是一个相当好的权衡。

-- Bounded as an explicit (minBound, maxBound) tuple
type Bounds i = (i, i)
data Matrix i e = Matrix { getBounds :: Bounds i, getMatrix :: Array (Edge i) e }

entireRange :: Ix i => Bounds i -> [i]
entireRange b = range b

matrix :: Ix i => Bounds i -> (Edge i -> e) -> Matrix i e
matrix bounds f = Matrix bounds $ listArray bounds $ map f $ entireRange bounds

然而，当您需要在类型类实例中构造矩阵时，这就会陷入困境。您无法通过运行时值抽象实例：实例声明中 左侧唯一有效的=>是另一个类型类约束。在像这样的声明中

instance Bounded i => Applicative (Matrix i) where
    pure x = matrix (const x)
    (<*>) = -- ...

我们别无选择，只能在实例字典中静态传递边界，因为 的类型pure不允许我们传递显式配置数据。这个限制有它的优点和缺点，但现在它确实是一个令人沮丧的东西：解决方法是完全从你的代码中删除所有的优雅。

不过，好消息是：您可以使用疯狂reflection库来模拟这种显式字典传递样式，该库会执行邪恶而神奇的操作，将运行时值推入类型类字典中。这是可怕的东西，但它确实有效，而且很安全。

这一切都发生在reify和reflect组合器中。reify根据该值的可用性获取一个运行时值和带有约束的代码块，并将它们相互插入。对reflect块内部的调用返回传递到reify块外部的值。

needsAnInt :: Reifies s Int => Proxy s -> IO ()
needsAnInt p = print (reflect p + 1)

example1 :: IO ()
example1 = reify 3 (\p -> needsAnInt p)  -- prints 4
example2 :: IO ()
example2 = reify 5 (\p -> needsAnInt p)  -- prints 6

花点时间反思一下（哈哈）这有多么奇怪。通常每种类型的范围内只有一个类字典（尽管有重叠的实例）。Proxy只有一个值 ( data Proxy a = Proxy)，那么如何reflect区分两个代理，每次返回不同的值？

无论如何，这有什么意义呢？实例不能依赖于运行时值，但它们可以依赖于其他实例。reflection为我们提供了将运行时值转换为实例字典的工具，因此这使我们能够构建动态依赖于运行时值的实例！

在本例中，我们正在构建一个Bounded. 我们需要一个newtype, 来创建一个不与任何其他实例重叠的实例：

-- in this case it's fine to just lift the Ix instance from the underlying type
newtype B s i = B i deriving (Eq, Ord, Ix)

显然可以是if isB的实例- 它可以从的实例中获取和- 但我们希望从上下文中获取它们。换句话说，我们将填充到字典中的运行时值将是一对s。BoundediminBoundmaxBoundiReifiesReifiesi

instance Reifies s (i, i) => Bounded (B s i) where
    minBound = B $ fst $ reflect (Proxy :: Proxy s)
    maxBound = B $ snd $ reflect (Proxy :: Proxy s)

我正在使用ScopedTypeVariables关键来得出Proxy正确类型的值。

现在，您可以编写使用Bounded上下文的完美普通代码（即使该上下文是由于某些其他实例而出现的），并使用动态构建的Bounded字典来调用它reify。

entireRange :: (Ix i, Bounded i) => [i]
entireRange = range (minBound, maxBound)

example3 :: IO ()
example3 = reify (3, 6) myComputation
    where myComputation :: forall s. Bounded (B s Int) => Proxy s -> IO ()
          myComputation p = print $ map unB (entireRange :: [B s Int])

ghci> example3
[3,4,5,6]

嗯，是的。reflection使用起来可能很棘手。归根结底，不去上课可能会更简单。