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

Question

В previous question Мне сказали, как переписать мои выражения вычислений, чтобы использовать хвостовую рекурсию. Я переписал свой код, но все еще получил исключение StackOverflowException. Для того, чтобы найти проблему, я написал некоторый маленький код, используя государственные монады (взятые из this blog entry):

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 можно использовать хвостовую рекурсию (?). Я думаю, что что-то не так с классом StateBuilder. Я пытался что-то сделать с помощью метода Delay. Сотрясать все в дополнительной лямбде, без успеха. Im полностью застрял в данный момент. Вот моя вторая попытка (не компилируется):

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, потому что вы запускаете программу в режиме отладки с отключенным хвостового вызова поколения. Если вы перейдете к свойствам проекта, вы можете найти Генерировать хвостовые звонки checkbox на Build tab. Когда я создаю новый проект, я могу воспроизвести его, но после проверки этого параметра он отлично работает (даже для гораздо большего числа итераций).

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

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