Функция Variadic append (добавление любого количества списков вместе)

Я пытаюсь реализовать схему процедуры append самостоятельно. Самая простая версия - добавить 2 списка вместе, это довольно просто и может быть сделано с помощью:

 (define (append lis1 lis2)
                  (if (null? lis1) 
                    lis2
                    (cons (car lis1)
                          (append (cdr lis1) lis2))))

Проблемы начинаются, когда вы хотите добавить любое количество списков. Для 0 списков и 1 списков идея проста, но мне очень трудно подумать, как применить эту процедуру к любому количеству списков... Любая помощь будет оценена, Орен


lambda variadic-functions scheme racket
person vito    schedule 08.02.2016    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Ответ Оскара хорош, но я бы, вероятно, reverse вводил и использовал foldl вместо этого, поскольку foldl реализован с правильным хвостовым вызовом.

(define (append* . xs)
  (foldl append null (reverse xs)))

Выход такой же

(append* '(1 2) '(3) '(4 5 6) '(7 8))
=> '(1 2 3 4 5 6 7 8)
person Mulan    schedule 08.02.2016
comment
(Я перечитал ваш ответ, и он не страдает от проблемы O (n²), о которой я упоминал. Но наивная реализация, использующая накопленный список в качестве левого аргумента для append, была бы неправильной.) Здесь есть +1. - person Chris Jester-Young; 08.02.2016
comment
@ChrisJester-Young, я прочитал многие из ваших статей и очень уважаю ваши отзывы. Не могли бы вы детализировать оценку, чтобы лучше проиллюстрировать проблему? Я все еще относительно новичок в рэкете. - person Mulan; 08.02.2016
comment
Ваш ответ в порядке (извините за неправильное прочтение вашего ответа в первую очередь). Неправильным ответом было бы что-то вроде (define (append* . lsts) (foldl (lambda (lst acc) (append acc lst)) '() lsts)), что было бы O(n²) (где n — общая длина всего списка ввода, кроме последнего), из-за того, как работает append. - person Chris Jester-Young; 08.02.2016
comment
Спасибо за простое решение! - person vito; 08.02.2016
comment
@oren Ха. Проводя исследование для предстоящего сообщения в блоге, чтобы ответить на вопрос Наомик, я обнаружил, что стандартная схема append уже имеет вариации и уже делает то, что вы ищете. Вы уверены, что вам вообще нужно писать код? (Редактировать: О, я перечитал ваш вопрос. Вы реализуете свой собственный append. Кажется, сегодня не лучший день для моего понимания прочитанного. :-P) - person Chris Jester-Young; 08.02.2016
comment
Сообщение в блоге уже опубликовано: qr.ae/ROZpq7. Я надеюсь, что это объясняет ситуацию лучше! /cc @oren - person Chris Jester-Young; 08.02.2016
comment
Следуя вашему блогу (большое спасибо!), и после небольшого собственного тестирования я наткнулся на что-то странное (может быть, не странное, но что-то, чего я не исключал) для следующего кода: (define x '(1 2 )) (define y '(3 4)) (define z (append x y) (set-car! x $) (set-car y *) вы получаете -> (1 2 * 4) с добавлением схемы, и все же ( 1 2 3 4) с другой реализацией я знаю, что и x, и y являются константами времени выполнения, и при использовании cons я создаю их копию, но вопрос в том, что делает chez по-другому? - person vito; 09.02.2016

arrow_upward
3
arrow_downward

Нам просто нужно неоднократно применять вашу функцию append, а foldr — это инструмент для работы. Попробуй это:

(define (append* . lsts)
  (foldr (lambda (sublist acc)
           (append sublist acc))
         '()
         lsts))

Например:

(append* '(1 2) '(3) '(4 5 6) '(7 8))
=> '(1 2 3 4 5 6 7 8)
person Óscar López    schedule 08.02.2016