OO 接口转换为 Haskell

Question

我的具体问题实际上不是关于 OO 接口到 Haskell 的一般转换。这是我能想到的最好的标题。然而，我确信我的问题源于对 Haskell 建模代码的理解仍然很差，以及仍然处于 OO 范式领域的心态（你看，仍然是一个 Haskell 初学者）。

我正在编写一个 Mastermind（变体）模拟来测试几种 Mastermind 策略的适用性。事实上，我已经在 Java 和 Lua 因此这个 Haskell版本只是我学习Haskell编程的一个练习。如果您对我最终想要实现的目标感兴趣，您可以查看 Lua/Java 版本的自述文件。

但现在对于我的具体问题（简而言之，用面向对象的术语）：我想为策略提供一个接口，以便我可以互换地将遵循该接口的策略放入模拟递归（循环）中，并在完成后接收一些数据关于该策略的绩效。此外，我希望允许策略保持任意状态，并且我不想关心每个策略保持什么样的状态。但正是这个决定——实际上是至关重要的——使一切变得复杂。具体导致下面描述的问题的另一个要求是可以提供策略名称作为命令行参数，然后使用该特定策略运行模拟。

起初，我认为类型类适合这些要求，但在没有想出如何以这种方式对代码进行建模的真正想法之后，我放弃了这个想法。然后我决定使用 ADT，从那时起就使用它，并且在代码方面取得了相对较大的进展 - 直到现在。

---

所以，表面的问题是如何解决我下面提供的问题。更深层次的问题是如何更好地模拟我对 Haskell 中具有任意状态的接口的需求。

这是我的代码的精简和改编摘录：

-- reduced & simplified example
import Control.Monad.State

type Code = [Int]

data Answer = Answer { 
    blacks :: Int, 
    whites :: Int 
    } deriving (Eq, Show)

-- As you can see I decided for a type variable a that
-- represents the arbitrary state a strategy might carry
-- around. I wonder if this is the right way to do it.
-- | This is the interface for a strategy. A strategy must provide a method 
-- that, given a mastermind answer, returns the next guess, an initial state 
-- and the very first guess.
data Strategy a = Strategy {
    firstGuess :: Int -> Code,
    initialize :: Int -> a, -- a "constructor" in disguise
    guess      :: Answer -> State a Code
    }

dummy = Strategy {
    firstGuess   = firstGuess',
    initialize   = initialize', 
    guess        = guess'
    }

-- | The very first guess is always T0,T1,...,Tx, where x is the code length.
firstGuess' :: Int -> Code
firstGuess' length = [0..length-1]

-- | Memorize the code length
initialize' :: Int -> Int
initialize' = id

-- | Always return the same guess
guess' :: Answer -> State Int Code
guess' = const $ liftM firstGuess' get

-- HERE IS THE PROBLEM
-- I need this function since I'll get the name of a strategy
-- as a string from the command line and need to dispatch the
-- correct strategy to the simulation. Note, that there would
-- be of course more pattern matches for different strategies
-- with different accompanying states a.
nameToStrategy :: String -> Strategy a
nameToStrategy "dummy" = dummy

执行文件会产生以下错误消息：

Prelude> :l Problem.hs
[1 of 1] Compiling Main             ( Problem.hs, interpreted )

Problem.hs:37:25:
    Couldn't match expected type `a' against inferred type `Int'
      `a' is a rigid type variable bound by
          the type signature for `nameToStrategy' at Problem.hs:36:37
      Expected type: Strategy a
      Inferred type: Strategy Int
    In the expression: dummy
    In the definition of `nameToStrategy':
        nameToStrategy "dummy" = dummy
Failed, modules loaded: none.

我可以直观地理解问题。问题似乎是 nameToStrategy 不能只返回具有某种状态 a 的策略。类型变量必须是 具体，因为如果我将 nameToStrategy 的类型更改为 String -> Strategy Int 一切都很好。但这并不能解决我的问题。

我想我需要放松一下类型。但是，我真的不知道该怎么做。我听说过 Data.Dynamic 和存在类型，这些可能对我有帮助。不过，我觉得如果对我的代码有更好的建模，我就不需要这些了。

---

编辑：毕竟我设法将 sclv 的建议合并到代码中，现在好多了。策略的代码更加清晰，因为我不再需要第一次猜测的特殊情况，并且我可以使用防护来更好地区分正确和错误猜测的情况。主要的模拟处理并不像 sclv 的版本那么优雅，因为我将 stepState （以及使用 stepState 的函数）放入 IO Monad 中来测量计算时间，因此有一些“monadic”语法噪音”。轻松模拟几个模拟步骤的能力（这在以前实际上是不可能的）帮助我找到了一个相互递归的无限循环（这个错误很难理解）。总而言之，现在代码感觉更加离散。不用说，我不再需要 unsafeCoerce hack 来将名称分配给策略（或更好的“打包策略”）。我希望有一天，函数式思维方式对我来说也能自然而然地发生。

