Ambiguous type variable when programming an AI Solver in Haskell

Question

I'm programming an AI General Problem Solver in Haskell for the AI Planning course at Coursera and ghci complains about an ambiguous type variable. Here is the Haskell code and the error I get:

-- Solver.hs
{-# LANGUAGE GADTs,FlexibleInstances,UndecidableInstances,ScopedTypeVariables,TypeFamilies,MultiParamTypeClasses #-}

module Solver
(Solver,State,Transition)
where

class (Show t,Eq t) => Transition t where
 transition :: State s => s -> t -> s

class (Show s,Eq s) => State s where
 getPossibleTransitions :: Transition t => s -> [t]
 isStateValid :: s -> Bool
 isGoalState :: s -> Bool

class Solver s t where
 getPossibleNextStates :: s -> [s]
 isStateVisited :: [s] -> s -> Bool
 getNextFringeStates :: [s] -> [[s]]
 --getNextGeneration :: [s] -> [s] -> [s]

flatten :: [[a]] -> [a]
flatten [] = []
flatten listOfLists = (head listOfLists) ++ (flatten (tail listOfLists))

instance (State s,Transition t) => Solver s t where

 getPossibleNextStates (state::s) =
  filter isStateValid (map transitionFunction possibleTransitions)
  where
   transitionFunction = (transition state)::(t -> s)
   possibleTransitions = (getPossibleTransitions state)::([t])

 isStateVisited visitedStates state =
  any (== state) visitedStates

 getNextFringeStates (states::[s]) =
  map (getPossibleNextStates :: (s -> [s])) (states::[s])

-- COMPILATION:
{-
Prelude> :l Solver.hs
[1 of 1] Compiling Solver           ( Solver.hs, interpreted )

Solver.hs:38:8:
    Ambiguous type variable `t0' in the constraint:
      (Transition t0) arising from a use of `getPossibleNextStates'
    Probable fix: add a type signature that fixes these type variable(s)
    In the first argument of `map', namely
      `(getPossibleNextStates :: s -> [s])'
    In the expression:
      map (getPossibleNextStates :: s -> [s]) (states :: [s])
    In an equation for `getNextFringeStates':
        getNextFringeStates (states :: [s])
          = map (getPossibleNextStates :: s -> [s]) (states :: [s])
Failed, modules loaded: none.
-}

Answer 1

I think you have an instance of type-class-itis. That is, too many type classes that don't really accomplish anything, leading to complicated code that's hard to reason about.

A symtpom of type-class-itis that helps to diagnose it is the need to keep introducing new language features to make stuff work. If you keep going down this route, then later on you'll find yourself needing to write lots of 'dummy types' that don't actually hold any data, and exist solely so that you can make them into instances of your various typeclasses.

You can read more about type-class-itis in these blog posts by Luke Palmer and Gabriel Gonzalez (the LP one is more moderate, the GG one more... extreme)

• Haskell Antipattern: Existential Typeclass
• Scrap Your Type Classes

A better solution is to remember that functions are data too. You can wrap up the functions you need into a record, and pass the record around instead. For example, in your case I'd probably structure it like this:

module Solver where

data State s t = State { state :: s
                       , getPossibleTransitions :: [t]
                       , isValid :: Bool
                       , isGoal :: Bool
                       , transition :: t -> State s t }

getPossibleNextStates :: State s t -> [State s t]
getPossibleNextStates s = filter isValid (map transitionFunction possibleTransitions)
    where
        transitionFunction  = transition s
        possibleTransitions = getPossibleTransitions s

isStateVisited :: Eq s => [s] -> State s t -> Bool
isStateVisited visitedStates s = any (== state s) visitedStates

getNextFringeStates :: [State s t] -> [[State s t]]
getNextFringeStates states = map getPossibleNextStates states

Notice how I don't need to introduce any special language features, and the code is a lot shorter as well - 19 lines as opposed to 38 lines, even though I included all the type signatures.

Good luck!

Answer 2

Eric Kow fixed my problem by using functional dependencies. He continues to use type-classes as I required. Here is his solution that compiles like a charm:

http://pastebin.com/tnqW2QGn

Here is our Haskell facebook group where we found the solution:

https://www.facebook.com/groups/programming.haskell/

-- Solver.hs
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE MultiParamTypeClasses  #-}
{-# LANGUAGE ScopedTypeVariables    #-}

module Solver
    (Solver,State,Transition)
  where

class (Show t,Eq t) => Transition t where
    transition :: State s => s -> t -> s

class (Show s,Eq s) => State s where
    getPossibleTransitions :: Transition t => s -> [t]
    isStateValid :: s -> Bool
    isGoalState  :: s -> Bool

class (State s, Transition t) => Solver s t | s -> t where

    getPossibleNextStates :: s -> [s]
    getPossibleNextStates state =
       filter isStateValid (map transitionFunction possibleTransitions)
      where
       transitionFunction  = transition state :: t -> s
       possibleTransitions = getPossibleTransitions state

    isStateVisited        :: [s] -> s -> Bool
    isStateVisited visitedStates state =
       any (== state) visitedStates

    getNextFringeStates :: [s] -> [[s]]
    getNextFringeStates = map getPossibleNextStates