LISP赐予我力量。

序

当时在学《SICP》的时候，突发奇想，看用Scheme(LISP方言的一种)来写C++寒假作业是什么效果。不出意料，实在是太好写了。有了函数式的“我手写我心”加成，短短几十行就把C++寒假作业给搞定了。

既然作业已经完成了，再重新用C++的命令式思路来做，显然太浪费精力和时间。于是萌生出了这么一个想法：何不尝试让C++去适应我的思路，让我写出函数式风格的C++作业呢？

要完成这个工作，首先要模仿LISP简单的结构和功能，本文就是用来解决这个问题。

基础结构

众所周知，LISP这个名字其实是来自于 “LISt Processor” —— “ list 处理器”。所谓的list，是如下的这么一个东西：

前一个盒子连着后一个盒子，第一个盒子有箭头指着，最后一个盒子什么都不指，用斜线填充。

用C++来表达这样的结构是很轻松的事情，每个盒子(Node)包含元素部分，类型为A(Arbitrary)，还有箭头部分，类型为std::shared_ptr<A> (注：std::shared_ptr可以使我们从内存管理的泥潭中抽身而出)。可以通过调用内部的head、tail函数来获取该元素，以及箭头。代码如下：

(*注：以下所有C++代码均采用C++14标准)

template <typename T>
class MyNode
{
public:
  MyNode(T a, std::shared_ptr<MyNode> b) : n(a), next(b){};
  T head() { return n; }
  std::shared_ptr<MyNode> tail() { return next; }
private:
  T n;
  std::shared_ptr<MyNode> next;
};

初步的结构有了，但请注意到，list是一种递归的结构，我取出某个list的tail(箭头)，它仍然是一个list，直到最后代表list完结的斜线。

所以，在这里我干脆把所有箭头都取相同的名字，叫做Mylist，给最后的斜线也取个名字，叫做EmptyList，规定EmptyList也是一个list。

template <typename T>
using MyList = std::shared_ptr<MyNode<T>>;
template <typename T>
MyList<T> EmptyList = nullptr;

基础函数

构造 LIST

上面说过，list是一种递归的结构，所以构造list的方法很简单：给定一个元素x，再一个list，就可以构造一个新的list。这个新list的head是x，tail是旧list，相当于旧list往最前面再长了一个盒子。

// * 构造List的基础函数
template <typename T>
MyList<T> Cons(T x, MyList<T> xs)
{
  return std::make_shared<MyNode<T>>(x, xs);
}
// auto list3 = Cons(3, EmptyList<int>); 
// => (3)
// auto list23 = Cons(2, list3); 
// => (2, 3)
// auto list123 = Cons(1, list23); 
// => (1, 2, 3)

每次都从斜线开始一个个盒子地构造list确实有点辛苦，所以我这里写了一个语法糖，让自己可以以轻松又易读的方式构造list：

// * 构造List的语法糖
template <typename T>
MyList<T> toList(const std::initializer_list<T> &il)
{
  MyList<T> res = EmptyList<T>;
  for (auto it = std::rbegin(il); it != std::rend(il); ++it)
    res = Cons(*it, res);
  return res;
}
// auto list123_ = Cons(1, Cons(2, Cons(3, EmtpyList<int>))); 
// => (1, 2, 3)
// auto list123__ = toList({1, 2, 3}); 
// => (1, 2, 3)

左右折叠函数

由于函数式语言里并没有常规命令式语言里面的循环语句，使得函数式语言的程序员们通常会采用递归式对list进行遍历操作。而遍历操作又如此地常见，于是有人抽象出了最常见的两种遍历方式，一种是fold left，一种是fold right。它们可以让程序员不必显式地写出递归式，只需要提供：

对 单个元素 和 已成功处理的结果 之间操作的函数。
初始结果。
待处理list。

便可以通过折叠(fold)函数将list折叠成期望的结构。

例如求和操作：

auto lst = toList({1, 2, 3});
auto a = FoldLeft([](int res, int x) { return x + res; }, 0, lst);
// a = 6
auto b = FoldRight([](int x, int res) { return x + res; }, 0, lst);
// b = 6

