>>> ORIGIN全文地址:算法思维体操：用JavaScript和Python自己实现reduceRight和map（链表）

推荐：编程鼠标·电竞鼠标

引言

我们从一个链表的构造函数开始，“cons”，它接收一个必要参数“head”及一个可选参数“tail”（相对于支持这样的实现的语言来说）。该构造函数返回一个链表的表示结构体，其中第一个元素为“head”，其余的元素被包裹在“tail“链表中。空链表的话用JavaScript中的undefined或Python中的None来表示。

举例来说，直到微小变化，”cons(1, cons(2, cons(3, cons(4))))"构造了一个含有4个元素的链表，”1 2 3 4“。

为了便于检查链表中的内容，我们定义了”listToString“方法来将链表转换为相应的字符串，其中链表元素之间用空格隔开。

”myMap“方法接收一个一元函数”fn“和一个链表”list“。它循序遍历链表中的每一个元素，并返回一个各元素都被”fn“转化过了的链表。

”myReduce"方法会对输入的链表从头到尾使用一个reducer函数“fn”，然后返回最终结果。比如，假设链表为“cons(1, cons(2, cons(3,)))”，“myReduce(fn, accm, list)”应该返回执行“fn(fn(fn(accm, 1), 2), 3)”得到的结果。

上述的三个方法都是使用递归实现的，巧妙运用了链表的递归结构。

第1部分：实现“myReduceRight"

请实现“myReduceRight”方法。其类似于“myReduce”，不同之处在于它是从尾到头对输入的链表使用reducer函数“fn”的。比如，假设链表为“cons(1, cons(2, cons(3)))"，”myReduceRight(fn, accm, list)"应该返回执行“fn(1, fn(2, fn(3, accm)))"得到的结果。

要求：

1. 你需要使用递归来实现，而不是任何显式的for/while循环；
2. 你不能在你的实现中使用先前已定义好的”listToString“、”myMap“和”myReduce“方法；
3. 你不能修改原始链表。

要检查你的实现的正确性，可以验证：

• ”myReduceRight(xTimesTwoPlusY, 0, exampleList)“应该得到“20”；
• “myReduceRight(unfoldCalculation, accm, exampleList)“应该表示为”fn(1, fn(2, fn(3, fn(4, accm))))”；
• “myReduceRight(printXAndReturnY, 0, exampleList)"应该按照输入链表的逆序来打印内容。

第2部分：实现”myMap2“

请基于“myReduceRight"方法实现”myMap2“，其应该在功能性上同质于”myMap“。

对实现的基本要求：

1. 你不能在你的实现中使用先前已定义好的”listToString“、”myMap“和”myReduce“方法；
2. 你不能修改任何函数的输入输出特征，包括”myReduceRight“的输入输出特征；
3. 你不能在借在”myReduceRight“中投机取巧来助力实现”myMap2“，例如向”myReduceRight“传递隐藏标志以表示特殊处理；
4. 你不能使用任何语言原生的特殊数据结构（举例，C++中的”std::vector"，Java中的“ArrayList”，Python中的“list”）。

如果你的实现满足以下尽可能多的要求，你将获得“加分”：

1. 不要使用任何显式的递归调用。特别地，避免在实现中声明调用“myMap2”；
2. 不要在实现中使用任何显式的for/while循环。为此你需要探究下“myReduceRight”的巧妙用法；
3. 不要修改原始链表。

以下是你可以遵循的几个方向：

• 列表翻转；
• 在reducer方法中修改链表；
• 巧妙地使用闭包和lambda函数来调整代码执行顺序。特别地，考虑考虑延时执行，如(() -> doSomething)()。

要检查你的实现的正确性，可以验证：

• “listToString(myMap2(plusOne, exampleList))”应该得到“2 3 4 5”；
• “myMap2(printAndReturn, exampleList)”应该按照正确的次序打印链表内容（“1 2 3 4”分别各占据一行而不是“4 3 2 1”）。

JavaScript代码模板：

// Refer to README for detailed instructions.functioncons(head,tail){return{head:head,tail:tail,};}functionlistToString(list){if(!list){return'';}if(!list.tail){returnlist.head.toString();}returnlist.head.toString()+' '+listToString(list.tail);}functionmyMap(fn,list){if(!list){returnundefined;}returncons(fn(list.head),myMap(fn,list.tail));}functionmyReduce(fn,accm,list){if(!list){returnaccm;}returnmyReduce(fn,fn(accm,list.head),list.tail);}functionmyReduceRight(fn,accm,list){// [BEGIN] YOUR CODE HEREreturnundefined;// [END] YOUR CODE HERE}functionmyMap2(fn,list){// [BEGIN] YOUR CODE HEREreturnundefined;// [END] YOUR CODE HERE}functionmain(){letexampleList=cons(1,cons(2,cons(3,cons(4))));letplusOne=(x)=>x+1;letxTimesTwoPlusY=(x,y)=>x*2+y;letprintXAndReturnY=(x,y)=>{console.log(x);returny;};letunfoldCalculation=(x,y)=>'fn('+x+', '+y+')';letprintAndReturn=console.log;console.log(listToString(exampleList),'should be 1 2 3 4');console.log(listToString(myMap(plusOne,exampleList)),'should be 2 3 4 5');console.log(myReduce(xTimesTwoPlusY,0,exampleList),'should be 26');console.log(myReduce(unfoldCalculation,'accm',exampleList),'should be fn(fn(fn(fn(accm, 1), 2), 3), 4)');console.log(myReduceRight(xTimesTwoPlusY,0,exampleList),'should be 20');console.log(myReduceRight(unfoldCalculation,'accm',exampleList),'should be fn(1, fn(2, fn(3, fn(4, accm))))');console.log('Below should output 4 3 2 1 each on a separate line:');myReduceRight(printXAndReturnY,0,exampleList);console.log(listToString(myMap2(plusOne,exampleList)),'should be 2 3 4 5');console.log('The two outputs below should be equal:');console.log('First output:');myMap(printAndReturn,exampleList);console.log('Second output:');myMap2(printAndReturn