在 F# 中使用不可变记录的状态机

Question

我对 F# 中的状态机有以下定义：

type MyEvent = Event1 | Event2 | Event3

type MachineState<'event when 'event:comparison> =
    {
    Transitions: Map<'event, MachineState<'event>>
    Data: int
    //...other State stuff, like parent state, entry/exit actions etc 
    }
    static member Default = {Transitions=Map.empty}

//simple helpers
let on event endState state =
    {state with Transitions = state.Transitions.Add(event, endState)}
let withData data state = {state with Data = data}

我的想法是，给定一个状态和一个事件，我将在转换映射中搜索事件键，如果找到，我将 return 新状态，否则将 return当前的。状态定义如下：

let rec StateA =
    MachineState<_>.Default
    |> on Event1 StateB
    |> withData 5
and StateB =
    MachineState<_>.Default
    |> on Event2 StateC
    |> withData -999
and StateC =
    MachineState<_>.Default
    //|> on Event3 StateA //This actually gives a runtime error
    |> withData 84

这给了我两个问题：一个错误 FS0031，表示 StateA 是它自己定义的一部分，还有一个警告，warn40，表示将在运行时评估对象的初始化可靠性。

我可以通过将所有内容包装在 lazy 中来修复错误：

...Transitions: Map<'event, Lazy<MachineState<'event>>>...
let rec StateA =
    lazy (MachineState<_>.Default
    |> on Event1 StateB)
and StateB =
    lazy (MachineState<_>.Default
    |> on Event2 StateC)
and StateC =
    lazy (MachineState<_>.Default
    |> on Event3 StateA)

这并没有解决警告问题，感觉有点勉强。

这是解决此问题的最佳方法吗？有没有更好的方法来处理不可变的递归结构？或者，更具体地说，实施不可变的 HFSM？

此 fiddle 包含一个运行示例：https://dotnetfiddle.net/TjjeBz

Answer 1

最好将 State 建模为简单的数据项。

type State =
  | A
  | B
  | C

type Event = 
  | Event1
  | Event2
  | Event3

type StateMachine<'state, 'ev when 'state : comparison and 'ev : comparison> = 
  {
    Transitions : Map<'state, Map<'ev, 'state>>
  }
  with 
    static member Default 
      with get () = 
        {
          Transitions = Map.empty
        }

module StateMachine = 
  
  let addTransition startState ev endState sm = 
    let m = 
      sm.Transitions
      |> Map.tryFind startState
      |> Option.defaultValue Map.empty
      |> Map.add ev endState

    {
      sm with
        Transitions = 
          sm.Transitions
          |> Map.add startState m
    }

  let tryTransition state ev sm = 
    sm.Transitions
    |> Map.tryFind state
    |> Option.defaultValue Map.empty
    |> Map.tryFind ev

let myStateMachine : StateMachine<State, Event> = 
  StateMachine<State, Event>.Default
  |> StateMachine.addTransition A Event1 B
  |> StateMachine.addTransition B Event2 C
  |> StateMachine.addTransition C Event3 A

printfn "%A" (myStateMachine |> StateMachine.tryTransition A Event1)
// Some B

printfn "%A" (myStateMachine |> StateMachine.tryTransition A Event2)
// None

我使用 Map 来存储转换，因为它们提供更有效的查找，但您可以改用 List。

如果您想在转换期间触发副作用，我建议将它们保留在状态表示之外。

例如：

let transitionAction previousState nextState = 
  match previousState, nextState with
  | (A, B) -> 
    async {
      printfn "Launching the missiles... "

      do! launchMissiles

      printfn "Game over."
    }
  | (_, _) -> 
    async {
      () // Do nothing
    }

由于 'state 可以是任何类型，您也可以向其附加任意数据：

type City = 
  | London
  | NewYork
  | Tokyo

type Fuel = int

type State = City * Fuel

Answer 2

这里的问题是您想要构造一个不可变的递归值 - 一个在内部某处包含对自身的引用的对象。这在函数式语言中很难做到，因为对象是不可变的。 F# 实际上可以在某些有限的情况下执行此操作。

在您的情况下，如果您仅使用原始值构造函数，则可以使内置的 F# 递归初始化工作 - 即不调用任何函数。我不得不用普通 list 替换转换列表中的 Map，但这有效：

type MyEvent = Event1 | Event2 | Event3

type MachineState<'event when 'event:comparison> =
  { Transitions: ('event * MachineState<'event>) list
    Data: int }
  static member Default = {Transitions=[]; Data=1}


let rec StateA = 
  { Transitions = [ Event1, StateB] 
    Data = 5 }
and StateB = 
  { Transitions = [ Event1, StateC] 
    Data = -999 }
and StateC = 
  { Transitions = [ Event1, StateA] 
    Data = 84 }

如果您想保留递归结构，但使用自定义函数对其进行初始化，那么您将需要在数据结构的某处有某种 Lazy。您的解决方法与任何其他选项一样有效。我可能会使整个 Map<..> 变得懒惰，这可能会为您提供更好的构造语法：

type MachineState<'event when 'event:comparison> =
  { Transitions: Lazy<Map<'event, MachineState<'event>>>
    Data: int }
  static member Default = {Transitions=lazy Map.empty; Data=1}

let on event (endState:Lazy<_>) state =
    {state with Transitions = lazy state.Transitions.Value.Add(event, endState.Value)}
let withData data state = {state with Data = data}

let rec StateA =
    MachineState<_>.Default
    |> on Event1 (lazy StateB)
    |> withData 5
and StateB =
    MachineState<_>.Default
    |> on Event2 (lazy StateC)
    |> withData -999 
and StateC =
    MachineState<_>.Default 
    |> on Event3 (lazy StateA)
    |> withData 84

在 F# 中使用不可变记录的状态机

State Machine using immutable Records in F#

recursion

f#

immutability

fsm