2

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

例如，(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)[The result should be (#t #f (#t #f))]

我怎样才能改变我的算法来纠正这个问题？

4

2 回答 2

4

这是我的解决方案——它非常便宜，因为它重用了内置的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)）。

于 2011-04-18T08:22:31.870 回答
3

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

至于你看到的问题——我猜你正在使用 Racket，因此你遇到了一个奇怪的情况。如果不是这种情况，那么您可以在此处停止阅读。

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

于 2011-04-18T07:52:56.920 回答