Thunk 递归内部递归

Question

给定一个函数

m(a, b) = 1

如果

n = 0

和

m(a, b) = m(a-q, m(a,b))

否则。

我想用thunk来控制这个函数的求值，我就是这么做的。我对这个解决方案的意图是让代码尽可能清晰，尤其是功能代码：

let thunk_ite i t e =
  match i with
  | true -> t ()
  | false -> e () ;;

let rec m_thunk a b = 
  thunk_ite 
    (a() = 0) 
    (fun () -> 1) 
    (fun () -> 
       m_thunk 
         ((fun () -> a() - 1)) 
         (fun () -> (m_thunk a b)));;

let m a b = 
  m_thunk (fun () -> a) (fun () -> b);;

m 1 0;;

这是正确的吗？

给出的解决方案是：

let rec mthunk a b = 
  let r = a() in 
  match r with 
  | 0 -> (fun () -> 1)
  | _-> mthunk (fun () -> r - 1) (fun ()-> (mthunk a b)());;

let m_bis a b = mthunk (fun ()-> a) (fun () -> b) ();;

m_bis 1 0;;

我知道它更短，但我只做了我的版本，所以我可以跟随我的思维过程。

Answer 1

你似乎错过了一个重要的点是在抽象上调用你的

thunk_ite

函数

thunk_ite i (fun () -> a) (fun () -> b)

严格等同于写作

if i then a else b

因此您的

m

函数可以重写为

let rec m_thunk a b = 
  if a() = 0 then 
    1
  else 
    m_thunk 
     (fun () -> a() - 1) 
     (fun () -> m_thunk a b);;

这应该使这个功能和

之间的区别

let rec mthunk a b = 
  let r = a() in 
  if r = 0 then 
    (fun () -> 1)
  else
    mthunk (fun () -> r - 1) (fun () -> mthunk a b ());;

更明显。