1

目标是消除所有内括号。

(flatten '(a (bc) d)) 变成 '(abcd)

这是我在球拍中的代码

; if slist is null, return empty
; otherwise, if it is a pair, recursively solve car and cdr and concat them
; if it is a symbol, return the symbol

(define flatten
  (lambda (slist)
    (cond
      [ (null? slist) '()]
      [ (pair? slist)  
        (cons ((flatten (car slist)) (flatten (cdr slist))))]
      [ (symbol? slist) slist])))

它在抱怨

procedure application: expected procedure, given: c; arguments were: ()

这意味着我正在尝试访问一个carcdr列表。

I did the trace:
> (flatten '(a (b c) d))
pair?-car-cdr
a
((b c) d)
symbol?
a
pair?-car-cdr
(b c)
(d)
pair?-car-cdr
b
(c)
symbol?
b
pair?-car-cdr
c
()
symbol?
c
(stops here)

跟踪代码很简单——一堆显示。

(define flatten
  (lambda (slist)
    (cond
      [ (null? slist) '()]
      [ (pair? slist) 
        (display 'pair?-car-cdr)
        (newline)
        (display (car slist))
        (newline)
        (display (cdr slist))
        (newline)
        (cons ((flatten (car slist)) (flatten (cdr slist))))]
      [ (symbol? slist) 
         (display 'symbol?)
         (newline)
         (display slist)
         (newline)
        slist])))

我不明白的是为什么第一个条件(null? slist)没有抓住空列表?我有两个递归调用。如果它确实捕获了空列表,它将进入下一个递归,即 list {d}

我的递归逻辑有什么问题?


更新版本

(define flatten
  (lambda (slist)
    (cond
      [ (null? slist) '()]
      [ (pair? slist)  
        (cons (flatten (car slist)) (flatten (cdr slist)))]
      [ (symbol? slist) slist])))

(display (equal? (flatten '(a (b a) b a c (a b) c (e f (b a)))) '(a b a b a c a b c e f b a)))
(newline)
(display (equal? (flatten '(a b c)) '(a b c)))
(newline)
(display (equal? (flatten '(a (b c))) '(a b c)))
(newline)
(display (equal? (flatten '((a)(b)(c) d)) '(a b c d)))
(newline)
(display (equal? (flatten '(a (b) ((c)) (((d))) ((((e (f g))))))) '(a b c d e f g )))
(newline)
(display (equal? (flatten '()) '()))
(newline)
(display (equal? (flatten '(a b () ())) '(a b)))
(newline)

正如 Ross Larson 建议的那样, append 将使程序正常工作。但是为了学习,如果有人有空的话,我的测试结果只显示通过了基本案例(第二个和空列表)

我想过写一个包装函数来调用(cons (flatten slist) empty)

4

2 回答 2

5

问题是这个表达式:

(((展平(汽车清单))...)

这意味着,应用任何 (flatten ...) 返回。但是由于这会返回一个列表,因此应用程序会失败。

将其更改为

(展平(车单))

于 2012-02-13T15:39:56.853 回答
1

cons 将重新创建结构(正如您所观察到的)。改为查看 append 。

http://docs.racket-lang.org/reference/pairs.html

(我没有解决其他问题,因为其他答案似乎已经修复了递归值的应用)

于 2012-02-13T23:36:36.017 回答