编写单链表反转的程序

首先，我们定义一个链表。

struct list {
    int value;
    struct list * next;
};

C 语言也要面向对象编程，于是，编写构造函数。

struct list * makeList(int value, struct list * next){
    struct list * this = (struct list*)malloc(sizeof(struct list));
    this->value = value;
    this->next = next;
}

编写反转程序。

struct list * reverse(struct list * L) {
    struct list * result = NULL;
    for(struct list * i = L; i != NULL; i = i->next){
        result = makeList(i->value, result);
    }
    return result;
}

OK，让我们测试一下。

void printList(struct list * L)
{
    printf("(");
    int n = 0;
    for(struct list * i = L; i != NULL; i = i->next, ++n){
        if(n != 0){  printf(","); };
        printf("%d", i->value);
    }
    printf(")");
    return;
}
int main(int argc, char *argv[])
{
    struct list * a = makeList(1, NULL);
    a = makeList(2, a);
    a = makeList(3, a);
    printf("before reverse:");
    printList(a);
    printf("\nafter reverse:");
    printList(reverse(a));
    printf("\n");

    printf("before reverse:");
    printList(NULL);
    printf("\nafter reverse:");
    printList(reverse(NULL));
    printf("\n");
    return 0;
}

程序输出

before reverse:(3,2,1)
after reverse:(1,2,3)
before reverse:()
after reverse:()

这个程序的风格是 imperative 的，如果使用函数式编程，我们得换一个语言 Java 。

    public static class List<T> {
        private final T value;
        private final List<T> next;

        public List(T value, List next) {
            this.value = value;
            this.next = next;
        }

        @Override
        public String toString() {
            int n = 0;
            StringBuilder sb = new StringBuilder();
            sb.append("(");
            for(List i = this; i!=null; i = i.next, n ++){
                if(n!=0) {
                    sb.append(",");
                }
                sb.append(i.value);
            }
            sb.append(")");
            return sb.toString();
        }
    }

构造函数

    public static <T> List<T> cons(T value, List<T> next) {
        return new List(value, next);
    }

著名的 foldl 函数，一切一次遍历循环的抽象。

    public static <T,R> R foldl(BiFunction<T,R,R> f, R r, List<T> l){
        if(l == null){
            return r;
        }else{
            return foldl(f, f.apply(l.value, r), (List<T>)l.next);
        }
    }

可惜 java 不支持 TCO (Tail Call Optimization) ，这种写法会爆栈的。于是，用命令式的编程风格再写一次。

    public static <T,R> R foldl(BiFunction<T,R,R> f, R init, List<T> l){
        R result = init;
        for(List<T> i = l; i!=null; i = i.next){
            result = f.apply(i.value, result);
        }
        return result;
    }

反转列表的函数

    static <T> List<T> reverse(List<T> l) {
        return foldl(ListTest::cons, null, l);
    }

测试代码

    @Test
    public void main() throws Exception {
        List a = new List(1, null);
        a = new List(2, a);
        a = new List(3, a);

        System.out.println("before reverse: " + a);

        List b = reverse(a);
        System.out.println("after reverse: " + b);
    }

输出结果

before reverse: (3,2,1)
after reverse: (1,2,3)

foldl 可以抽象很多一次遍历的循环，例如，max 可以如下

    static <T extends Comparable<? super T>> T max(List<T> l){
        if(l == null) return null;
        return foldl((r1,r2) -> Comparator.<T>naturalOrder().compare(r1,r2) > 0?r1:r2,l.value, l);
    }

在函数式编程中，reverse-foldl 是一个俗语。例如 map 可以写成下面的形式。

    static <T,R> List<R> map(Function<T,R> f, List<T> l) {
        return reverse(foldl((r,n) -> cons(f.apply(r),n), null,l));
    }

测试代码

    @Test
    public void main2() throws Exception {
        List<Integer> a = new List(1, null);
        a = new List(2, a);
        a = new List(3, a);
        System.out.println("map: " + map(v-> v + 100, a));
    }

输出结果

map: (103,102,101)