Python中的函数式链表

链表结构

Nil = None

def cons(x, xs=Nil):
    return (x, xs)

assert cons(0) == (0, Nil)
assert cons(0, (1, (2, Nil))) == (0, (1, (2, Nil)))
def lst(*xs):
    if not xs:
        return Nil
    else:
        return cons(xs[0], lst(*xs[1:]))

assert lst() == Nil
assert lst(1) == (1, Nil)
assert lst(1, 2, 3, 4) == (1, (2, (3, (4, Nil))))

基础操作

  • head 返回列表的第一个元素
  • tail 返回一个除了第一个元素的其它所有元素的列表
def head(xs):
    return xs[0]

assert head(lst(1, 2, 3)) == 1
def tail(xs):
    return xs[1]

assert tail(lst(1, 2, 3, 4)) == lst(2, 3, 4)

长度和连接

def length(xs):
    if is_empty(xs):
        return 0
    else:
        return 1 + length(tail(xs))

assert length(lst(1, 2, 3, 4)) == 4
assert length(Nil) == 0
def concat(xs, ys):
    if is_empty(xs):
        return ys
    else:
        return cons(head(xs), concat(tail(xs), ys))

assert concat(lst(1, 2), lst(3, 4)) == lst(1, 2, 3, 4)

Last, init, and list reversal

def last(xs):
    if is_empty(tail(xs)):
        return head(xs)
    else:
        return last(tail(xs))

assert last(lst(1, 3, 3, 4)) == 4
def init(xs):
    if is_empty(tail(tail(xs))):
        return cons(head(xs))
    else:
        return cons(head(xs), init(tail(xs)))

assert init(lst(1, 2, 3, 4)) == lst(1, 2, 3)
def reverse(xs):
    if is_empty(xs):
        return xs
    else:
        return append(reverse(tail(xs)), cons(head(xs), Nil))

assert reverse(Nil) == Nil
assert reverse(cons(0, Nil)) == (0, Nil)
assert reverse(lst(1, 2, 3, 4)) == lst(4, 3, 2, 1)
assert reverse(reverse(lst(1, 2, 3, 4))) == lst(1, 2, 3, 4)

Prefixes and suffixes

def take(n, xs):
    if n == 0:
        return Nil
    else:
        return cons(head(xs), take(n-1, tail(xs)))

assert take(2, lst(1, 2, 3, 4)) == lst(1, 2)
def drop(n, xs):
    if n == 0:
        return xs
    else:
        return drop(n-1, tail(xs))

assert drop(1, lst(1, 2, 3)) == lst(2, 3)
assert drop(2, lst(1, 2, 3, 4)) == lst(3, 4)

Element selection

def apply(i, xs):
    return head(drop(i, xs))

assert apply(0, lst(1, 2, 3, 4)) == 1
assert apply(2, lst(1, 2, 3, 4)) == 3

More complex examples

def insert(x, xs):
    if is_empty(xs) or x <= head(xs):
        return cons(x, xs)
    else:
        return cons(head(xs), insert(x, tail(xs)))

assert insert(0, lst(1, 2, 3, 4)) == lst(0, 1, 2, 3, 4)
assert insert(99, lst(1, 2, 3, 4)) == lst(1, 2, 3, 4, 99)
assert insert(3, lst(1, 2, 4)) == lst(1, 2, 3, 4)

def isort(xs):
    if is_empty(xs):
        return xs
    else:
        return insert(head(xs), isort(tail(xs)))

assert isort(lst(1, 2, 3, 4)) == lst(1, 2, 3, 4)
assert isort(lst(3, 1, 2, 4)) == lst(1, 2, 3, 4)
def to_string(xs, prefix="[", sep=", ", postfix="]"):
    def _to_string(xs):
        if is_empty(xs):
            return ""
        elif is_empty(tail(xs)):
            return str(head(xs))
        else:
            return str(head(xs)) + sep + _to_string(tail(xs))
    return prefix + _to_string(xs) + postfix

assert to_string(lst(1, 2, 3, 4)) == "[1, 2, 3, 4]"