SCHeng

It all returns to nothing.

python, scheme, sicp,

树的映射以及map函数

scheng

这篇文章是sicp2.2节内容的笔记,主要记录一下里面提到的scale-tree这个函数。

“`(scale-tree tree factor)“`以一棵树和一个因子作为参数,将树上的所有节点的值都乘上因子。

首先提供了一个朴素版本的scale-tree,就是递归左右子树,检查当前节点是否属于叶子节点。如果是,那么就乘上因子;如果不是,那么就继续左右递归。

(define (scale-tree tree factor)
  (cond ((null? tree) '())
    ((not (pair? tree)) (* tree factor))
    (else (cons (scale-tree (car tree) factor)
            (scale-tree (cdr tree) factor)))))

(define tree1 (list 1 (list 2 (list 3 4) 5) (list 5 7)))

(scale-tree  tree1 10)

会使原来的树(也就是tree1)的节点上的值都乘以10。

下面又提供了一个map加lambda匿名函数的版本,但是比较抽象,一下子难以理解。

(define (scale-tree1 tree factor)
  (map (lambda (sub-tree)
     (if (pair? sub-tree)
         (scale-tree sub-tree factor)
         (* sub-tree factor)))
       tree))

我使用python重新写了一次,加深理解。

def scale_tree(tree, factor):
    return tuple(map(lambda sub_tree : scale_tree(sub_tree, factor) if type(sub_tree) == tuple else sub_tree * factor,tree))

def scale_tree2(tree, factor):
    def iter(subtree):
        if type(subtree) == tuple:
            return scale_tree2(subtree, factor)
        return subtree * factor
    return tuple(map(iter, tree))

t = ((1, 2), 3, 4)

这里定义的两个函数功能上是一样的,因为scale_tree同时用map、lambda可读性可能不是很高,于是就用高阶函数的方法重新构造了scale_tree2这个函数。

首先要讲的是map函数,通常使用的map函数的参数列表应该是这样的:

map(function, parameter)

第一个参数接受一个函数,第二个接受一个值或者某种数据结构(也可以传入更多个)。然后将对后面的这个参数使用function。比如说下面这个最简单的例子:

def square(x):
    return x * x

print(list(map(square, [1, 2, 3])))

map会对列表中的每一个数都执行一次square,最后会返回一个[1,4,9]。不过这只是对于一层的列表来执行的。通过更高阶的函数配合可以进行更深层的操作,也就是scale-tree,对树的映射。

def iter(subtree):
        if type(subtree) == tuple:
            return scale_tree2(subtree, factor)
        return subtree * factor

这个iter函数接受的参数是一棵子树,我这里用python的元组来表示scheme中的list,如果当前位置的元素不是元组了,那么就说明是叶子节点,就需要乘以因子;如果不是那么就继续递归遍历子树,不过值得注意的是这里的递归并不是显示的,是通过map函数来进行的,因为它能将函数迭代地操作在每一层的结构上。

再去看上面的那个scheme版本,其实就是一样的写法,不过这种遍历树的方法实在是太妙了。

本来这篇文章应该在上周或者上上周就写好了,但是因为中途又重装了一次arch,又去更新eaf-rss-reader的opml功能,所以一直拖延到了今天才写。不过我总算是把这个这么美妙的方法记录下来了。

发表评论

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