Scheme - 用于将函数应用于嵌套列表中的元素的Map函数

Question

我正在尝试在方案中编写映射函数，该函数将函数应用于嵌套列表中的每个值。

例如，(map number? '(3 (2 A) 2 Z)应该返回(#t (#t #f) #t #f)

这是我到目前为止所拥有的：

(define (map fun lst)
    (if (null? lst) '()
        (if (list? (car lst)) 
            (cons (map fun (car lst)) (map fun (cdr lst)))
                 (cons (fun (car lst)) (map fun (cdr lst))))))

如果嵌套列表位于列表的前面，则它可以工作。例如，(map number? '((3 A) 2 Z))正确返回((#t #f) #t #f)

当嵌套列表发生在原始列表中的另一个元素之后时，会发生此问题。例如(map number? '(3 A (2 Z)))错误地返回(#t #f #f) [结果应该是(#t #f (#t #f))]

如何更改算法以更正此问题？

Answer 1

这是我的解决方案---它使用map重新使用内置的decorator pattern非常便宜。 （我知道，使用设计模式的Scheme程序？： - O）

(define (deep-map f l)
  (define (deep x)
    (cond ((null? x) x)
          ((pair? x) (map deep x))
          (else (f x))))
  (map deep l))

通过使用命名的let，可以进一步“简化”：

(define (deep-map f l)
  (let deep ((x l))
    (cond ((null? x) x)
          ((pair? x) (map deep x))
          (else (f x)))))

（代码的两个片段不完全相同，但是对于这个问题，如果将列表作为输入，两者都将起作用。）

使用null?和pair?检查（均为O（1））以避免使用list?（即O（n））。

Answer 2

你的代码是正确的，除了它太冗长了。提示：你只需要担心两个案例：lst是否是pair?。就这样。换句话说，您的代码假定输入始终是一个列表，但它可以简化为接受任何内容，并在它成对时执行特殊的递归操作。

至于你所看到的问题 - 我的猜测是你正在使用Racket，因此你会遇到奇怪的情况。如果不是这种情况，那么你可以在这里停止阅读。

问题是在Racket中函数本身将在绑定到map之前编译，因此map调用不是真正的递归，而是它们只是调用内置的map。稍后，map（重新）绑定到结果函数，但递归调用已经编译。如果您输入两次相同的定义，您将看到它再次开始工作。解决这个问题的方法是不在REPL中工作，而是始终在一些以#lang <something>开头的文件中编写定义。