Haskell 中的可扩展状态机
Extensible state machines in Haskell
我可以定义一个玩具状态机(带有简单的输入)如下:
--------------------------------------------
-- 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
如果我现在决定添加一个新状态,我必须:
- 修改状态模块以添加新状态,比如说
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步。
这种问题可以使用(Conor McBride 版本的)索引 monad 来解决吗?似乎我们可以在我们事先不知道 return 状态的情况下使用某种索引状态 monad,我从他对 的回答中收集到的是 MonadIx 实现的。
使用可扩展求和,我们可以删除第 1 步,将第 3 步减少到 "import C"。
完全删除第 3 步和第 1 步会带来让最终模块知道新转换的问题,我不确定纯粹使用 Haskell 是否可行。需要某种元编程(例如,通过 TH 或 CPP)。
作为替代(和更简单)的方法,我将状态集推断为从预定初始状态可到达的状态,这意味着步骤 2 可能还包括对现有转换函数的一些更改,以 使新状态可达。我希望这是一个公平的假设。
如果我们将状态不需要预先声明作为约束条件,我们仍然需要某种字母表来引用这些状态。 GHC 的 Symbol
类型(类型级字符串)给出了一个方便的字母表。我们将符号包装在一个新的类型构造函数中以使事情更卫生:应用程序可以通过声明其自己的 Named
.
版本来创建新的状态命名空间
data Named (s :: Symbol)
每个类型 Named s
都是一个 "name" 或 "key" (k
) 来标识一种状态,例如 Named "A"
或 Named "B"
.我们可以使用类型 class 将它们关联到
- 其内容的类型(例如,
B
包含一个 Int
);
- 一组可能的输出状态,每个状态都以其名称和内容的形式给出。
此类型class还包含要为每个状态定义的转换函数。
class State k where
type Contents k :: *
type Outputs k :: [(*, *)]
transition :: Contents k -> S (Outputs k)
S
是一种可扩展的求和类型。例如,S '[ '(Named "A", ()), '(Named "B", Int) ]
是由 "A"
标记的单位和 "B"
标记的 Int
的总和。
data S (u :: [(*, *)]) where
Here :: forall k a u. a -> S ('(k, a) ': u)
There :: forall u x. S u -> S (x ': u)
我们可以使用由键 k
.
索引的智能构造函数 inj1 @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
类型 class 能够在类型级别提供足够的信息来重建完整的状态机。从那里 "just" 类型级编程的问题,使直觉成为现实。如果出现提示,我可以多谈一点,但现在这里有一个完整的例子:
https://gist.github.com/Lysxia/769ee0d4eaa30004aa457eb809bd2786
为了简单起见,此示例使用 INCOHERENT
个实例,通过统一生成最终的状态集,但是使用显式固定点 iteration/graph 搜索的更强大的解决方案当然是可能的。
我可以定义一个玩具状态机(带有简单的输入)如下:
--------------------------------------------
-- 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
如果我现在决定添加一个新状态,我必须:
- 修改状态模块以添加新状态,比如说
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步。
这种问题可以使用(Conor McBride 版本的)索引 monad 来解决吗?似乎我们可以在我们事先不知道 return 状态的情况下使用某种索引状态 monad,我从他对
使用可扩展求和,我们可以删除第 1 步,将第 3 步减少到 "import C"。
完全删除第 3 步和第 1 步会带来让最终模块知道新转换的问题,我不确定纯粹使用 Haskell 是否可行。需要某种元编程(例如,通过 TH 或 CPP)。
作为替代(和更简单)的方法,我将状态集推断为从预定初始状态可到达的状态,这意味着步骤 2 可能还包括对现有转换函数的一些更改,以 使新状态可达。我希望这是一个公平的假设。
如果我们将状态不需要预先声明作为约束条件,我们仍然需要某种字母表来引用这些状态。 GHC 的 Symbol
类型(类型级字符串)给出了一个方便的字母表。我们将符号包装在一个新的类型构造函数中以使事情更卫生:应用程序可以通过声明其自己的 Named
.
data Named (s :: Symbol)
每个类型 Named s
都是一个 "name" 或 "key" (k
) 来标识一种状态,例如 Named "A"
或 Named "B"
.我们可以使用类型 class 将它们关联到
- 其内容的类型(例如,
B
包含一个Int
); - 一组可能的输出状态,每个状态都以其名称和内容的形式给出。
此类型class还包含要为每个状态定义的转换函数。
class State k where
type Contents k :: *
type Outputs k :: [(*, *)]
transition :: Contents k -> S (Outputs k)
S
是一种可扩展的求和类型。例如,S '[ '(Named "A", ()), '(Named "B", Int) ]
是由 "A"
标记的单位和 "B"
标记的 Int
的总和。
data S (u :: [(*, *)]) where
Here :: forall k a u. a -> S ('(k, a) ': u)
There :: forall u x. S u -> S (x ': u)
我们可以使用由键 k
.
inj1 @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
类型 class 能够在类型级别提供足够的信息来重建完整的状态机。从那里 "just" 类型级编程的问题,使直觉成为现实。如果出现提示,我可以多谈一点,但现在这里有一个完整的例子:
https://gist.github.com/Lysxia/769ee0d4eaa30004aa457eb809bd2786
为了简单起见,此示例使用 INCOHERENT
个实例,通过统一生成最终的状态集,但是使用显式固定点 iteration/graph 搜索的更强大的解决方案当然是可能的。