Неоднозначная переменная типа при программировании AI Solver в Haskell

Question

Я программирую общий алгоритм ИИ в Haskell для курса планирования ИИ в Coursera и ghci, который жалуется на неоднозначную переменную типа. Вот код Haskell и ошибка, которую я получаю:

-- 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

Эрик Коу исправил мою проблему, используя функциональные зависимости. Он по-прежнему использует классы типа, как мне было нужно. Вот его решение, которое собирает как шарм:

http://pastebin.com/tnqW2QGn

Вот наш Haskell facebook группа, где мы нашли решение:

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 

Answer 2

Я думаю, у вас есть экземпляр типа-класса. То есть слишком много классов типов, которые на самом деле ничего не выполняют, что приводит к сложному коду, о котором трудно рассуждать.

Симптом типа-класса, который помогает диагностировать его, заключается в необходимости продолжать внедрять новые языковые функции, чтобы заставить работу работать. Если вы продолжаете идти по этому маршруту, то позже вам будет нужно написать много «фиктивных типов», которые фактически не содержат никаких данных, и существуют исключительно для того, чтобы вы могли превратить их в экземпляры ваших различных типов.

Вы можете прочитать больше о машинке класса-ИТИС в этих сообщениях в блоге Люк Палмер и Габриэль Гонсалес (ЛП один является более умеренным, ГГ еще один ... экстремальный)

• Haskell Antipattern: Existential Typeclass
• Scrap Your Type Classes

лучшее решение помнить, что функции данных слишком. Вы можете завернуть нужные вам функции в запись и вместо этого передать запись. Например, в вашем случае я бы, вероятно, структурировать его так:

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 

Обратите внимание, как я не нужно вводить какие-либо специальные функции языка, и код намного короче, а также - 19 строк, в отличие до 38 строк, хотя я включил все типы подписей.

Удачи вам!