引言咱们从一个链表的构造函数开始，“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)))"失去的后果。
要求：
你须要应用递归来实现，而不是任何显式的for/while循环；你不能在你的实现中应用先前已定义好的”listToString“、”myMap“和”myReduce“办法；你不能批改原始链表。要查看你的实现的正确性，能够验证：
”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“。
对实现的根本要求：
你不能在你的实现中应用先前已定义好的”listToString“、”myMap“和”myReduce“办法；你不能批改任何函数的输入输出特色，包含”myReduceRight“的输入输出特色；你不能在借在”myReduceRight“中投机取巧来助力实现”myMap2“，例如向”myReduceRight“传递暗藏标记以示意非凡解决；你不能应用任何语言原生的非凡数据结构（举例，C++中的”std::vector"，Java中的“ArrayList”，Python中的“list”）。如果你的实现满足以下尽可能多的要求，你将取得“加分”：
不要应用任何显式的递归调用。特地地，防止在实现中申明调用“myMap2”；不要在实现中应用任何显式的for/while循环。为此你须要探索下“myReduceRight”的奇妙用法；不要批改原始链表。以下是你能够遵循的几个方向：
列表翻转；在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.function cons(head, tail) { return { head: head, tail: tail, };}function listToString(list) { if (!list) { return ''; } if (!list.tail) { return list.head.toString(); } return list.head.toString() + ' ' + listToString(list.tail);}function myMap(fn, list) { if (!list) { return undefined; } return cons(fn(list.head), myMap(fn, list.tail));}function myReduce(fn, accm, list) { if (!list) { return accm; } return myReduce(fn, fn(accm, list.head), list.tail);}function myReduceRight(fn, accm, list) { // [BEGIN] YOUR CODE HERE return undefined; // [END] YOUR CODE HERE}function myMap2(fn, list) { // [BEGIN] YOUR CODE HERE return undefined; // [END] YOUR CODE HERE}function main() { let exampleList = cons(1, cons(2, cons(3, cons(4)))); let plusOne = (x) => x + 1; let xTimesTwoPlusY = (x, y) => x * 2 + y; let printXAndReturnY = (x, y) => { console.log(x); return y; }; let unfoldCalculation = (x, y) => 'fn(' + x + ', ' + y + ')'; let printAndReturn = 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, exampleList);}main();Python代码模板：# Refer to README for detailed instructions.from __future__ import print_functionclass LinkedList: def __init__(self, head, tail): self.head = head self.tail = taildef cons(head, tail=None): return LinkedList(head, tail)def listToString(list): if list is None: return "" if list.tail is None: return str(list.head) return str(list.head) + " " + listToString(list.tail)def myMap(fn, list): if list is None: return None return cons(fn(list.head), myMap(fn, list.tail))def myReduce(fn, accm, list): if list is None: return accm return myReduce(fn, fn(accm, list.head), list.tail)def myReduceRight(fn, accm, list): # [BEGIN] YOUR CODE HERE return None # [END] YOUR CODE HEREdef myMap2(fn, list): # [BEGIN] YOUR CODE HERE return None # [END] YOUR CODE HEREdef main(): exampleList = cons(1, cons(2, cons(3, cons(4)))) plusOne = lambda x: x + 1 xTimesTwoPlusY = lambda x, y: x * 2 + y def printXAndReturnY(x, y): print(x) return y def unfoldCalculation(x, y): return "fn(%s, %s)" % (str(x), str(y)) printAndReturn = print print(listToString(exampleList), "should be 1 2 3 4") print(listToString(myMap(plusOne, exampleList)), "should be 2 3 4 5") print(myReduce(xTimesTwoPlusY, 0, exampleList), "should be 26") print(myReduce(unfoldCalculation, "accm", exampleList), "should be fn(fn(fn(fn(accm, 1), 2), 3), 4)") print(myReduceRight(xTimesTwoPlusY, 0, exampleList), "should be 20") print(myReduceRight(unfoldCalculation, "accm", exampleList), "should be fn(1, fn(2, fn(3, fn(4, accm))))") print("Below should output 4 3 2 1 each on a separate line:"); myReduceRight(printXAndReturnY, 0, exampleList) print(listToString(myMap2(plusOne, exampleList)), "should be 2 3 4 5") print("The two outputs below should be equal:") print("First output:") myMap(printAndReturn, exampleList) print("Second output:") myMap2(printAndReturn, exampleList)if __name__ == "__main__": main()最终实现：JavaScript实现：// Refer to README for detailed instructions.function cons(head, tail) { return { head: head, tail: tail, };}function listToString(list) { if (!list) { return ''; } if (!list.tail) { return list.head.toString(); } return list.head.toString() + ' ' + listToString(list.tail);}function myMap(fn, list) { if (!list) { return undefined; } return cons(fn(list.head), myMap(fn, list.tail));}function myReduce(fn, accm, list) { if (!list) { return accm; } return myReduce(fn, fn(accm, list.head), list.tail);}function myReduceRight(fn, accm, list) { // [BEGIN] YOUR CODE HERE if (!list) { return accm; } // State-of-the-art trampoline trick to prevent recursion stack overflow const trampoline = (fun) => { return function trampolined(...args) { var result = fun(...args); while (typeof result == 'function') { result = result(); } return result; }; }; const reverseOperation = (origList) => { const reverseCons = (cons, acc = []) => { if (!cons) { return undefined; } acc.push(cons.head); if (cons.tail instanceof Object) { return reverseCons(cons.tail, acc); } else { return acc.reverse(); } }; const recursCons = (jsList = []) => { if (jsList.length <= 0) { return undefined; } else { return { head: jsList[0], tail: recursCons(jsList.slice(1)), }; } }; // IMMUTABLE const newList = Object.assign({}, origList); // Get the reversed version of Linklist in another plain representation const reversedJSList = trampoline(reverseCons)(newList, []); // Back assign the reversed plain representation to Linklist const reversedLinkList = trampoline(recursCons)(reversedJSList); return reversedLinkList; }; const innerReducer = (fn_, accm_, list_) => { if (!list_) { return accm_; } return innerReducer(fn_, fn_(list_.head, accm_), list_.tail); }; return trampoline(innerReducer)(fn, accm, reverseOperation(list)); // [END] YOUR CODE HERE}function myMap2(fn, list) { // [BEGIN] YOUR CODE HERE // State-of-the-art trampoline trick to prevent recursion stack overflow const trampoline = (fun) => { return function trampolined(...args) { var result = fun(...args); while (typeof result == 'function') { result = result(); } return result; }; }; const polishedFn = (cur, acc) => { let newAcc = {}; newAcc.tail = Object.keys(acc).length > 0 ? acc : undefined; newAcc.head = () => fn(cur); // delay to keep the map order return newAcc; }; let newList = Object.assign(list); const storeList = myReduceRight(polishedFn, {}, newList); const activateStore = (store) => { if (!store) return undefined; store.head = store.head instanceof Function ? store.head() : store.head; store.tail = activateStore(store.tail); return store; }; return trampoline(activateStore)(storeList); // [END] YOUR CODE HERE}function main() { let exampleList = cons(1, cons(2, cons(3, cons(4)))); let plusOne = (x) => x + 1; let xTimesTwoPlusY = (x, y) => x * 2 + y; let printXAndReturnY = (x, y) => { console.log(x); return y; }; let unfoldCalculation = (x, y) => 'fn(' + x + ', ' + y + ')'; let printAndReturn = 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, exampleList);}main();窍门：应用蹦床函数trampoline优化递归调用。打印后果：'1 2 3 4' 'should be 1 2 3 4''2 3 4 5' 'should be 2 3 4 5'26 'should be 26''fn(fn(fn(fn(accm, 1), 2), 3), 4)' 'should be fn(fn(fn(fn(accm, 1), 2), 3), 4)'20 'should be 20''fn(1, fn(2, fn(3, fn(4, accm))))' 'should be fn(1, fn(2, fn(3, fn(4, accm))))''Below should output 4 3 2 1 each on a separate line:'4321'2 3 4 5' 'should be 2 3 4 5''The two outputs below should be equal:''First output:'1234'Second output:'1234Python实现：# Refer to README for detailed instructions.from __future__ import print_functionimport copyimport typesclass LinkedList: def __init__(self, head, tail): self.head = head self.tail = taildef cons(head, tail=None): return LinkedList(head, tail)def listToString(list): if list is None: return "" if list.tail is None: return str(list.head) return str(list.head) + " " + listToString(list.tail)def myMap(fn, list): if list is None: return None return cons(fn(list.head), myMap(fn, list.tail))def myReduce(fn, accm, list): if list is None: return accm return myReduce(fn, fn(accm, list.head), list.tail)def myReduceRight(fn, accm, list): # [BEGIN] YOUR CODE HERE if list is None: return accm def reverseOperation(origList): # Get the reversed version of Linklist in another plain representation def reverseCons(cons, acc = []): if cons is None: return None acc.append(cons.head) if cons.tail != None: return reverseCons(cons.tail, acc) else: return acc[::-1] # Back assign the reversed plain representation to Linklist def recursCons(pyList = []): if len(pyList) <= 0: return None else: return cons(pyList[0], recursCons(pyList[1:])) newList = copy.deepcopy(origList) reversedPyList = reverseCons(newList, []); reversedLinkList = recursCons(reversedPyList); return reversedLinkList def innerReducer(fn_, accm_, list_): if list_ is None: return accm_ return innerReducer(fn_, fn_(list_.head, accm_), list_.tail) return innerReducer(fn, accm, reverseOperation(list)); # [END] YOUR CODE HEREdef myMap2(fn, list): # [BEGIN] YOUR CODE HERE def polishedFn(cur, acc): newAcc = cons(None) newAcc.tail = acc if isinstance(acc, LinkedList) else None newAcc.head = lambda: fn(cur) # delay to keep the map order return newAcc newList = copy.deepcopy(list) storeList = myReduceRight(polishedFn, {}, newList); def activateStore(store): if store is None: return None store.head = store.head() if isinstance(store.head, types.FunctionType) else store.head store.tail = activateStore(store.tail) return store return activateStore(storeList) # [END] YOUR CODE HEREdef main(): exampleList = cons(1, cons(2, cons(3, cons(4)))) plusOne = lambda x: x + 1 xTimesTwoPlusY = lambda x, y: x * 2 + y def printXAndReturnY(x, y): print(x) return y def unfoldCalculation(x, y): return "fn(%s, %s)" % (str(x), str(y)) printAndReturn = print print(listToString(exampleList), "should be 1 2 3 4") print(listToString(myMap(plusOne, exampleList)), "should be 2 3 4 5") print(myReduce(xTimesTwoPlusY, 0, exampleList), "should be 26") print(myReduce(unfoldCalculation, "accm", exampleList), "should be fn(fn(fn(fn(accm, 1), 2), 3), 4)") print(myReduceRight(xTimesTwoPlusY, 0, exampleList), "should be 20") print(myReduceRight(unfoldCalculation, "accm", exampleList), "should be fn(1, fn(2, fn(3, fn(4, accm))))") print("Below should output 4 3 2 1 each on a separate line:"); myReduceRight(printXAndReturnY, 0, exampleList) print(listToString(myMap2(plusOne, exampleList)), "should be 2 3 4 5") print("The two outputs below should be equal:") print("First output:") myMap(printAndReturn, exampleList) print("Second output:") myMap2(printAndReturn, exampleList)if __name__ == "__main__": main()备注：Python的trampoline蹦床函数实现有些简单，间接递归解决了。可参考文章Tail recursion in Python, part 1: trampolines)。打印后果：1 2 3 4 should be 1 2 3 42 3 4 5 should be 2 3 4 526 should be 26fn(fn(fn(fn(accm, 1), 2), 3), 4) should be fn(fn(fn(fn(accm, 1), 2), 3), 4)20 should be 20fn(1, fn(2, fn(3, fn(4, accm)))) should be fn(1, fn(2, fn(3, fn(4, accm))))Below should output 4 3 2 1 each on a separate line:43212 3 4 5 should be 2 3 4 5The two outputs below should be equal:First output:1234Second output:1234
...