(Как) могу ли я сделать эту монадическую привязку хвостовой рекурсивной?

Ответ 1

Мне кажется, что ваша монада - это государство с обработкой ошибок.

В основном это ErrorT< State<'s,Either<'e,'a>>> , но ветвь ошибки снова связывается, что мне не очень понятно почему.

Во всяком случае, я смог воспроизвести ваш переполнение стека с помощью основной государственной монады:

type State<'S,'A> = State of ('S->('A * 'S))

module State =
    let run (State x) = x :'s->_
    let get() = State (fun s -> (s , s))  :State<'s,_>
    let put x = State (fun _ -> ((), x))  :State<'s,_>
    let result a = State(fun s -> (a, s))
    let bind (State m) k = State(fun s -> 
                                    let (a, s') = m s
                                    let (State u) = (k a) 
                                    u s')     :State<'s,'b>

    type StateBuilder() =
        member this.Return op = result op
        member this.Bind (m, cont) = bind m cont

    let state = StateBuilder()

    let rec loop (i: 'i) (next: 'i -> 'i) (pred: 'i ->  -> bool) (m: 'i -> State<'s, unit>) =
        state {
            let! s = get()
            do! if pred i s then
                    state {
                        do! m i
                        let i = next i
                        do! loop i next pred m }
                else result () }

    let during (pred :  -> bool) (m : State<'s, unit>) =
        loop () id (fun _ -> pred) (fun _ -> m)

// test
open State
ignore <| run (state { do! during (fun c -> true) (result ()) })  () // boom

Как указано в комментариях, один из способов решения этой проблемы - использовать StateT<'s,Cont<'r,'a>>.

Вот пример решение. В конце есть тест с функцией zipIndex, которая также ударяет по стеклу, когда определяется с нормальной монадой штата.

Заметьте, что вам не нужно использовать Monad Transformers из FsControl, я использую их, потому что это легче для меня, поскольку я пишу меньше кода, но вы всегда можете создать свою преобразованную монаду вручную.