关于javascript:算法思维体操用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.

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