方案 - 用于将函数应用于嵌套列表中的元素的映射函数

发布于 2024-11-02 07:17:23 字数 660 浏览 4 评论 0原文

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

例如， (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))]

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

原文

I'm trying to write a mapping function in scheme that applies a function to each value in a nested list.

For example, (map number? '(3 (2 A) 2 Z) should return (#t (#t #f) #t #f)

Here's what I have so far:

(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))))))

It works if the nested list is at the front of the list. For example (map number? '((3 A) 2 Z)) correctly returns ((#t #f) #t #f)

The problem occurs when the nested list occurs after another element in the original list.
For example (map number? '(3 A (2 Z))) incorrectly returns (#t #f #f) [The result should be (#t #f (#t #f))]

How can I change my algorithm to correct this?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

野却迷人 2024-11-09 07:17:23

这是我的解决方案——它非常便宜，因为它使用装饰器模式。（我知道，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)）。

Here's my solution---it's seriously cheap in that it reuses the built-in map, using the decorator pattern. (I know, Scheme programs using design patterns? :-O)

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

This can be "simplified" even further by using a named let:

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

(The two snippets of code are not identical, but for this question, both will work the same if given a list as input.)

The null? and pair? checks (both O(1)) are used in order to avoid using list? (which is O(n)).

回复收藏 0 原文

离不开的别离 2024-11-09 07:17:23

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

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

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