对于求和操作，fold left和fold right都能求出结果，但求值的方式是有所不同：他们的求值结构和顺序是不同的。这里不详细解释他们之间的不同之处，有兴趣可以查阅维基百科：https://en.wikipedia.org/wiki/Fold_(higher-order_function)

将左右折叠写成C++的形式：

// * 左右折叠函数
template <typename F, typename Z, typename T>
Z FoldRight(F fn, Z zero, MyList<T> xs)
{
  if (xs == EmptyList<T>)
    return zero;
  else
    return fn(xs->head(), FoldRight(fn, zero, xs->tail()));
}
template <typename F, typename Z, typename T>
Z FoldLeft(F fn, Z zero, MyList<T> xs)
{
  if (xs == EmptyList<T>)
    return zero;
  else
    return FoldLeft(fn, fn(zero, xs->head()), xs->tail());
}

可以看出他们实际上都是递归式。

翻转 list

由于上面已经实现了左右折叠函数，在这里可以直接现用了，因为翻转list也不过是个遍历操作。

// * 反转
template <typename T>
MyList<T> Reverse(MyList<T> xs)
{
  return FoldLeft([](MyList<T> xs, T x) -> MyList<T> { return Cons<T>(x, xs); } , 
                  EmptyList<T>, xs);
}

相信读者已经看出了函数式语句是何等的简洁了，我上面所实现的函数全都不过寥寥几行，却已经完整表达了我所期望的操作。

list 长度

不出意外，一样是可以通过fold解决。

// * Length
template <typename T>
size_t Length(MyList<T> xs)
{
  return FoldLeft( [](size_t x, T rest) { return (x + 1); },
                   0, xs);
}

Map 函数

这里的Map和hash table所表达的Map含义不同。这里只是指：提供一个将list元素映射到另外一个元素的函数，通过遍历list的每个元素，将原有的list映射到另外一个相同长度的list。

fold函数再次出场：

// * Map
template <typename T, typename F>
MyList<T> PoorMap(F fn, MyList<T> xs)
{
  return FoldRight([&fn](T x, MyList<T> xs) -> MyList<T> { return Cons<T>(fn(x), xs); },
                   EmptyList<T>, xs);
}

这里需要解释的是，真正的Map函数是可以将一种类型映射到另外一种类型的，这里只能是相同类型之间的映射，所以我称为PoorMap。原因是，以我的能力，要写可以映射到另外一种类型的Map，用户代码将变得丑陋。不得已，我牺牲了功能完备性，保留了简洁性。用户代码若需要映射到另外一种类型时，我将临时使用for循环代替。

过滤器函数

提供一个判断条件，和一个list，可以将不符合条件的元素去除。

fold之舞：

// * Filter
template <typename F, typename T>
MyList<T> Filter(F fn, MyList<T> xs)
{
  return FoldRight([&fn](T x, MyList<T> xs) -> MyList<T> { return (fn(x) ? Cons<T>(x, xs) : xs); },
                   EmptyList<T>, xs);
}

其他函数

取list前n个元素，构成新list

// * list-head
template <typename T>
MyList<T> ListHead(MyList<T> xs, size_t n)
{
  return ( n == 0 ) ? EmptyList<T> : Cons(xs->head(), ListHead(xs->tail(), n - 1)) ;
}

丢弃list前n个元素，构成新list

// * list-tail
template <typename T>
MyList<T> ListTail(MyList<T> xs, size_t n)
{
  return ( n == 0 ) ? xs : ListTail(xs->tail(), n - 1) ;
}

list 里是否存在符合条件的元素

// * any
template <typename F, typename T>
bool Any(F pred, MyList<T> lst)
{
  return FoldLeft( [&pred](bool x, T rest) { return pred(rest) || x; }, 
                   false, lst);
}

基础结构和功能已经构造完毕，下面将用来……完成作业。
完整代码：https://github.com/zhongzc/C-/blob/master/mylist.h