Как получить функцию segs?

Question

Как я могу построить функцию segs, которая возвращает список всех смежных сегментов в списке? Например, (segs '(l i s t)) должен произвести следующий ответ:

(() (t) (s) (s t) (i) (i s) (i s t) (l) (l i) (l i s) (l i s t)) 

Я особенно заинтересован в том, как решить эту проблему в соответствии с принципами дизайна, описанных в HTDP (нет, это не проблема из книги, поэтому, пожалуйста, не стесняйтесь обсуждать это!) Как это решить? Какие принципы следует использовать при выводе программ?

Answer 1

Start путем создания набора связанных примеров, самый тривиальный первый:

(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 говорит о сложности немного, но такого рода перегруппировка вычислений обычно обсуждается больше в курсе алгоритмов под «динамическим программированием и памятью». Обратите внимание, что альтернативой слиянию двух функций было бы memoize non-empty-prefixes; что также затруднило бы сложность.

Последнее: аргументы append вблизи конца должны быть отменены, до (append ne-prefixes segs-of-rest). (Разумеется, это означает переписывание всех тестов для использования нового порядка или запись/поиск функции сравнения списка без учета порядка.) Попробуйте сравнить две версии функции в большом списке (около 300-400 элементов), посмотрите, можете ли вы сказать разницу, и посмотрите, сможете ли вы это объяснить. (Это больше материалов алгоритмов, а не дизайн.)

Answer 2

Происходит 2 рекурсии: первый отбивает атомы слева, а второй отбирает атомы справа. Вот как я бы решить рекурсивно в 2-х функций, в простых терминах (так как я не свободно на схеме):

Start with the FullList variable in function A, 
accumulate right-chop results on FullList from recursive function B, 
then chop off the left character of FullList and call function A with it. 
Stop when an empty list is received. 

накапливались все результаты, и вы золотой.