読者です 読者をやめる 読者になる 読者になる

歩いたら休め

If the implementation is easy to explain, it may be a good idea.

【R】Yコンビネータ(不動点コンビネータ)をRで写経する

R

最近関数型言語(主にHaskell)で遊んでいます。

その中「ラムダ式の中で再帰を行うことができる」Yコンビネータという概念が出てきたのですが、ちょっと理解できなかったので、Rで実装してみたという記事です。

Pythonによる実装は以下の記事に詳しく解説されているので、これを基に「Rを使ったYコンビネータによる階乗の実装」をRで再実装(写経)してみました。

時間城年代記:PythonによるYコンビネータの仕組みの(多分)わかりやすい説明

解説もしようと思ったのですが、思ったよりエグいのと、元記事が素晴らしいのでそれで済ませます…。

yconv <- function(f) {
  (function(x) {
    function(m) {
      f(x(x))(m)
    }
  })(
    function(x) {
      function(m) {
        f(x(x))(m)
      }
    }
  )
}

func <- function(f) {
  function(n) {
    if(n < 2) {
      n
    } else {
      f(n - 1) * n
    }
  }
}

yconv(func)(5)
# => 120

ところで、Rでは当然関数での再帰は使えますし、再帰専用のRecallという関数も用意されているので、Yコンビネータを使う必要はありません。

Wikipediaの不動点コンビネータの記事にも、

不動点コンビネータにより、第一級関数をサポートしているプログラミング言語において、明示的に再帰を書かずに再帰を実現する為に用いる事ができる。なお、一般にそういった言語では普通に再帰が使えるので、プログラミングにおいてはパズル的なテクニック以上の意味は無い。

とあります。ラムダ計算の理論では重要らしいですが。