function segs를 파생시키는 방법은 무엇입니까?

Question

목록의 모든 연속 세그먼트 목록을 반환하는 함수 segs을 어떻게 구성 할 수 있습니까? 아니,이 책에서 문제가되지 않습니다 (

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

내가 HTDP에 설명 된 설계 원칙에 따라이 문제를 해결하는 방법에 특히 관심이 있어요 : 예를 들어 , (segs '(l i s t)) 다음과 같은 대답을 생산한다 그러니 자유롭게 토론하십시오!) 어떻게 해결할 수 있습니까? 프로그램 유도에서 사용하는 원칙은 무엇입니까?

Answer 1

시작 사소한 첫째, 관련 사례의 집합을 구축하여 다음 답변 :

(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)을 두 번 호출합니다. 즉, (non-empty-prefixes tail)을 호출하는 (segs tail)을 호출하고 다시 (non-empty-prefixes tail)을 호출하는 (non-empty-prefixes (cons head 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 요소)에서 두 가지 버전의 함수를 벤치마킹 해보십시오. 당신이 차이를 말할 수 있는지, 그리고 당신이 그것을 설명 할 수 있는지보십시오. (이것은 알고리즘이 아니라 디자인입니다.)

Answer 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. 

누산 모든 결과, 당신은 황금 위치 : 여기에 (내가 계획에 능통 아니에요 이후) 나는 일반 용어로,이 개 기능에 반복적으로 그것을 해결 것 방법입니다.