递归地比较两个列表中的每个项目,返回具有最小项目的新列表

Question

在Scheme/Racket中执行此操作

问题是:取两个等长的数字列表,然后返回一个由位置最小的数字组成的列表.

例如: listMins( '(1 7 5) '(2 8 3) )

返回(1, 7, 3)因为1<2与7<8和3<5

我是函数式编程的新手,在递归时很弱.我觉得好像我只是缺少一些我不知道如何处理我的伪代码的关键部分,所以我可以开始编写这个真实的代码.(我尝试先跳入代码,但它没有用,所以我退回到伪代码.)

伪代码:

(listMins x, y)(
    (if !null A)
        (if > listAitem listBitem)
            (add A to newList) ;where do I make newList?
            (add B to newList)
        (return newList)
)

Answer 1

如果你使用高阶函数map,这实际上非常容易,特别是因为Scheme map可以接受许多参数,在这种情况下它就像一个"zip"函数.这意味着可以list-mins在一个简洁的代码行中实现您的功能:

(define (list-mins . lsts)
  (apply map min lsts))

这使用了一些相对复杂的Scheme/Racket机器,所以可能不太清楚发生了什么.虚线参数,配对apply允许list-mins使用任意数量的列表,但你真的只需要它接受两个,所以这里是一个更简单的版本:

(define (list-mins a b)
  (map min a b))

这是做什么的？好吧,map并行迭代它的参数,对每组元素应用一个过程,然后生成一个包含结果元素的新列表.该min函数只返回其参数的最小值.要了解这在实际行动中的作用,以下代码基本上是这样做的:

   (map min '(1 7 5) '(2 8 3))
=> (list (min 1 2)
         (min 7 8)
         (min 5 3))
=> (list 1 7 3)

当然,使用递归也可以自己编写.手动完成它看起来像这样:

(define (list-mins a b)
  (if (empty? a)
      '()
      (cons (min (first a) (first b))
            (list-mins (rest a) (rest b)))))

这几乎只是展开了什么map,并且map直接使用更加清晰(它表达了迭代一组列表的意图),所以它比自己进行递归更加惯用.不过,如果你正在学习,那么显式版本可能会更清楚.