haskell - Haskell 中的可扩展状态机

Question

我可以定义一个玩具状态机(使用简单的输入)如下:

--------------------------------------------
-- module State where

data State = A | B Int

--------------------------------------------
-- module A where
-- import State

transitionA :: State
transitionA = B 10

--------------------------------------------
-- module B where
-- import State

transitionB :: Int -> State
transitionB i
  | i < 0     = A
  | otherwise = B (i-1)

--------------------------------------------
-- module StateMachine where
-- import State
-- import A
-- import B

transition :: State -> State
transition A     = transitionA
transition (B i) = transitionB i

如果我现在决定添加新状态，我必须:

1. 修改 State 模块以添加新状态

 

data State = A | B Int | C Double Double

在模块C中添加新的转换函数transitionC

在最后一个模块中导入C，并将C的大小写添加到模式匹配中

我想进行设置，以便我只需执行步骤 2(编写新的转换函数)，其他所有事情都会自动处理。
例如，可以尝试使用存在类型来执行以下操作:

--------------------------------------------
{-# LANGUAGE ExistentialQuantification #-}
-- module State where

class State s where
    transition :: s -> AState

data AState = forall s. State s => AState s

instance State AState where
    transition (AState s) = transition s

-------------------------------------
-- module A where
-- import State
-- import B

data A = A

instance State A where
  transition _ = AState (B 10)

-------------------------------------
-- module B where
-- import State
-- import A

data B = B Int

instance State B where
    transition (B i)
      | i < 0     = AState ( A )
      | otherwise = AState ( B (i-1) )

这非常方便:要添加新的状态，我们只需要做一件事，就是在新模块中编写数据类型及其关联的转换函数，其他不需要更改。不幸的是，这种方法不起作用，因为它会创建循环依赖关系，例如在这种情况下，A 需要引用 B，B 需要引用 A。

我还尝试考虑使用可扩展的求和类型(多态变体)，但是除非我们在单独的模块中提前声明所有可能的状态以便后续模块可以引用它们，否则会出现同样的问题。换句话说，它可以消除步骤3，但不能消除步骤1。

这种问题可以使用索引单子(monad)(Conor McBride 的版本)来解决吗？看来我们可以使用某种索引状态单子(monad)，我们事先不知道返回状态，这是我从他对 What is indexed monad? 的回答中收集到的。 ，是 MonadIx 实现的目标。

Answer 1

使用可扩展和，我们可以删除步骤 1 并将步骤 3 减少为“导入 C”。

完全删除步骤 3 和步骤 1 会带来使最终模块了解新转换的问题，并且我不确定纯粹使用 Haskell 是否可能实现这一点。需要某种类型的元编程(例如，通过 TH 或 CPP)。

作为一种替代(且更简单)的方法，我将状态集推断为从预定初始状态可到达的状态，这意味着步骤 2 可能还包括对现有转换函数的一些更改，以使新状态可到达 。我希望这是一个合理的假设。

<小时/>

如果我们将状态不需要预先声明作为约束，我们仍然需要某种字母来引用这些状态。 GHC 的 Symbol 给出了一个方便的字母表。 type(类型级字符串)。我们将符号包装在新的类型构造函数中，以使事情更加卫生:应用程序可以通过声明自己的 Named 版本来创建新的状态 namespace 。 .

data Named (s :: Symbol)

每种类型Named s是标识状态类型的“名称”或“键”( k )，例如 Named "A"或Named "B" 。我们可以使用类型类将它们关联到

• 其内容的类型(例如 B 包含 Int )；
• 可能的输出状态集，每个状态都以其名称和内容对的形式给出。

该类型类还包含为每个状态定义的转换函数。

class State k where
  type Contents k :: *
  type Outputs k :: [(*, *)]
  transition :: Contents k -> S (Outputs k)

S是可扩展的求和类型。例如，S '[ '(Named "A", ()), '(Named "B", Int) ]是 "A" 标记的单位的总和和一个Int标记为 "B" .

data S (u :: [(*, *)]) where
  Here :: forall k a u. a -> S ('(k, a) ': u)
  There :: forall u x. S u -> S (x ': u)

我们可以使用智能构造函数自动将类型注入(inject)总和 inj1 @k按键k索引.

-- v is a list containing the pair (k, a)
-- instances omitted
class Inj1 k a v where
  inj1 :: a -> S v

<小时/>

跳过整个设置，让我们看看使用这个框架会是什么样子。

要创建新的转换，需要声明 State 的实例。 。唯一的依赖项是一般依赖项。如前所述，文件不需要知道一组预定的状态，它声明它需要什么。

模块A

-- Transitions out of A
instance State (Named "A") where

  -- There is no meaningful value contained in the A state
  type Contents (Named "A") = ()

  -- The only transition is to "B"
  type Outputs (Named "A") = '[ '(Named "B", Int)]

  transition () = inj1 @(Named "B") 10

模块B

-- transitions out of B
instance State (Named "B") where
  type Contents (Named "B") = Int
  type Outputs (Named "B") = '[ '(Named "A", ()), '(Named "B", Int)]
  transition i
    | i < 0 = inj1 @(Named "A") ()
    | otherwise = inj1 @(Named "B") (i-1)

在主模块中，我们仍然需要导入所有转换，并选择一个可以计算可达状态的初始状态。

import A
import B

type Initial = Named "A"

-- Initial state A
initial :: Inj1 Initial () u => S u
initial = inj1 @Initial ()

给定初始状态的名称，有一个通用函数可以生成完整的转换函数，从而生成可到达状态的完整列表。

sm :: forall initial u ...
   .  (... {- all reachable states from 'initial' are in 'u' -})
   => S u -> S u

因此我们可以按如下方式定义和使用转换:

transition' = sm @Initial  -- everything inferred (S _ -> S _)

-- Run 14 steps from the initial state.
main = do
  let steps = 14
  mapM_ print . take (steps+1) . iterate transition' $ initial

输出:

Here ()
There Here 10
There Here 9
There Here 8
There Here 7
There Here 6
There Here 5
There Here 4
There Here 3
There Here 2
There Here 1
There Here 0
There Here -1
Here ()
There Here 10

<小时/>

希望很明显 State类型类在类型级别提供了足够的信息来重建完整的状态机。从那里开始，“只是”类型级编程的问题，使这种直觉成为现实。如果有提示，我可以多谈一点，但现在这是一个完整的示例:

https://gist.github.com/Lysxia/769ee0d4eaa30004aa457eb809bd2786

此示例使用 INCOHERENT为了简单起见，通过统一生成最终的状态集，但是具有显式固定点迭代/图搜索的更强大的解决方案当然是可能的。