2

我知道问“为什么我的代码不起作用”不是最好的问题。但是，我想了解更多关于在图论问题的算法上下文中在 Haskell 中使用 monad 的信息，并以以下代码为起点来了解 ST monad 将如何用于此类算法。

我在一些更简单的算法（快速排序）上取得了进展，并取得了 Dijkstra 算法的进展。我无法编译 Dijkstra 算法的以下实现（2012 年编写）：http ://www.rosettacode.org/wiki/Dijkstra%27s_algorithm#Haskell

我得到的错误如下：

• Non type-variable argument
        in the constraint: MArray (STArray s) e0 m
      (Use FlexibleContexts to permit this)
    • When checking the inferred type
        f :: forall (m :: * -> *).
             (MArray (STArray s) e0 m, MArray (STArray s) v m) =>
             Set (a0, v) -> (v, a0) -> m (Set (a0, v))
      In the expression:
        let
          edges = adj_list ! u
          f vertex_queue (v, weight) = do ...
        in foldM f vertex_queue' edges >>= aux
      In a case alternative:
          Just ((dist, u), vertex_queue')
            -> let
                 edges = adj_list ! u
                 f vertex_queue (v, weight) = ...
               in foldM f vertex_queue' edges >>= aux
   |
18 |                 f vertex_queue (v, weight) = do

（PS：这不是学校作业，这只是自我激励），我已经尝试了我在 Haskell 中所知道的一切（包括适当的缩进），但未能成功。

4

1 回答 1

0

正如错误所说，该算法使用FlexibleContexts扩展名 [haskell.org]。通常只有C t或形式的约束与类型类和,和类型变量一起使用。通过启用，约束也可以使用类型构造函数。C (q t1 t2 … tn)CqttiFlexibleContexts

编译器检测到类型约束(MArray (STArray s) e0 m, MArray (STArray s) v m)用作上下文，因此STArray用作类型构造函数，这是不允许的。编译器检测到这一点并引发一个错误，其中提到：

(Use FlexibleContexts to permit this)

因此，编译器就可以解决问题的方法给出建议，尽管我同意它有点“神秘”。

因此，您可以使用文件头部的语言编译指示启用此功能：

{-# LANGUAGE FlexibleContexts #-}

--- rest of the file ⋮
于 2021-10-04T09:30:09.020 回答