无法在 Dijkstra 的 Haskell 实现中发现代码中的问题

Question

我知道问“为什么我的代码不起作用”不是最好的问题。但是，我想了解更多关于在图论问题的算法上下文中使用 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 中所知道的一切（包括适当的缩进）但无法成功.

Answer 1

如错误所述，该算法使用 FlexibleContexts extension [haskell.org]。通常只有 C t 或 C (q t1 t2 ... tn) 可以使用，C 类型类和 q、t 和 ti 类型变量。通过启用 FlexibleContexts，约束还可以使用类型构造函数。

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

(Use FlexibleContexts to permit this)

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

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

{-# LANGUAGE <strong>FlexibleContexts</strong> #-}

--- rest of the file ⋮

无法在 Dijkstra 的 Haskell 实现中发现代码中的问题

Not being able spot the problem in the code in Dijkstra’s Haskell implementation

monads

haskell

compiler-errors

ghc

st-monad