State Machine using immutable Records in F#

The issue here is that you want to construct an immutable recursive value - an object that contains, somewhere inside, references to itself. This is hard to do in functional languages, because objects are immutable. F# can actually do this in some limited situations.

In your case, you can get the built-in F# recursive intialization to work if you use only primitive value constructors - i.e. not call any functions. I had to replace Map in the list of transitions with plain list, but this works:

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 }

If you want to keep the recursive structure, but initialize it using custom functions, then you will need to have some kind of Lazy somewhere in the data strucutre. Your workaround works as well as any other option. I would probably make the whole Map<..> lazy, which maybe gives you a bit nicer syntax for the construction:

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

It might be better to model the State as simple data-term.

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

I used Map to store the transitions because they give more efficient look-ups, but you could use List instead.

If you want to trigger side-effects during transitions, I would suggest keeping those outside of the state representation.

For example:

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

      do! launchMissiles

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

Since the 'state can be any type, you can also attach arbitrary data to it:

type City = 
  | London
  | NewYork
  | Tokyo

type Fuel = int

type State = City * Fuel