Answer 1

好吧，让我们从头开始。纯策略是给定知识状态并产生猜测的函数。 状态->猜猜。对于任何给定的状态，都有一些方法可以为其添加新知识 -- Answer ->状态->状态。我们现在只需要一个初始状态，而不是初始猜测。

data Strategy state = Strategy {
                 initialState :: state,
                 extractGuess :: state -> Guess,
                 updateState  :: Answer -> state -> state
         }

现在让我们看看当我们组合这些函数时会发生什么。

type Oracle = Guess -> Maybe Answer -- we'll encode success as Nothing

stepState :: Oracle -> Strategy state -> state -> Maybe state
stepState oracle str state = fmap (\ans -> updateState str ans state) $ 
                                      oracle (extractGuess str state)

stepMany :: Strategy state -> Oracle -> [state]
stepMany str oracle = go (initialState str)
      where go state = case stepState oracle str state of
               Nothing -> []
               Just newState -> newState : go newState

所以 stepMany 是我们想要的 90%，但它在那个讨厌的状态参数中仍然是多态的。这很容易解决——毕竟我们想要步骤的数量，而不是步骤本身的中间状态。

type packedStrategy = Oracle -> Int

packStrategy :: Strategy state -> PackedStrategy
packStrategy str oracle = length $ stepMany str oracle

现在您可以编写 [packStrategy stratOne, packStrategy stratTwo] 等。在此过程中，我们发现了一些重要的东西 - 您从策略中关心的只是它是某些函​​数的函数问题（由预言机表示）到解决问题所需的步骤。产生这种策略的一种方法（不是唯一的方法）是提供一种寻求新知识（猜测）的方法和一种更新我们的知识（更新状态）的方法。

这不是唯一的答案，也许不适合您的目的，但它应该有助于您思考函数和类型，而不是对象和功能。

Answer 2

您可以使用 GADT（广义代数数据类型）和存在性（下面的“forall a.”）精确地完成您想要的操作。类型“Strategy”隐藏了内部类型“a”，它是一个实现细节。调用“go”时的模式匹配将策略的所有部分纳入范围。请注意，我使用 GHC 的 RecordWildCards“{..}”来保存我的手指。之所以能够编译，是因为“go”不会返回任何公开内部类型“a”的内容。

GHC 用户手册中有更多详细信息。

{-# LANGUAGE GADTs, RankNTypes, RecordWildCards #-}
import Control.Monad.State

type Code = [Int]

data Answer = Answer { blacks :: Int, whites :: Int } 
  deriving (Eq, Show)

data Strategy where
    Strategy :: forall a. { strategyName :: String
                          , firstGuess   :: Int -> Code
                          , initialize   :: Int -> a
                          , guess        :: Answer -> State a Code
                          } 
             -> Strategy

dummy = Strategy { strategyName = "dummy"
                 , firstGuess   = firstGuess'
                 , initialize   = initialize'
                 , guess        = guess'
                 }

-- | The very first guess is always T0,T1,...,Tx, where x is the code length.
firstGuess' :: Int -> Code
firstGuess' length = [0..length-1]

-- | Memorize the code length
initialize' :: Int -> Int
initialize' = id

-- | Always return the same guess
guess' :: Answer -> State Int Code
guess' = const $ liftM firstGuess' get

-- Take size and strategy and compute number of steps to win
-- modified to create local type variable 'a' to write type for 'step'
go :: Code -> Strategy -> (String,Int)
go secretCode (Strategy {initialize=initialize::Int->a,..}) =
  let size = length secretCode
      nextAnswer :: Code -> Maybe Answer
      nextAnswer _ = undefined {- compare with secretCode -}

      step :: Code -> Int -> State a (String,Int)
      step code n = case nextAnswer code of
                      Nothing -> return (strategyName,n)
                      Just answer -> do
                        code' <- guess answer
                        step code' $! (succ n)

  in evalState (step (firstGuess size) 0) (initialize size)

通过使用 WriterT，我可以添加猜测的日志：

-- Take size and strategy and compute number of steps to win
goW :: Code -> Strategy -> ((String,Int),[(Code,Answer)])
goW secretCode (Strategy {..}) =
  let size = length secretCode
      nextAnswer :: Code -> Maybe Answer
      nextAnswer _ = undefined {- compare with secretCode -}

      step code n = case nextAnswer code of
                      Nothing -> return (strategyName,n)
                      Just answer -> do
                        code' <- lift (guess answer)
                        tell [(code,answer)]
                        step code' $! (succ n)

  in evalState (runWriterT (step (firstGuess size) 0)) (initialize size)