Начните с создания набора связанных примеров, наиболее тривиальных сначала:
(equal? (segs '())
(list '()))
(equal? (segs '(z))
(list '()
'(z)))
(equal? (segs '(y z))
(list '() '(z)
'(y) '(y z)))
(equal? (segs '(x y z))
(list '() '(z) '(y) '(y z)
'(x) '(x y) '(x y z)))
Глядя на примеры, вы можете сделать наблюдение (которое я использовал для форматирования, чтобы выделить): ответдля каждого примера включены все элементы из ответа для предыдущего примера.Фактически, смежные подпоследовательности непустого списка - это просто смежные подпоследовательности его хвоста вместе с непустыми префиксами самого списка.
Так что отложите основную функцию и напишите non-empty-prefixes
non-empty-prefixes : list -> (listof non-empty-list)
С помощью этой вспомогательной функции легко написать основную функцию.
(Необязательно) Полученная наивная функция имеет плохую сложность, потому что она повторяет вызовыnon-empty-prefixes.Рассмотрим (segs (cons head tail)).Он вызывает (non-empty-prefixes tail) дважды: один раз, потому что он вызывает (segs tail), который вызывает (non-empty-prefixes tail), и снова, потому что он вызывает (non-empty-prefixes (cons head tail)), который вызывает (non-empty-prefixes tail) рекурсивно.Это означает, что наивная функция имеет излишне плохую сложность.
Проблема в том, что (segs tail) вычисляет (non-empty-prefixes tail), а затем забывает об этом, поэтому (segs (cons head tail)) должен повторить работу.Решение состоит в том, чтобы сохранить эту дополнительную информацию путем объединения segs и non-empty-prefixes в одну функцию, которая вычисляет оба ответа:
segs+ne-prefixes : list -> (values (listof list) (listof non-empty-list))
Затем определите segs как функцию адаптера, которая просто отбрасываетвторая часть.Это решает основную проблему со сложностью.
(отредактировано для добавления) Относительно segs+ne-prefixes: вот один из способов определения non-empty-prefixes.(Примечание: пустой список не имеет непустых префиксов. Не нужно выдавать ошибку.)
;; non-empty-prefixes : list -> (listof non-empty-list)
(define (non-empty-prefixes lst)
(cond [(empty? lst)
empty]
[(cons? lst)
(map (lambda (p) (cons (first lst) p))
(cons '() (non-empty-prefixes (rest lst))))]))
И segs выглядит следующим образом:
;; segs : list -> (listof list)
(define (segs lst)
(cond [(empty? lst) (list '())]
[(cons? lst)
(append (segs (rest lst))
(non-empty-prefixes lst))]))
Вы можете плавитьони вот так:
;; segs+ne-prefixes : list -> (values (listof list) (listof non-empty-list))
;; Return both the contiguous subsequences and the non-empty prefixes of lst
(define (segs+ne-prefixes lst)
(cond [(empty? lst)
;; Just give the base cases of each function, together
(values (list '())
empty)]
[(cons? lst)
(let-values ([(segs-of-rest ne-prefixes-of-rest)
;; Do the recursion on combined function once!
(segs+ne-prefixes (rest lst))])
(let ([ne-prefixes
;; Here's the body of the non-empty-prefixes function
;; (the cons? case)
(map (lambda (p) (cons (first lst) p))
(cons '() ne-prefixes-of-rest))])
(values (append segs-of-rest ne-prefixes)
ne-prefixes)))]))
Эта функция по-прежнему следует рецепту проектирования (или она была бы, если бы я показывал свои тесты): в частности, она использует шаблон для структурной рекурсии в списке.HtDP не говорит о values и let-values, но вы можете сделать то же самое со вспомогательной структурой для группировки информации.
HtDP немного говорит о сложности, но такая перегруппировкавычисления обычно обсуждаются в курсе алгоритмов, в разделе «Динамическое программирование и запоминание».Обратите внимание, что альтернативой слиянию двух функций было бы запоминание non-empty-prefixes;это также исправило бы сложность.
И последнее: аргументы для append ближе к концу следует поменять местами до (append ne-prefixes segs-of-rest).(Конечно, это означает, что нужно переписать все тесты, чтобы использовать новый порядок, или написать / найти функцию сравнения списков, нечувствительных к порядку.) Попробуйте сравнить две версии функции в большом списке (около 300-400 элементов),посмотрите, сможете ли вы сказать разницу, и посмотрите, сможете ли вы это объяснить(Это скорее материал алгоритмов, а не дизайн.)