Y型結合器在JavaScript

Question

我建立了一個Y型組合子在JS這樣

const y = f => { const g = self => x => f(self(self))(x); return g(g);} 

，我簡化了這樣

const y = f => { const g = self => f(self(self)); return g(g);} 

此得到無限遞歸的代碼。 這兩個版本有什麼區別？

Answer 1

如果你不明白兩者之間的差別，我會驚訝你實際上建立了它們。然而，也許是爲了證明兩者之間的區別的最好辦法，是按照他們的評價

const y = f => { 
    const g = self => x => f(self(self))(x) 
    return g(g) 
} 

y (z) ... 
// (self => x => z(self(self))(x)) (self => x => z(self(self))(x)) ... 
// returns: 
// x => z((self => x1 => z(self(self))(x1))(self => x2 => z(self(self))(x2)))(x) 

好了，y(z)（其中z一些功能，這並不重要）返回函數x => ...。直到申請那個功能，評價在那裏停止。

現在讓我們來比較，爲您的第二個定義

const y = f => { 
    const g = self => f(self(self)) 
    return g(g) 
} 

y (z) ... 
// (self => z(self(self))) (self => z(self(self))) 
// z((self => z(self(self)))(self => z(self(self)))) ... 
// z(z((self => z(self(self)))(self => z(self(self))))) ... 
// z(z(z((self => z(self(self)))(self => z(self(self)))))) ... 
// z(z(z(z((self => z(self(self)))(self => z(self(self))))))) ... 
// ... and on and on 

所以y (z)永遠不會終止 - 在JavaScript中，它使用應用性爲了評估至少 - 在功能參數進行評估之前被調用的功能應用

---

替代Y-組合器

在這裏，我們可以從組最多

// standard definition 
const Y = f => f (Y (f)) 

// prevent immediate infinite recursion in applicative order language (JS) 
const Y = f => f (x => Y (f) (x)) 

// remove reference to self using U combinator 
const U = f => f (f) 
const Y = U (h => f => f (x =>h (h) (f) (x)))

建立一個Y型組合子讓我們來測試一下

const U = f => f (f) 
 

 
const Y = U (h => f => f (x => h (h) (f) (x))) 
 

 
// range :: Int -> Int -> [Int] 
 
const range = Y (f => acc => x => y => 
 
    x > y ? acc : f ([...acc,x]) (x + 1) (y)) ([]) 
 

 
// fibonacci :: Int -> Int 
 
const fibonacci = Y (f => a => b => x => 
 
    x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) 
 
    
 
console.log(range(0)(10).map(fibonacci)) 
 
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]

還是我最近喜歡

// simplified Y 
 
const Y = f => x => f (Y (f)) (x) 
 

 
// range :: Int -> Int -> [Int] 
 
const range = Y (f => acc => x => y => 
 
    x > y ? acc : f ([...acc,x]) (x + 1) (y)) ([]) 
 

 
// fibonacci :: Int -> Int 
 
const fibonacci = Y (f => a => b => x => 
 
    x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) 
 
    
 
console.log(range(0)(10).map(fibonacci)) 
 
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]