list - 再帰を使用してアトムのリストを単一のリストに変換する

Question

アトムのリストを再帰的に単一のリストに変える答えを探しています。

例は(slist '(a (b c) (d e (f) g) h))、(slist (a b c d e f g h))

どんな答えでも役に立ちます。

Answer 1

あなたがやろうとしていることは、リストの平坦化と呼ばれます。ここにたくさんのオプションがあります：

; required predicate

(define (atom? x)
  (and (not (null? x))
       (not (pair? x))))

; naïve version using append

(define (flatten1 lst)
  (cond ((null? lst)
         '())
        ((not (pair? lst))
         (list lst))
        (else
         (append (flatten1 (car lst))
                 (flatten1 (cdr lst))))))

; naïve version using append, map, apply

(define (flatten2 lst)
  (if (atom? lst)
      (list lst)
      (apply append (map flatten2 lst))))

; efficient version using fold-left

(define (flatten3 lst)
  (define (loop lst acc)
    (if (atom? lst)
        (cons lst acc)
        (foldl loop acc lst)))
  (reverse (loop lst '())))

; very efficient version with no higher-order procedures

(define (flatten4 lst)
  (let loop ((lst lst)
             (acc '()))
    (cond ((null? lst)
           acc)
          ((not (pair? lst))
           (cons lst acc))
          (else
           (loop (car lst) (loop (cdr lst) acc))))))

上記のいずれも期待どおりに機能します。たとえば、次を使用しflatten4ます。

(flatten4 '(a (b c) (d e (f) g) h))
=> '(a b c d e f g h)

使用しているインタープリターによっては、既に実装が含まれている可能性があります。たとえば、ラケットでは次のようになります。

(flatten '(a (b c) (d e (f) g) h))
=> '(a b c d e f g h)

Answer 2

すでに正しい答えを確認しましたが、再帰を明確に示す簡単な実装を次に示します。

(define (slist list)
  (if (null? list)
      '()
      (let ((next (car list))
            (rest (cdr list)))
        (if (list? next) 
            (append (slist next) (slist rest))
            (cons next (slist rest))))))