链表似乎是数据结构中最简单，使用过程式语言实现链表的思路一般是：定义结点，通过指针把结点连接起来。然后在这链表上通过大量的指针操作实现插入、删除、定位等功能，甚至，在链表上添加一层抽象，把添加head、tail、len变量分别快速确定头结点、尾结点和链表长度。实践表面，这是一种高效的方法。但如果换个思路，实现链表就马上变得困难了—使用函数式，难点在于结点和结点的连接比常规思路困难多了。本文提供一种思路，基于lambda表达式和Python。

在函数式环境下，表示链表的方式如下：

1
l = Node(1, Node(2, Node(3, Node(4, Node(5, None)))))

上面表达式中，每个结点的第二个参数都是链表，因此，函数式链表可以抽象为：

1
l = Node(value, l)

那么，在具体的编程环境下，如何实现这种具有递归性质的结点（Node）？答案是通过lambda表达式：

1
2
3
def Node(current_value, next_value):
    return lambda is_current: current_value \
        if is_current else next_value

Node函数会保存当前结点的值和结点指向的链表的头结点，即next_value。例如：

1
l = Node(1, Node(2, Node(3, Node(4, Node(5, None)))))

根据Node函数返回的lambda表达式可以知道，根据不同的输入确定lambda返回当前结点值还是当前结点执行的链表的头结点。通过如下方式操作链表：

1
2
3
4
5
6
7
8
9
10
NEXT = False
CURRENT = True

l = Node(1, Node(2, Node(3, Node(4, Node(5, None)))))

l(NEXT) // 访问l的下一个结点，返回第1结点
l(NEXT)(CURRENT) // 访问l的下一个结点，返回第1结点的值

l(NEXT)(NEXT) // 访问l的下下一个结点，返回第2结点
l(NEXT)(NEXT)(CURRENT) // 访问l的下下一个结点，返回第2结点的值

在上面的基本操作上，添加链表的常见操作方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def next_value(l):
    print(l(CURRENT))
    return l(NEXT)

def print_list(l):
    while l:
        l = next_value(l)

def list_length(l):
    length = 0
    while l:
        l = l(NEXT)
        length += 1
    return length

def find_index(l, index):
    for _ in range(index):
        l = l(NEXT)
    return l(CURRENT)

如果往链表中插入结点，根据l=Node(value, l)的定义不能实现：

1
2
def add_to_head(l, value):
    return Node(value, l)

以上是我对函数式在链表的实现上的认识，待灵感一闪而更新。最后提一个问题—你能利用上述提供的函数式思路翻转链表吗？表吗？