共计 11998 个字符,预计需要花费 30 分钟才能阅读完成。
引言
咱们从一个链表的构造函数开始,“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_function
class LinkedList:
def __init__(self, head, tail):
self.head = head
self.tail = tail
def 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 HERE
def myMap2(fn, list):
# [BEGIN] YOUR CODE HERE
return None
# [END] YOUR CODE HERE
def 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:'
4
3
2
1
'2 3 4 5' 'should be 2 3 4 5'
'The two outputs below should be equal:'
'First output:'
1
2
3
4
'Second output:'
1
2
3
4
Python 实现:
# Refer to README for detailed instructions.
from __future__ import print_function
import copy
import types
class LinkedList:
def __init__(self, head, tail):
self.head = head
self.tail = tail
def 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 HERE
def 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 HERE
def 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 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:
4
3
2
1
2 3 4 5 should be 2 3 4 5
The two outputs below should be equal:
First output:
1
2
3
4
Second output:
1
2
3
4