Ambiguous type variable when programming AI Solver in Haskell
I'm programming a generic AI algorithm in Haskell for an AI planning course at Coursera and ghci that complains about an ambiguous type variable. Here is the Haskell code and the error I am getting:
-- 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.
-}
source to share
Eric Coe fixed my problem using functional dependencies. It still uses the type classes as I needed it. Here's his solution, which compiles like a charm:
Here is our Facebook Haskell 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
source to share
I think you have an instance of itis-class-type. That is, there are too many typeclasses that actually do nothing, resulting in complex code that is difficult to reason about.
A symptom of class-itis-type that helps diagnose it is the need to keep introducing new language features to make it work. If you keep going this route, then later on you will need to write many "dummy types" that do not actually contain any data, and exist solely so that you can turn them into instances of your various types.
You can read more about type-class-itis in these blogs by Luke Palmer and Gabriel Gonzalez (LP is more moderate, GG is another ... extreme)
The best solution is to remember that functions are also data. You can wrap the functions you want in a record and pass the record instead. For example, in your case, I would 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
Note that I do not need to introduce any special language features and the code is much shorter - 19 lines instead of 38 lines, although I have included all signature types.
Good luck!
source to share