SCHeng

It all returns to nothing.

emacs, python, scheme

SICP回顾:cons函数、使用过程定义数据结构(下)

scheng

接着写上一篇的内容,我打算实现三个基本函数conscarcdr,尝试了几种方法都没能很好的实现,并且前两种方法在后来的测试中发现都有问题(第二种方法在嵌套使用的时候仍然有bug)。我逛了一圈github,发现有一位老哥已经用python实现了SICP的大部分习题,https://github.com/Reo-LEI/SICP-Python 。其中他编写了一个ordered.py,其中对cons的实现和对lister(在scheme里面是list)的实现是比较优雅的。

我将他的代码稍稍修改了一下,现在的构造是这样的:

def is_null(item):
    return item is None

def cons(a, b):
    return (a, b)

def car(x):
    return x[0]

def cdr(x):
    return x[1]

def lister(*args):
    def coner(x, y):
        if y == []:
            return cons(x, None)
        else:
            return cons(x, coner(y[0], y[1:]))
    L = list(args)
    first, other = L[0], L[1:]
    return coner(first, other)

其实就是在我的第二次尝试的代码里面使用cons重新写了一个lister数据结构,使cons能够正确处理嵌套结构。

一个lister接受多个参数(*args使函数能够接收若干个参数)。将args转换为list作为temp保存,tuple()无法接受多个参数。
first取第一个(类似car),other取剩余的(类似cdr),使用内部函数对first与other继续递归构造。而coner函数就是将这个list(或者说是other参数)展开,逐个地将元素用cons链接起来,到list被分解完毕了,就返回一个None作为递归的结束(这就类似scheme里的'() 或者 nil了)。

这个数据结构能够很好的处理嵌套的lister和cons,是我上一次构造的时候没想到的,我认为是一个较为优雅的方法了,唯一不足的就是对一个lister的直接呈现效果仍然是这样(1, (2, (3, None))),而不是(1, 2, 3)这样的。不过问题不大。

因为对重新构造了list的数据结构,那基于list的一些操作函数也会发生变化,python自带的map函数已经无法处理这里的lister了,所以就重新构造了一个mappingmapping_n函数来作为新的map函数。

def is_null(item):
    return item is None

def mapping(func, item): 
    if is_null(item):
        return None
    else:
        return cons(func(car(item)), mapping(func, cdr(item)))

def mapping_n(func, *seqs):
    # 将序列转化为元组
    def seq_trans(seq):
        def translator(s):
            if is_null(cdr(s)):
                return [car(s)]
            else:
                return [car(s)]+translator(cdr(s))
        return tuple(translator(seq))

    def _map(f, seq):
        if is_null(car(seq)):
            return None
        else:
            return cons(f(*seq_trans(car_n(seq))), _map(f, cdr_n(seq)))  # 用*解包元组调用f

        # 判断seqs为树或者多个列表并解包
    if len(seqs) > 1:
        seqs = lister(*seqs)
    # 若为树直接解包
    else:

        seqs = seqs[0]
    return _map(func, seqs)

mapping(func, item),类似原map函数,mapping的第一个参数接受一个函数,第二个参数接受一种数据或者一种数据结构。

使用cons将item重新链接,并用car、cdr进行分解,对car(item)执行func操作,cdr(item)取剩下的数据部分,传入mapping进行递归。

mapping_n是P70脚注78提到的map扩充函数,能够接受多个表作/序列作为参数,依次取各个序列第k元素组成序列seq(k)作为func的参数,返回结果序列。

这是我修改后的文件,我希望后续能将它变成一个python抽象scheme的标准函数库。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注