javascript - 如何存储 Monoidal List 功能链的数据？

Question

这是我之前在这里提出的问题的高级主题:

How to store data of a functional chain?

简要思路是

下面是一个简单的函数:

const L = a => L;

表格

L
L(1)
L(1)(2)
...

这似乎形成了一个列表，但根本没有存储实际数据，所以如果需要存储 [1,2] 等数据，那么完成任务最聪明的做法是什么？

其中一个突出的想法来自@user633183，我将其标记为已接受的答案(参见问题链接)，@Matías Fidemraizer 还提供了另一个版本的柯里化(Currying)函数。

所以这里是:

const L = a => {
  const m = list => x => !x
    ? list
    : m([...list, x]);
  return m([])(a);
}; 

const list1 = (L)(1)(2)(3); //lazy : no data evaluation here
const list2 = (L)(4)(5)(6);

console.log(list1()) // now evaluated by the tail ()
console.log(list2())  

我真正喜欢的是结果是惰性求值。

虽然给定的方法满足我提到的，但是这个函数失去了外部结构或者我必须提到:

代数结构

 const L = a => L;

which forms list and more fundamentally gives us a algebraic structure的 identity element , 可能连同 Monoid或 Magma .

留下了正确的身份

Monoids 和身份的最简单示例之一是 JavaScript 中的数字和 "Strings" 和 [Array]。

0 + a === a === a + 0
1 * a === a === a * 1

在字符串中，空引号 "" 是标识元素。

  "" + "Hello world" === "Hello world" === "Hello world" + ""

[Array] 也是如此。

同样适用于 L:

(L)(a) === (a) === (a)(L)

const L = a => L;

const a = L(5); // number is wrapped or "lift" to Type:L
                // Similarity of String and Array
                // "5"  [5]

//left identity
console.log(
  (L)(a) === (a)    //true 
);
 
//right identity
console.log(
  (a) === (a)(L)    //true
); 

以及明显的身份不变性:

const L = a => L;
 
console.log(
  (L)(L) === (L)    //true
); 
console.log(
  (L)(L)(L) === (L)    //true
); 
console.log(
  (L)(L)(L)(L) === (L)    //true
); 

还有以下内容:

const L = a => L;

const a = (L)(1)(2)(3);
const b = (L)(1)(L)(2)(3)(L);

 
console.log(
   (a) === (b)    //true 
);
 

问题

实现满足 3 个要求的 L 的最聪明或最优雅的方法是什么(非常实用且没有突变(也没有 Array.push)) :

要求 0 - 身份

一个简单的函数:

const L = a => L;

已经满足我们已经看到的恒等律。

要求 1 - eval() 方法

虽然L满足恒等律，但是没有办法访问列出/累积的数据。

(我在上一个问题中提供的答案提供了数据积累能力，但违反了身份法则。)

惰性评估似乎是正确的方法，因此提供更清晰的规范:

提供L的eval方法

const L = a => L; // needs to enhance to satisfy the requirements

const a = (L)(1)(2)(3);
const b = (L)(1)(L)(2)(3)(L);


console.log(
   (a) === (b)    //true 
);

console.log(
   (a).eval()    //[1, 2, 3]
);

console.log(
   (b).eval()    //[1, 2, 3]
);

要求 3 - 幺半群结合律

除了突出的Identify结构，Monoids还满足Associative law

(a * b) * c === a * b * c === a * (b * c)

这只是意味着“扁平化列表”，换句话说，该结构不包含嵌套列表。

[a, [b, c]] 不好。

示例:

const L = a => L; // needs to enhance to satisfy the requirements

const a = (L)(1)(2);
const b = (L)(3)(4);
const c = (L)(99);

const ab = (a)(b);
const bc = (b)(c);
const abc1 = (ab)(c);
const abc2 = (a)(bc);

console.log(
   abc1 === abc2  // true for Associative
);

console.log(
   (ab).eval()    //[1, 2, 3, 4]
);

console.log(
   (abc1).eval()   //[1, 2, 3, 4, 99]
);
console.log(
   (abc2).eval()   //[1, 2, 3, 4, 99]
);

这就是将 L 实现为幺半群的 3 个要求。

这对我来说是函数式编程的一个巨大挑战，实际上我自己尝试了一段时间，但是问前面的问题，分享我自己的挑战并听取人们的意见并阅读他们优雅的代码是很好的练习。

谢谢。

Answer 1

您的数据类型不一致!

