iteration - 使用过滤器或折叠球拍遍历嵌套列表

Question

我需要使用列表迭代和过滤来遍历 Racket 中包含子列表的列表，其中一个列表是嵌套列表，我尝试使用“ list?”和“ car”在内部进行迭代，但当然这只适用于第一个值子列表。

有没有办法使用列表迭代和过滤来迭代整个嵌套列表？

(define (count-evens lst)
  (length 
    (filter 
      (lambda (x) 
        (cond 
           [(and (list? x) 
                 (and (number? (car x)) 
                      (eq? (modulo (car x) 2) 0))) 
              #t]
           [(and (number? x) 
                 (eq? (modulo x 2) 0)) 
              #t]
           [else
              #f]))
    lst)))

(count-evens '(1 2 5 4 (8 4 (b (10 3 3))) 3))  
=> 3
Should return  => 5

我会使用递归函数来执行此操作，但分配不允许这样做。

标签： iterationfilteringracketnested-listsfold

Answer 1

“...赋值不允许 [递归函数]”

不确定这个任务允许什么，但在过去，我们用堆栈处理递归数据结构......

(define (count-evens lst)
  (define (lst-at stack)          ;; (car stack) = index in deepest sub-list
    ;; produce list cursor within lst indexed by stack
    (do ([stack  (reverse stack) (cdr stack)]
         [cursor (list lst) (list-tail (car cursor) (car stack))])
      ((null? stack) cursor)))
  (do ([stack (list 0)
              (cond
                [(null? (lst-at stack))
                 (cdr stack)]     ;; pop stack
                [(pair? (car (lst-at stack)))
                 (cons 0 stack)]  ;; push stack
                [else             ;; step through current (sub)list
                 (cons (+ 1 (car stack)) (cdr stack))])]
       [count 0
              (let ([item (car (lst-at stack))])
                (if (and (number? item) (even? item)) (+ 1 count) count))])
    ((null? (lst-at stack)) count)))

> (count-evens '(1 2 5 4 (8 4 (b (10 3 3))) 3))  ;=>
5