合并和提取列表

Question

我正在编写一个合并两个列表的函数.如果列表的项目之一是列表,我也需要提取它.

list1:'(1 (2 3 4) 5 6)) 

list2: '(7 (8 9) 10 (11))

output: (1 2 3 4 5 6 7 8 9 10 11)

我尝试通过我的代码解决它不起作用.问题是什么？

(define (merge lis1 lis2)
    (define (combine lis fine)
        (cond
            ((null? lis) lis)
            ((list? lis) (combine (car lis) fine) (combine (cdr lis) fine))
            (else  (cons lis fine))))

        (cond
            (combine (cons lis2 lis1) '())))

Answer 1

最简单的方法是简单地使用库函数flatten.

(define (merge lis1 lis2)
  (flatten (cons lis1 lis2)))

flatten 获取可以包含列表的列表(反过来可以包含更多列表,...)并将结果展平为非列表列表,这是您的组合函数似乎正在尝试执行的操作.

(flatten '(1 2 (3 (4 5) 6))) 回报 '(1 2 3 4 5 6)

如果此库函数不受限制,则您的代码实际上非常接近正确.

第一个问题是((list? lis) (combine (car lis) fine) (combine (cdr lis) fine) )在线. fine永远不会改变,所以代码计算(combine (car lis) fine)然后返回(combine (cdr lis) fine),其中fine第二个表达式是原始值fine.这条线是一样的((list? lis) (combine (cdr lis) fine) ),显然不是我们想要的.相反,我们必须在第二个表达式中使用第一个表达式((list? lis) (combine (cdr lis) (combine (car lis) fine))).

第二个问题是,在combine中,当lis为null时,我们需要返回fine,而不是lis.

下一个问题是这个代码遍历列表,获取第一个元素lis并将其放在前面fine,然后传递新创建的列表并将其用于函数的下一次迭代,其中它取第二个值lis并且把它贴在新fine的前面,在第一个值的前面lis.按顺序返回的结果fine- (merge '(1 2 (3)) '(4 (5 6)))将返回(6 5 4 3 2 1).我们有两个选择:我们可以combine在体内返回时调用反向,merge或者我们可以反转我们在上面改变的线,制作它((list? lis) (combine (car lis) (combine (cdr lis) fine))).这意味着我们会fine在添加当前元素之前添加列表的其余部分,这正是我们想要的.

另一个问题是,我们需要利弊lis1来lis2,而不是周围的其他方式.

最后一个问题是,cond在体内merge是不必要的 - 我们可以删除它.

作为旁注,通常认为不要给出一个新的线和一个define或cond仅仅两个空格的主体缩小括号.

通过所有这些更改,最终代码为:

(define (merge lis1 lis2)
  (define (combine lis fine)
    (cond
      ((null? lis) fine)
      ((list? lis) (combine (car lis)
                            (combine (cdr lis) fine)))
      (else  (cons lis fine))))

  (combine (cons lis1 lis2) '()))