Рекурсивные вычисления выражений

Question

В предыдущем вопросе мне сказали, как переписать мои вычислительные выражения, чтобы он использовал хвостовую рекурсию.Я переписал свой код, но все еще получил исключение StackOverflowException.Чтобы найти проблему, я написал небольшой код с использованием монады состояний (взятой из этой записи в блоге ):

type State<'a, 's> = State of ('s -> 'a * 's)

let runState (State s) initialState = s initialState

let getState = State (fun s -> (s,s))
let putState s = State (fun _ -> ((),s))

type StateBuilder() =
  member this.Return a = State (fun s -> (a, s))
  member this.Bind(m, k) = 
    State (fun s -> let (a,s') = runState m s in runState (k a) s')
  member this.ReturnFrom a = a
let state = new StateBuilder()

let s max = 
    let rec Loop acc = state {
        let! n = getState
        do! putState (n + 1)
        if acc < max then
            return! Loop (acc + 1)
        else return acc
        }
    Loop 0

runState (s 100000) 0

Это снова вызывает исключение StackOverflowException, хотя функция Loop может использовать tailрекурсия (?).Я думаю, что-то не так с классом StateBuilder.Я пытался что-то сделать с помощью метода задержки.Заворачивать все в лишнюю лямбду, безуспешно.Я полностью застрял на данный момент.Вот моя вторая попытка (не компилируется):

type State<'a, 's> = State of ('s -> 'a * 's)

let runState (State s) initialState = s initialState

let getState = fun () -> State (fun s -> (s,s))
let putState s = fun () -> State (fun _ -> ((),s))

type StateBuilder() =
  member this.Delay(f) = fun () -> f()
  member this.Return a = State (fun s -> (a, s))
  member this.Bind(m, k) = 
    fun () -> State (fun s -> let (a,s') = runState (m ()) s in runState ((k a) ()) s')
  member this.ReturnFrom a = a
let state = new StateBuilder()

let s max = 
    let rec Loop acc = state {
        let! n = getState
        do! putState (n + 1 - acc)
        if acc < max then
            return! Loop (acc + 2)
        else return acc
        }
    Loop 0

runState (s 100000 ()) 0

Answer 1

Боюсь, что вы можете получить StackOverflowException, потому что вы запускаете программу в режиме отладки с отключенной генерацией хвостовых вызовов.Если вы зайдете в Свойства проекта, то на вкладке Сборка вы можете найти флажок Генерация хвостовых вызовов .Когда я создаю новый проект, я могу воспроизвести поведение, но после проверки этого параметра, он работает нормально (даже для гораздо большего числа итераций).

Причина, по которой хвостовые вызовы по умолчанию отключены вРежим отладки заключается в том, что он значительно усложняет отладку (если вызов выполняется как хвостовой вызов, вы не увидите его в окне Call Stack )

Это будетдовольно глупая причина ошибки ... извините, что я забыл упомянуть об этом, когда вы спросили ранее!