何为分组函数?

举个例子,有1个包含9个数值元素的list,其中每3个元素为1个点的三维坐标,现在要求将每个点的三维坐标提取出来, 组成1个list,然后,将这些点坐标list作为元素,返回一个与初始list相同顺序的点坐标list的list。

上述这个例子,就是一个分组问题,能解决这个问题的函数,就可以称作为分组函数。这种分组函数的应用,实际上是十分广泛的, 然而,大多数的lisp实现,并没有内置这样的函数,得我们自己动手来实现。

分组函数功能分析

还是以上述的坐标值list为例。

首先,要提取3个坐标值,组成新的list,代表某个点的三维坐标。如果推广一下,就是提取n个元素,组成新list。 姑且称之为功能1。

其次,返回值是以新list为元素的list,因此,要用新list作为元素来构造一个list作为返回值。 姑且称之为功能2。

最后,返回值list中元素的顺序需要与初始list的顺序一致,那么,就需要一种保证顺序不乱的机制或者策略。 姑且称之为功能3。

分组函数的算法

老规矩,还是用递归,毕竟是lisp。

功能1的算法很简单,提取首元素,递归调用函数自身n次即可。功能2也是很简单的,构造list的方法是很多的。

最麻烦的是功能3,要保证元素顺序,那么给每个元素加个编号?似乎有点用力过度了。既然是递归的思路解决问题, 那就把功能1提取出来的元素去掉呗,这样一来,下次执行功能1的时候,就能提取到新的一组元素,并且,还是按顺序提取的, 一石二鸟。

在功能1和功能3已然以递归实现之后,功能2用递归来实现,也就是水到渠成的了。

分组函数的源代码

功能1:提取n个元素

可以写作下面这样:

1
2
3
4
(defun xg/take (lst n) 
  (if (or (null lst) (> 1 n)) 
    '()
    (cons (car lst) (xg/take (cdr lst) (- n 1)))))

这里有一点需要特别注意,这个函数的递归出口,也就是终止条件,用的是n < 1,而不是n <= 0。 之所以这么写,原因是n < 1时没有实际意义,属于不合法的参数值。

功能3:去掉n个元素

可以写作下面这样:

1
2
3
4
(defun xg/drop (lst n) 
  (if (or (null lst) (> 1 n)) 
    lst
    (xg/drop (cdr lst) (- n 1))))

功能2:组成新list

功能2也就是分组函数的主函数,可以写作下面这样:

1
2
3
4
5
(defun xg/group (lst n) 
  (cond 
    ((> 1 n) lst)
    ((null lst) '())
    (t (cons (xg/take lst n) (xg/group (xg/drop lst n) n)))))

小结

至此,分组函数大功告成。

由于功能1、功能3都是常见的、高频使用的,可以作为顶层(top-level)函数实现,以充实自己的函数库。 如果不需要这2个函数,那么就可以将二者封装起来,写作主函数的子函数,可以写作下面这样:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
(defun xg/group (lst n / xg/take xg/drop) 
  ;; 分组函数的主函数
  ;; 作者:徐工, 微博:@徐工徐工2020,头条:@徐工徐工
  ;; 返回分组后的list。

  (defun xg/take (lst n) 
    ;; 分组函数的子函数
    ;; 作者:徐工, 微博:@徐工徐工2020,头条:@徐工徐工
    ;; 返回前n个元素组成的list。
    (if (or (null lst) (> 1 n)) 
      '()
      (cons (car lst) (xg/take (cdr lst) (- n 1)))))

  (defun xg/drop (lst n) 
    ;; 分组函数的子函数
    ;; 作者:徐工, 微博:@徐工徐工2020,头条:@徐工徐工
    ;; 返回剔除掉前n个元素之后的list。
    (if (or (null lst) (> 1 n)) 
      lst
      (xg/drop (cdr lst) (- n 1))))

  (cond 
    ((> 1 n) lst)
    ((null lst) '())
    (t (cons (xg/take lst n) (xg/group (xg/drop lst n) n)))))

对于autolisp/visual lisp以外的lisp方言来说,上述代码中(defun xg/group (lst n / xg/take xg/drop), 直接写作(defun xg/group (lst n)即可。

结语

从本文以及之前的几篇博客,可以看出来,化整为零在函数功能分析和代码实现当中是非常好用的方法, 把大的复杂的功能合理切分为若干个小功能,然后,逐一实现这些小功能的函数,最后,拼装为一个大功能, 任务就完成了。

事实上,功能切分与函数实现可能会相互影响,功能切分会影响函数实现,函数实现反过来也可能会影响功能切分, 总的指导原则就是“高内聚低耦合”,当然,“高内聚低耦合”也是我们写代码所追求的目标。