Это какие-то неправильные умные книжки. Или вы их как-то неправильно поняли. Вот, например, конечный автомат на два состояния - Пыщь и Адын:

open ExtString

type state = Pysh | Adyn 

let fsm evt =
    let input state x = match state, x with
    | Pysh, '{' -> Adyn
    | Pysh, ' ' -> Pysh 
    | Pysh, c   -> Printf.printf "Pysh! %c\n" c; Pysh
    | Adyn, '}' -> Pysh
    | Adyn, ' ' -> Adyn
    | Adyn, c   -> Printf.printf "Adyn! %c\n" c; Adyn 

    in List.fold_left input Pysh (String.explode evt)

let _ = 
    fsm "000000000 { 1111111111111111111 } 2222222222222222222"

никакие монады для его реализации не понадобились, и за исключением побочного эффекта печатания - вполне функционально. Стейт, заметим, есть, но при этом все остается в рамках концепции.

заметим еще, что сделать такой автомат на императивном языке "где есть состояния" c++ - будет несколько более громоздко.