在Haskell中编写AI Solver时出现模糊类型变量

Question

我正在Haskell编写一个AI General Problem Solver,用于Coursera的AI Planning课程,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

我认为你有一个type-class-itis的实例.也就是说,太多类型的类没有真正完成任何事情,导致复杂的代码很难推理.

有助于诊断它的类型-isis的symtpom需要不断引入新的语言功能以使其工作.如果你继续沿着这条路走下去,那么稍后你就会发现自己需要编写许多实际上并不包含任何数据的"虚拟类型",并且只是存在以便你可以将它们变成各种类型类的实例.

你可以在Luke Palmer和Gabriel Gonzalez的博客文章中阅读更多关于type-class-itis的内容(LP更温和,GG更多......极端)

• Haskell反模式:存在类型类
• 废弃你的类型

更好的解决方案是记住功能也是数据.您可以将所需的功能包装到记录中,然后传递记录.例如,在你的情况下,我可能会像这样构造它:

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行,即使我包含了所有类型的签名.

祝好运!