Слияние пар прыжков

Question

Как рекурсивно объединить прыгающих пар элементов списка списков?Мне нужно, чтобы

'((a b c) (e d f) (g h i))

из

'((a b) c (e d) f (g h) i)

Моя попытка

(define (f lst)      
  (if (or (null? lst)            
          (null? (cdr lst))) 
      '()                                                          
      (cons (append (car lst) (list (cadr lst))) 
            (list (append (caddr lst) (cdddr lst))))))

работала, если я определил

(define listi '((a b) c (d e) f))

, из которого я получаю

((a b c) (d e f))

, выполняя просто

(f listi)

, но это не работает для длинных списков.Я знаю, что мне нужна рекурсия, но я не знаю, где снова вставить f в последнее предложение моего кода.

Answer 1

В вашем коде нет рекурсивного регистра, поэтому он будет работать статически для списка из 4 элементов. Вам необходимо поддержать следующее:

(f '()) ; ==> ()
(f '((a b c) d (e f g) h)) ; ==> (cons (append '(a b c) (list 'd)) (f '((e f g) h)))

Теперь для этого требуется ровно четное количество элементов, и каждый нечетный элемент является правильным списком. В этом нет ничего плохого, но onw может захотеть убедиться в этом, проверив тип или добавив код для того, что должно произойти, когда это не так.

Answer 2

Сопоставление с образцом (используя match ниже) безумно полезно для такого рода проблем -

(define (f xs)
  (match xs
    ;; '((a b) c . rest)
    [(list (list a b) c rest ...)
     (cons (list a b c)
           (f rest))]
    ;; otherwise
    [_
     empty]))

define/match предлагает немного синтаксического сахара для этого общего стиля процедуры, делающего вещи еще лучше -

(define/match (f xs)
  [((list (list a b) c rest ...))
   (cons (list a b c)
         (f rest))]
  [(_)
   empty])

И хвост-рекурсивная ревизия -

(define (f xs)
  (define/match (loop acc xs)
    [(acc (list (list a b) c rest ...))
     (loop (cons (list a b c) acc)
           rest)]
    [(acc _)
     acc])
  (reverse (loop empty xs)))

Вывод для каждой программы одинаковый -

(f '((a b) c (e d) f (g h) i))
;; '((a b c) (e d f) (g h i))

(f '((a b) c))
;; '((a b c))

(f '((a b) c x y z))
;; '((a b c))

(f '(x y z))
;; '()

(f '())
;; '()

---

В качестве дополнительного бонуса в этом ответе не используется дорогостоящая append операция

Answer 3

Более простой случай, когда ваш алгоритм не работает: (f '((1 2) 3)) должен привести к '((1 2 3)), но ваш приведет к ошибке.

Сначала мы определим некоторые термины:

1. «Элемент» - это обычный элемент, например 1 или 'a.

2. «Простой список» - это просто список «элементов» без вложенного списка. Например, '(1 2 3) - простой список. '((1 2) 3) не простой список. «Простой список» - это либо:

   • и empty список
   • a cons "элемента" и следующего "простого списка"

3. «Список прыжковых пар» - это список четной длины, где нечетный индекс имеет «простой список», а четный индекс имеет элемент. Например, '((1) 2 (a) 4) - это «список прыжковых пар». «Список прыжковых пар» - это либо:

   • и empty список
   • a cons из
     1. «простой список»
     2. a cons "элемента" и следующего "списка прыжковых пар"

Мы закончили с терминологией. Прежде чем писать функцию, давайте начнем с нескольких примеров:

(f '())              equivalent to (f empty)

                     should output '()
                     equivalent to empty

(f '((1 2) 3))       equivalent to (f (cons (cons 1 (cons 2 empty)) 
                                            (cons 3 
                                                  empty)))

                     should output '((1 2 3))
                     equivalent to (cons (cons 1 (cons 2 (cons 3 empty)))
                                         empty)

(f '((1 2) 3 (4) a)) equivalent to (f (cons (cons 1 (cons 2 empty)) 
                                            (cons 3
                                                  (cons (cons 4 empty)
                                                        (cons 'a 
                                                              empty)))))

                     should output '((1 2 3) (4 a))
                     equivalent to (cons (cons 1 (cons 2 (cons 3 empty)))
                                         (cons (cons 4 (cons 'a empty))
                                               empty))

Итак, f - это функция, которая использует «список прыжковых пар» и возвращает список «простого списка».

Теперь напишем функцию f:

(define (f lst)
  ???)

Обратите внимание, что тип lst является «списком прыжковых пар», поэтому мы выполним анализ случая непосредственно:

(define (f lst)      
  (cond
    [(empty? lst) ???]               ;; the empty list case

    [else         ???                ;; the cons case has
                  (first lst)        ;; the "plain list",
                  (first (rest lst)) ;; the "element", and
                  (rest (rest lst))  ;; the next "list of jumping pairs"
                  ???]))             ;; that are available for us to use

Из примера:

(f '())              equivalent to (f empty)

                     should output '()
                     equivalent to empty

мы знаем, что пустой регистр должен возвращать пустой список, поэтому давайте заполним соответствующее отверстие:

(define (f lst)      
  (cond
    [(empty? lst) empty]             ;; the empty list case

    [else         ???                ;; the cons case has
                  (first lst)        ;; the "plain list",
                  (first (rest lst)) ;; the "element", and
                  (rest (rest lst))  ;; the next "list of jumping pairs"
                  ???]))             ;; that are available for us to use

Из примера:

(f '((1 2) 3))       equivalent to    (f (cons (cons 1 (cons 2 empty)) 
                                               (cons 3 
                                                     empty)))

                     should output '((1 2 3))
                     equivalent to (cons (cons 1 (cons 2 (cons 3 empty)))
                                         empty)

мы знаем, что мы определенно хотим поместить «элемент» в конец «простого списка», чтобы получить результирующий «простой список», который нам нужен:

(define (f lst)      
  (cond
    [(empty? lst) empty] ;; the empty list case

    [else ;; the cons case has:
          ???

          ;; the resulting "plain list" that we want
          (append (first lst) (cons (first (rest lst)) empty))

          ;; the next "list of jumping pairs"
          (rest (rest lst))   

          ;; that are available for us to use
          ???]))              

Остался еще один «список прыжковых пар», с которым нам нужно разобраться, но у нас уже есть способ справиться с ним: f!

(define (f lst)      
  (cond
    [(empty? lst) empty] ;; the empty list case

    [else ;; the cons case has:
          ???

          ;; the resulting "plain list" that we want
          (append (first lst) (cons (first (rest lst)) empty))

          ;; the list of "plain list"
          (f (rest (rest lst)))

          ;; that are available for us to use
          ???]))

И тогда мы можем вернуть ответ:

(define (f lst)      
  (cond
    [(empty? lst) empty] ;; the empty list case

    [else ;; the cons case returns
          ;; the resulting list of "plain list" that we want
          (cons (append (first lst) (cons (first (rest lst)) empty))
                (f (rest (rest lst))))]))