list - Scheme - 映射函数，用于将函数应用于嵌套列表中的元素

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

这是我的解决方案 --- 它非常便宜，因为它使用 decorator pattern 重用内置 map . (我知道，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)).