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

Question

I understand that asking “why my code does not work” is not the best question. However, I am asking as I wish to learn more about using monads in Haskell in an algorithmic context for graph theory problems, and took the following code as a starting point to understand how the ST monad would be used in such an algorithm.

I made progress on some simpler algorithms (quick sort) and progressed to Dijkstra’s algorithm. I was unable to compile the following implementation (written in 2012) of Dijkstra’s algorithm: http://www.rosettacode.org/wiki/Dijkstra%27s_algorithm#Haskell

The error I get is the following :

• 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 : this is not for a school assignment, this is just self-motivated), I have tried everything I knew in Haskell (including proper indentations) but couldn’t succeed.

Answer 1

As the error says, the algorithm makes use of the FlexibleContexts extension [haskell.org]. Normally only constraints of the form C t, or C (q t1 t2 … tn) can be used, with C a typeclass and q, t and ti type variables. By enabling the FlexibleContexts, the constraints can also make use of type constructors.

The compiler detects that the type constraints use (MArray (STArray s) e0 m, MArray (STArray s) v m) as context, so with STArray as a type constructor, which is not allowed. The compiler detects this and raises an error that mentions:

(Use FlexibleContexts to permit this)

The compiler thus gives advise on what might fix the problem, although I agree it is a bit "cryptic".

You thus can enable this with a language pragma in the head of the file:

{-# LANGUAGE FlexibleContexts #-}

--- rest of the file ⋮