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

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

3. 在最后一个模块中导入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解决的问题吗？似乎我们可以使用某种索引状态monad,我们不知道提前返回状态,我从他的回答中找到了什么是索引monad？,是MonadIx实现的目标.

Answer 1

使用可扩展的总和,我们可以删除步骤1并将步骤3减少为"导入C".

完全删除步骤3和步骤1会产生使最终模块意识到新转换的问题,并且我不确定纯粹使用Haskell是否可行.需要某种元编程(例如,通过TH或CPP).

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

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

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)

我们可以使用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://lpaste.net/1474513567511216128

此示例使用INCOHERENT实例来简化,通过统一生成最终状态集,但是使用显式修复点迭代/图搜索的更强大的解决方案当然是可能的.