算法思维体操：用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代码模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// 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代码模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
# 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实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
// 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
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
'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实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
# 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
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

扫一扫，分享到微信

微信分享二维码