所以，你想创建一个幺半群。考虑一个幺半群的结构:

class Monoid m where
    empty :: m           -- identity element
    (<*>) :: m -> m -> m -- binary operation

-- It satisfies the following laws:

empty <*> x = x = x <*> empty     -- identity law
(x <*> y) <*> z = x <*> (y <*> z) -- associativity law

现在，考虑您的数据类型的结构:

(L)(a) = (a) = (a)(L)     // identity law
((a)(b))(c) = (a)((b)(c)) // associativity law

因此，根据您的说法，标识元素是 L，二元运算是 function application .然而:

(L)(1)                  // This is supposed to be a valid expression.
(L)(1) != (1) != (1)(L) // But it breaks the identity law.

// (1)(L) is not even a valid expression. It throws an error. Therefore:

((L)(1))(L)                // This is supposed to be a valid expression.
((L)(1))(L) != (L)((1)(L)) // But it breaks the associativity law.

问题是您将二元运算与反向列表构造函数混为一谈:

// First, you're using function application as a reverse cons (a.k.a. snoc):

// cons :: a -> [a] -> [a]
// snoc :: [a] -> a -> [a] -- arguments flipped

const xs = (L)(1)(2); // [1,2]
const ys = (L)(3)(4); // [3,4]

// Later, you're using function application as the binary operator (a.k.a. append):

// append :: [a] -> [a] -> [a]

const zs = (xs)(ys); // [1,2,3,4]

如果您将函数应用程序用作snoc，那么您也不能将它用于append:

snoc   :: [a] ->  a  -> [a]
append :: [a] -> [a] -> [a]

请注意类型不匹配，但即使匹配，您仍然不希望一个操作做两件事。

你想要的是差异列表。

A difference list是一个函数，它接受一个列表并将另一个列表添加到它的前面。例如:

const concat = xs => ys => xs.concat(ys); // This creates a difference list.

const f = concat([1,2,3]); // This is a difference list.

console.log(f([])); // You can get its value by applying it to the empty array.

console.log(f([4,5,6])); // You can also apply it to any other array.

差异列表的酷之处在于它们形成一个幺半群，因为它们只是 endofunctions :

const id = x => x; // The identity element is just the id function.

const compose = (f, g) => x => f(g(x)); // The binary operation is composition.

compose(id, f) = f = compose(f, id);                   // identity law
compose(compose(f, g), h) = compose(f, compose(g, h)); // associativity law

更好的是，您可以将它们打包成一个简洁的小类，其中函数组合是点运算符:

class DList {
    constructor(f) {
        this.f  = f;
        this.id = this;
    }

    cons(x) {
        return new DList(ys => this.f([x].concat(ys)));
    }

    concat(xs) {
        return new DList(ys => this.f(xs.concat(ys)));
    }

    apply(xs) {
        return this.f(xs);
    }
}

const id = new DList(x => x);

const cons = x => new DList(ys => [x].concat(ys));   // Construct DList from value.

const concat = xs => new DList(ys => xs.concat(ys)); // Construct DList from array.

id . concat([1, 2, 3]) = concat([1, 2, 3]) = concat([1, 2, 3]) . id // identity law

concat([1, 2]) . cons(3) = cons(1) . concat([2, 3]) // associativity law

您可以使用 apply 方法检索 DList 的值，如下所示:

class DList {
    constructor(f) {
        this.f  = f;
        this.id = this;
    }

    cons(x) {
        return new DList(ys => this.f([x].concat(ys)));
    }

    concat(xs) {
        return new DList(ys => this.f(xs.concat(ys)));
    }

    apply(xs) {
        return this.f(xs);
    }
}

const id = new DList(x => x);

const cons = x => new DList(ys => [x].concat(ys));

const concat = xs => new DList(ys => xs.concat(ys));

const identityLeft  = id . concat([1, 2, 3]);
const identityRight = concat([1, 2, 3]) . id;

const associativityLeft  = concat([1, 2]) . cons(3);
const associativityRight = cons(1) . concat([2, 3]);

console.log(identityLeft.apply([]));  // [1,2,3]
console.log(identityRight.apply([])); // [1,2,3]

console.log(associativityLeft.apply([]));  // [1,2,3]
console.log(associativityRight.apply([])); // [1,2,3]

与常规列表(功能列表，而不是 JavaScript 数组)相比，使用差异列表的一个优势是连接效率更高，因为列表是从右到左连接的。因此，如果您连接多个列表，它不会一遍又一遍地复制相同的值。