首页 文章

使用（约束）Racket查找列表的深度

提问于
浏览 次
2

逻辑的另一个问题，任务是找到列表的深度，例如：给定一个 (A B (C D (E))) 列表，它应该以某种方式指示深度为2（如果包含基本列表则为3） . 我被限制在一组常见的Racket函数中，我将在下面列出 . 我在哪里，我可以遍历列表，但最终停在第一个子列表，即： (A (B (C)) (D (E (F)))) 只出现2 .

以下是可用功能列表：

  • cons，car，cdr，define，quote，if，cond，else

  • 算术的基本形式（， - ，*，/）

  • 非常基本的测试（null？，list？，eq？，数字比较）

到目前为止，这是我的定义，如果有人能让我朝着正确的方向转变，我真的很感激 .

(define (len l) (if (null? l) 0 (+ 1 (len (cdr l)))))

(define A '(A (B) (C (D))))

(define (depth l) (cond

                    [(null? l) '()]

                    [(list? (car l)) (cons (car l) (depth (car l)))]

                    [else (depth (cdr l))]

                    ))

(depth A)

(len (depth A))
list recursion lisp racket depth

3 回答

  • 1

    这是我在Common Lisp中的定义

    (defun list-depth (list &optional (depth 0))
  (cond ((null list) depth)
        ((atom (first list)) (list-depth (rest list) depth))
        (t (max (list-depth (first list) (1+ depth))
                (list-depth (rest list) depth)))))

    我没有在这台电脑上安装Racket，所以这是一个未经测试的Scheme / Racket翻译：

    (define (list-depth lst depth)
  (cond ((null? lst) depth)
        ((not (list? (car lst)) (list-depth (cdr list) depth))
        (else (max (list-depth (car lst) (+ 1 depth))
                   (list-depth (cdr lst) depth)))))

    逻辑如下：

    • 如果列表为空，则返回当前深度 .

    • 如果列表的 car 是原子（不是列表），则不会增加深度，找到列表的其余部分（ cdr ）的深度 .

    • 否则，深度将是 car 的1个深度之间的最大值（记住，现在是列表）和列表的 cdr 的深度 . 注意 car 的深度增加，而不是 cdr .

    使用的预定义程序： + ， max ， null? ， list? ， car ， cdr ， not .

    回复于
  • 0

    在我的答案中，列表以深度0开始，并且每个嵌套级别增加1 . 如果您希望它们以1的深度开始，您可以在列表深度过程中将（y 0）更改为（y 1）

    这可以通过简单的折叠实现

    (define (list-depth xs (y 0))
  (foldl (λ (x z)
           (if (list? x)
               (max z (list-depth x (+ 1 y)))
               (max z y)))
         y
         xs))

    foldl 有一个简单的实现

    (define (foldl f y xs)
  (if (null? xs)
      y
      (foldl f (f (car xs) y) (cdr xs))))

    这是一些输出

    (list-depth '())                              ; ⇒ 0
(list-depth '(A))                             ; ⇒ 0
(list-depth '(A (B)))                         ; ⇒ 1
(list-depth '(A (B (C))))                     ; ⇒ 2
(list-depth '(A (B (C (D (E)))) (B (C)) (B))) ; ⇒ 4

    如果您不想使用折叠抽象，则可以在 list-depth 内扩展折叠

    ;; THIS CODE IS BROKEN, DO NOT USE
;; @mobiuseng found bugs
(define (list-depth xs (y 0))
  (cond
    [(null? xs) y]
    [(list? (car xs))
     (max y (list-depth (car xs) (+ 1 y)))]
    [else
     (max y (list-depth (cdr xs) y))]))

    两者都产生相同的输出，但在此实现中，折叠和最大值这两个概念纠缠在一起 . 与第一个相比，看到折叠的内脏使得阅读这个答案变得更加困难 .

    折叠的内脏使得虫子很容易隐藏在最后的片段中 . 我不能建议首先写这种方式，所以我不打算花费精力来修复它 .

    回复于
  • 0

    每个列表都是在 car 下的当前元素和 cdr 下的列表的其余部分构建的 .

    • 列表的深度与列表其余部分的深度相同，如果这是最深的 .

    • 如果这是最深的，那么列表的深度比其 car 的深度多一个 .

    所以，

    (define (depth lst)
  (define a-depth (+ 1 (depth (car lst))))
  (define d-depth (depth (cdr lst)))
  (if (< ..... ) ..... 
    ; or else
    ...... ))

    当然，不要忘记处理列表为空时的情况，或者原子（不是一对 - 你不能用非对参数调用 car 或 cdr ，如果你这样做会导致错误） ：

    • 空列表的深度为零 .

    • 原子的深度为零 .

    回复于

相关问题