javascript - 从没有数组的函数链中提取数据

Question

这是一个高级话题

How to store data of a functional chain of Monoidal List?

我很确定我们可以在不使用存储数据的数组的情况下以某种方式从函数链中提取数据。
基本结构是:

L = a => L

非常简单，但是这个结构会生成一个列表:

L(1)(2)(3)(4)(5)(6)()

这可能与
What is a DList?
，但这种结构仅严格依赖于函数链。

那么，提取整个值的方法是什么？
我目前的成就只是把头和尾拉出来，我不知道如何解决这个问题。

编辑:
我忘了提到我尝试做的是

List.fold(f)/reduce(f)

手术。

因此，如果选择 f 作为 Array.concat 这意味着您可以将数据提取为数组，但简单的 fold 不仅限于数组连接。和 f 可以是加/和等。

所以，目前，到目前为止，为了可视化内部行为，在某种意义上，我将 log 写为 f 。

编辑2

我必须澄清更多。可以提供规范:

const f = (a) => (b) => a + b;//binary operation

A(a)(b)(f) = f(a)(b)  // a + b

A(a)(b)(c)(f) = f(f(a)(b))(c) // a + b + c

所以这正是

(a b c).reduce(f)

事情，当

f = (a) => (b) => a.concat(b)

结果将是 [a, b, c] 。
Array.concat 只是广义二元运算 f 的一个成员。

起初，这个挑战对我的技能来说很容易，但结果很难，我觉得最好问更聪明的编码员。

谢谢。

const A = a => {

    const B = b => (b === undefined)
        ? (() => {
            log("a " + a);
            return A();
        })()
        : c => (c === undefined)
            ? (() => {
                log("b " + b);
                return B()();
            })()
            : B;

    return B;

};
 

A(1)(2)(3)(4)(5)(6)()

function log(m)  {
    console.log((m)); //IO
    return m;
};

结果:

b 6
a 1
a undefined

Answer 1

给定一个像 A(a)(b)(f) 这样的表达式，其中 f 是一个函数，不可能知道 f 是否应该添加到列表中，或者它是否是一个减少函数。因此，我将描述如何编写与 A(a)(b)(f, x) 等价的 [a, b].reduce(f, x) 等表达式。这使我们能够根据您提供的参数数量来区分列表何时结束:

const L = g => function (x, a) {
    switch (arguments.length) {
    case 1: return L(k => g((f, a) => k(f, f(a, x))));
    case 2: return g((f, a) => a)(x, a);
    }
};

const A = L(x => x);

const xs = A(1)(2)(3)(4)(5);

console.log(xs((x, y) => x + y, 0));        // 15
console.log(xs((x, y) => x * y, 1));        // 120
console.log(xs((a, x) => a.concat(x), [])); // [1,2,3,4,5]

它由于延续而起作用。每次我们添加一个新元素，我们都会累积一个 CPS 函数。每个 CPS 函数调用前一个 CPS 函数，从而创建一个 CPS 函数链。当我们给这个 CPS 函数链一个基函数时，它展开链并允许我们减少它。这与 transducers 和 lenses 背后的想法相同。

编辑: user633183's solution 很棒。它使用 Church encoding of lists using right folds 来减轻对延续的需求，从而使代码更简单，易于理解。这是她的解决方案，修改后使 foldr 看起来像 foldl :

const L = g => function (x, a) {
    switch (arguments.length) {
    case 1: return L((f, a) => f(g(f, a), x));
    case 2: return g(x, a);
    }
};

const A = L((f, a) => a);

const xs = A(1)(2)(3)(4)(5);

console.log(xs((x, y) => x + y, 0));        // 15
console.log(xs((x, y) => x * y, 1));        // 120
console.log(xs((a, x) => a.concat(x), [])); // [1,2,3,4,5]

这里的 g 是到目前为止积累的 Church 编码列表。最初，它是空列表。调用 g 从右侧折叠它。但是，我们也从右侧构建列表。因此，由于我们编写它的方式，似乎我们正在构建列表并从左侧折叠它。

如果所有这些功能都让您感到困惑，那么 user633183 真正在做的是:

const L = g => function (x, a) {
    switch (arguments.length) {
    case 1: return L([x].concat(g));
    case 2: return g.reduceRight(x, a);
    }
};

const A = L([]);

const xs = A(1)(2)(3)(4)(5);

console.log(xs((x, y) => x + y, 0));        // 15
console.log(xs((x, y) => x * y, 1));        // 120
console.log(xs((a, x) => a.concat(x), [])); // [1,2,3,4,5]

如您所见，她正在向后构建列表，然后使用 reduceRight 向后折叠向后列表。因此，看起来您正在构建并向前折叠列表。