recursion - 在 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}

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

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 表示将在运行时评估对象的初始化健全性。

我可以通过将所有内容包装在惰性中来修复错误:

...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

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

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

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