代码之家 › 专栏 › 技术社区 › Aadit M Shah

如何递归定义广义投影函数?

combinatory-logic functional-programming recursion javascript

0

Aadit M Shah · 技术社区 · 6 年前

Projection functions 例如 id ( ^一第页 _一 )以及 const ( ^二第页 _一 )在函数式编程中非常有用。但是,有时需要更复杂的投影函数,如 ^五第页 _四 . 你可以用有意义的方式手工编写 a => b => c => d => e => d 但这是乏味的,不太可读。因此,最好能写 proj(5)(4) 相反。下面是我目前如何在JavaScript中定义这个广义投影函数:

const proj = n => m => curry(n, (...args) => args[m - 1]);

const curry = (n, f, args = []) => n > 0 ?
    x => curry(n - 1, f, args.concat([x])) :
    f(...args);

console.log(proj(5)(4)("a")("b")("c")("d")("e")); // prints "d"

如您所见,这个 proj 是一个黑客,因为它使用可变参数。因此,它不能直接翻译成像Agda或Idris这样的语言(在这种语言中,由于依赖类型,广义投影函数实际上是可输入的)。那么,如何递归地定义一个广义投影函数,使它可以直接转换成Agda呢?

1 回复 | 直到 6 年前

1

0

Aadit M Shah 6 年前

所有投影函数可以分解为以下三个组合:

I :: a -> a
I x = x

K :: a -> b -> a
K x y = x

C :: (a -> c) -> a -> b -> c
C f x y = f x

使用这三个组合词,我们可以定义如下各种投影函数:

âââââââ¬âââââââââââ¬âââââââââââ¬âââââââââââ¬âââââââââââ¬ââââââââââââââ
â n\m â     1    â     2    â     3    â     4    â      5      â
âââââââ¼âââââââââââ¼âââââââââââ¼âââââââââââ¼âââââââââââ¼ââââââââââââââ¤
â  1  â      I   â          â          â          â             â
â  2  â      K   â     KI   â          â          â             â
â  3  â     CK   â     KK   â   K(KI)  â          â             â
â  4  â   C(CK)  â   K(CK)  â   K(KK)  â K(K(KI)) â             â
â  5  â C(C(CK)) â K(C(CK)) â K(K(CK)) â K(K(KK)) â K(K(K(KI))) â
âââââââ´âââââââââââ´âââââââââââ´âââââââââââ´âââââââââââ´ââââââââââââââ

如您所见,这里有一个递归模式:

proj 1 1 = I
proj n 1 = C (proj (n - 1) 1)
proj n m = K (proj (n - 1) (m - 1))

请注意 K = CI 这就是为什么 proj 2 1 作品。将其直接转换为JavaScript:

const I = x => x;
const K = x => y => x;
const C = f => x => y => f(x);

const raise = (Error, msg) => { throw new Error(msg); };

const proj = n => n === 1 ?
    m => m === 1 ? I : raise(RangeError, "index out of range") :
    m => m === 1 ? C(proj(n - 1)(1)) : K(proj(n - 1)(m - 1));

console.log(proj(5)(4)("a")("b")("c")("d")("e")); // prints "d"

我将把它作为练习留给您,让您了解这个函数的依赖类型。