如何存储 Monoidal List 函数链的数据? [英] How to store data of a functional chain of Monoidal List?
问题描述
这是我上一个问题的高级主题:
简单的想法是
下面是一个简单的函数:
const L = a =>升；表格
LL(1)L(1)(2)...这似乎形成了一个列表，但实际数据根本没有存储，所以如果需要存储诸如[1,2]之类的数据，那么完成任务的最聪明做法是什么?
其中一个突出的想法来自@user633183，我将其标记为已接受的答案(请参阅问题链接)，@Matías Fidemraizer 还提供了另一个版本的咖喱函数.
这里是:
const L = a =>{const m = 列表 =>x =>！X?列表: m([...list, x]);返回 m([])(a);};const list1 = (L)(1)(2)(3);//懒惰:这里没有数据评估const list2 = (L)(4)(5)(6);console.log(list1())//现在由 tail () 评估console.log(list2()) 我真正喜欢的是惰性求值.
虽然给出的方法满足我提到的，但这个函数已经失去了外部结构或者我必须提到:
代数结构
const L = a =>升；哪个表单列表更根本地为我们提供了一个代数结构的身份元素，可能与 Monoid 或 Magma.>
左右身份
最简单的 Monoids 和恒等式示例之一是 JavaScript 中的数字和 "Strings" 和 [Array].
0 + a === a === a + 01 * a === a === a * 1在字符串中，空引号 "" 是标识元素.
"" + "Hello world" === "Hello world" === "Hello world" + ""同样适用于 [Array].
同样适用于 L:
(L)(a) === (a) === (a)(L)const L = a =>升；const a = L(5);//数字被包裹或提升"到类型:L//字符串和数组的相似性//"5" [5]//左身份控制台日志((L)(a) === (a)//真);//正确的身份控制台日志((a) === (a)(L)//真);以及明显的身份不变性:
const L = a =>升；控制台日志((L)(L) === (L)//真);控制台日志((L)(L)(L) === (L)//真);控制台日志((L)(L)(L)(L) === (L)//真);还有以下内容:
const L = a =>升；const a = (L)(1)(2)(3);const b = (L)(1)(L)(2)(3)(L);控制台日志((a) === (b)//真);问题
实现满足 3 个要求的 L 的最聪明或最优雅的方法是什么(非常实用且没有变化(也没有 Array.push)):
要求 0 - 身份
一个简单的函数:
const L = a =>升；已经满足我们已经看到的恒等律.
要求 1 - eval() 方法
虽然L满足恒等律，但是没有办法访问列出/累积的数据.
(我上一个问题的答案提供了数据积累能力，但违反了恒等律.)
懒惰评估似乎是正确的方法，因此提供更清晰的规范:
提供L
的eval方法const L = a =>升；//需要增强以满足要求const a = (L)(1)(2)(3);const b = (L)(1)(L)(2)(3)(L);控制台日志((a) === (b)//真);控制台日志((a).eval()//[1, 2, 3]);控制台日志((b).eval()//[1, 2, 3]);要求 3 - 幺半群结合律
除了突出的Identify结构，Monoids还满足结合律
(a * b) * c === a * b * c === a * (b * c)这只是意味着展平列表"，换句话说，该结构不包含嵌套列表.
[a, [b, c]] 不好.
示例:
const L = a =>升；//需要增强以满足要求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);控制台日志(abc1 === abc2//关联为真);控制台日志((ab).eval()//[1, 2, 3, 4]);控制台日志((abc1).eval()//[1, 2, 3, 4, 99]);控制台日志((abc2).eval()//[1, 2, 3, 4, 99]);这就是将 L 实现为幺半群的 3 个要求.
这对我来说是函数式编程的一大挑战，实际上我自己尝试了一段时间，但是问了之前的问题，分享我自己的挑战并听取人们的意见并阅读他们优雅的代码是非常好的做法.
谢谢.
你的数据类型不一致！
所以，你想创建一个幺半群.考虑幺半群的结构:
class Monoid m where空 :: m -- 标识元素(<*>)::m->米->m -- 二元运算-- 它满足以下法律:空 <*>x = x = x <*>空——恒等律(x <*> y) <*>z＝x<*>(y <*> z) -- 结合律现在，考虑您的数据类型的结构:
(L)(a) = (a) = (a)(L)//恒等式((a)(b))(c) = (a)((b)(c))//结合律因此，根据您的说法，标识元素是 L，二元运算是 功能应用.然而:
(L)(1)//这应该是一个有效的表达式.(L)(1) != (1) != (1)(L)//但它违反了恒等律.//(1)(L) 甚至不是一个有效的表达式.它抛出一个错误.所以:((L)(1))(L)//这应该是一个有效的表达式.((L)(1))(L) != (L)((1)(L))//但它违反了结合律.问题在于您将二元运算与反向列表构造函数混为一谈:
//首先，您使用函数应用程序作为反向缺点(又名 snoc)://缺点 :: a ->[a] ->[一种]//snoc :: [a] ->->[a] -- 参数翻转const xs = (L)(1)(2);//[1,2]const ys = (L)(3)(4);//[3,4]//稍后，您使用函数应用程序作为二元运算符(又名追加)://追加 :: [a] ->[a] ->[一种]const zs = (xs)(ys);//[1,2,3,4]如果您将函数应用程序用作 snoc，那么您也不能将其用于 append:
snoc :: [a] ->->[一种]追加:: [a] ->[a] ->[一种]请注意类型不匹配，但即使它们匹配，您仍然不希望一个操作做两件事.
您想要的是差异列表.
差异列表 是一个函数，它接受一个列表并在其前面添加另一个列表.例如:
const concat = xs =>ys =>xs.concat(ys);//这将创建一个差异列表.const f = concat([1,2,3]);//这是一个差异列表.console.log(f([]));//您可以通过将其应用于空数组来获取其值.console.log(f([4,5,6]));//您也可以将其应用于任何其他数组.差异列表很酷的一点是它们形成了一个幺半群，因为它们只是endofunctions:
const id = x =>X;//标识元素只是 id 函数.const compose = (f, g) =>x =>f(g(x));//二元运算是组合.compose(id, f) = f = compose(f, id);//恒等式撰写(撰写(f，g)，h)=撰写(f，撰写(g，h))；//结合律更好的是，您可以将它们打包成一个简洁的小类，其中函数组合是点运算符:
class DList {构造函数(f){this.f = f;this.id = 这个；}缺点(x){return new DList(ys => this.f([x].concat(ys)));}连接(xs){return new DList(ys => this.f(xs.concat(ys)));}申请(xs){返回 this.f(xs);}}const id = new DList(x => x);const cons = x =>new DList(ys => [x].concat(ys));//从值构造 DList.const concat = xs =>new DList(ys => xs.concat(ys));//从数组构造 DList.ID .concat([1, 2, 3]) = concat([1, 2, 3]) = concat([1, 2, 3]) .id//恒等式concat([1, 2]) .缺点(3) = 缺点(1) .concat([2, 3])//结合律您可以使用 apply 方法来检索 DList 的值，如下所示:
class DList {构造函数(f){this.f = f;this.id = 这个；}缺点(x){return new DList(ys => this.f([x].concat(ys)));}连接(xs){return new DList(ys => this.f(xs.concat(ys)));}申请(xs){返回 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]) .缺点(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 数组)相比，使用差异列表的一个优点是连接效率更高，因为列表是从右到左连接的.因此，如果您连接多个列表，它不会一遍又一遍地复制相同的值.
This is an advanced topic of my prior question here:
How to store data of a functional chain?
The brief idea is
A simple function below:
const L = a => L;
forms
L
L(1)
L(1)(2)
...
This seems to form a list but the actual data is not stored at all, so if it's required to store the data such as [1,2], what is the smartest practice to have the task done?
One of the prominent ideas is from @user633183 which I marked as an accepted answer(see the Question link), and another version of the curried function is also provided by @Matías Fidemraizer .
So here goes:
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())
What I really like is it turns out lazy evaluation.
Although the given approach satisfies what I mentioned, this function has lost the outer structure or I must mentiion:
Algebraic structure
const L = a => L;
which forms list and more fundamentally gives us an algebraic structure of identity element, potentially along with Monoid or Magma.
Left an Right identity
One of the easiest examples of Monoids and identity is number and "Strings" and [Array] in JavaScript.
0 + a === a === a + 0
1 * a === a === a * 1
In Strings, the empty quoate "" is the identity element.
"" + "Hello world" === "Hello world" === "Hello world" + ""
Same goes to [Array].
Same goes to 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
);
and the obvious identity immutability:
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
);
Also the below:
const L = a => L;
const a = (L)(1)(2)(3);
const b = (L)(1)(L)(2)(3)(L);
console.log(
(a) === (b) //true
);
Questions
What is the smartest or most elegant way (very functional and no mutations (no Array.push, also)) to implement L that satisfies 3 requirements:
Requirement 0 - Identity
A simple function:
const L = a => L;
already satisfies the identity law as we already have seen.
Requirement 1 - eval() method
Although L satisfies the identity law, there is no method to access to the listed/accumulated data.
(Answers provided in my previous question provide the data accumulation ability, but breaks the Identity law.)
Lazy evaluation seems the correct approach, so providing a clearer specification:
provide eval method of L
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]
);
Requirement 3 - Monoid Associative law
In addition to the prominent Identify structure, Monoids also satisfies Associative law
(a * b) * c === a * b * c === a * (b * c)
This simply means "flatten the list", in other words, the structure does not contain nested lists.
[a, [b, c]] is no good.
Sample:
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]
);
That is all for 3 requirements to implement L as a monoid.
This is a great challenge for functional programming to me, and actually I tried by myself for a while, but asking the previous questions, it's very good practice to share my own challenge and hear the people and read their elegant code.
Thank you.
Your data type is inconsistent!
So, you want to create a monoid. Consider the structure of a monoid:
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
Now, consider the structure of your data type:
(L)(a) = (a) = (a)(L) // identity law
((a)(b))(c) = (a)((b)(c)) // associativity law
Hence, according to you the identity element is L and the binary operation is function application. However:
(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.
The problem is that you are conflating the binary operation with the reverse list constructor:
// 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]
If you're using function application as snoc then you can't use it for append as well:
snoc :: [a] -> a -> [a]
append :: [a] -> [a] -> [a]
Notice that the types don't match, but even if they did you still don't want one operation to do two things.
What you want are difference lists.
A difference list is a function that takes a list and prepends another list to it. For example:
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.
The cool thing about difference lists are that they form a monoid because they are just 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
Even better, you can package them into a neat little class where function composition is the dot operator:
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
You can use the apply method to retrieve the value of the DList as follows:
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]
An advantage of using difference lists over regular lists (functional lists, not JavaScript arrays) is that concatenation is more efficient because the lists are concatenated from right to left. Hence, it doesn't copy the same values over and over again if you're concatenating multiple lists.
这篇关于如何存储 Monoidal List 函数链的数据?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
