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

Question

我一直在玩奥康纳的matrix基于 *-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取决于上下文中矩阵的大小。

从概念上讲，我可以想到两种方法:

定义一个新的 BoundedInt输入 Bounded当我们知道数组的大小时可以在运行时设置的实例，或

找到一种声明 Applicative (Matrix i e) 实例的方法参数化矩阵的大小。

但我不知道如何实现其中任何一个，围绕该主题的搜索似乎会出现非常复杂的事情。 This问题看起来也很相关，但我认为它不能解决问题(尽管它可以让我在固定 Bounded i 大小的矩阵上使用 Int 构造函数)。

这里最简单的解决方案是什么？是否有一个无需学习如何使用单例库/某种依赖类型？

Answer 1

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

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

解决此问题的最简单方法是调整 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 的类型不允许我们传递显式配置数据。 This restriction has its ups and downs ，但现在它确实令人沮丧:解决方法是完全从你的代码中删除所有的优雅。

不过好消息是:您可以使用疯狂的 reflection 来模拟这种显式的字典传递风格。库，它做了邪恶的、神奇的事情来将运行时值推送到类型类字典中。这是可怕的东西，但它确实有效，而且很安全。

这一切都发生在 reify 和 reflect 组合器。 reify根据该值的可用性，获取一个运行时值和一个带有约束的代码块，并将它们相互插入。调用reflect在 block 内返回传递给 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)

显然 B可以是 Bounded 的实例如果 i是-它可以得到minBound和 maxBound来自 i的实例 - 但我们想从 Reifies 获取它们语境。换句话说，我们将填充到 Reifies 中的运行时值字典将是一对 i s。

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使用起来可能很棘手。归根结底，不去上课可能更简单。