foldr 및 lambda을 사용하여 목록에서 1의 수를 찾는 방법을 알아 냈습니다. 목록이 하나 (1)라켓을 사용하여 하나의 "1"에 대한 목록을 검색하십시오.
(define (exactlyone L)
(foldr (lambda (elem count) (if (equal? elem 1) (+ count 1) count))
0 L)
)
이있는 경우 그러나 어떻게 가능한 경우 경우 상태에서 count 값을 사용할 수 있습니다 어떻게 확인하는 if 조건 또는 다른 방법을 사용 하는가?
모든 목록을 탐색 할 때까지 1의 수를 확신 할 수 없으므로, 반드시 foldr은 모든 항목을 소비해야합니다. count의 반환 값이 1 있다면 그 후에는 테스트의 단순한 문제입니다 : 물론
(define (exactlyOne L)
(= 1
(foldr (lambda (elem count)
(if (equal? elem 1)
(+ count 1)
count))
0
L)))
, 가장 간단한 방법 대신 바퀴를 재발의, (예 count) 기존 프로 시저를 사용하는 것입니다. 이 라켓에서 작동합니다 : 예를 들어
(define (exactlyOne lst)
(= 1
(count (curry equal? 1) lst)))
:
(exactlyOne '(1 2 3))
=> #t
(exactlyOne '(1 2 3 1))
=> #f
가장 쉬운 방법은 자신의 재귀 할 것입니다 : 당신이 배와 그것을 해결하려면
(define (only-one predicate lst)
(let loop ((lst lst) (seen #f))
(cond ((null? lst) seen)
((not (predicate (car lst))) (loop (cdr lst) seen))
;; from here on we know predicate is true
(seen #f) ; at least two
(else (loop (cdr lst) #t))))) ; recurse with seen as #t
을 할 수 있습니다 :
(define (only-one predicate lst)
(call/cc
(lambda (return)
(foldl (lambda (e seen)
(cond ((not (predicate e)) seen) ; keep seen (whatever it is)
(seen (return #f)) ; short circuit at second match
(else #t))) ; change seen to #t
#f
lst))))
모든 요소가 처리되기 전에 우리가 결과를 알고있는 경우에 대비하여 종료 절차를 얻기 위해 call/cc을 사용합니다. 하나가 일치하지 않으면 #f이고, 정확히 한 번만 있으면 #t됩니다. 이 같은
두 작품 : 당신은 배의 커널 함수가 가변 변수를 포함하는 어휘 범위를 캡처 할 수있는 경우
(only-one (lambda (x) (equal? x 1)) '(0 1 2 3 4 5)) ; ==> #t
(only-one (lambda (x) (equal? x 1)) '(2 3 4 5)) ; ==> #f
(only-one (lambda (x) (equal? x 1)) '(0 1 2 1 3 4 5)) ; ==> #f
이 문제는 해결 될 수있다. 그런 다음 누적 기 유형 Boolean을 유지하면서 계산을 수행 할 충분한 상태를 유지할 수 있습니다.
의사 코드 :
(foldl (let ([s 0])
(lambda (accum item)
;; if (equal? item 1) and s is not already 2
;; increment s
;; return (equal? s 1)
)
#f list)
당신은 어떤 환경을 캡처하지 않는 기능이 문제를 해결 할 수 없습니다; 그러나 왜 그것을 제한합니까? 함수는 정의에 따라 코드와 어휘 환경을 더한 것입니다.
위의 경우 누산기는 기본적으로 더미입니다. s 상태가 우리가 필요한 모든 것을 나타 내기 때문에 우리는 그것을 보지 않습니다. 부울 s을 사용하여 상태가 누적 기 매개 변수와 정보의 조합 인 s이 될 수 있습니다. 부울 누적 기와 부울 s 사이에서 상태를 나눌 수 있습니다 (따라서 이들이 함께 세 개의 상태를 나타내는 2 비트 카운터를 형성합니다).
여기가 변경 가능한 환경 않고 단지 부울을 반환하는 기능으로 해결 될 수없는 비공식 증거 :
이 결과는 부울이어야한다는 관찰이 : 정확히 하나의 1가되고, 사실인가 거짓인가?따라서 접기 커널로 사용하는 함수에는 누적 기가 반환되는 부울 누산기가 있어야합니다.
폴드의 누산기는 커널 함수의 알고리즘이 결정을 내리는 전체 상태를 캡슐화합니다. 예를 들어 함수가 변경 가능한 변수를 포함하는 어휘 범위를 사용하면 이는 부정 행위입니다.
알고리즘은 누산기에 적어도 세 가지 상태가 필요합니다. 누산기는 다른 1가 볼 때 S2로 천이되는로부터 1가 볼 S1으로 전환되는 일부 초기 S0에 있어야한다. 이 누적 기는 거짓을 표시하는 S0 및 S2, 그리고 거짓을 나타내는 S1으로 해석되어야합니다.
이론적으로 방문 항목 간 누적 기 유형을 변경할 수 있지만 정보가 없습니다. 우리는 어떤 요소가 마지막인지 알지 못합니다. 우리가 마지막 요소를보고 있다는 것을 알았다면 tri-state accumulator를 부울 값으로 소멸시켜이를 반환 할 수 있습니다. Sylwester의 대답의 두 번째 부분은 연속성을 사용하는 이유
입니다 : 다음 알고리즘 대신 직접 배에서 탈출하고 거짓을 생성 할 수 있습니다 S2로 전환의를; 누산기는 부울이 될 수 있습니다. (렉시 컬 블록 (lexical block)에서 돌아 오는 것과 같이 완전히 끊김없는 연속 대신에 훨씬 간단한 비 국지적 출구 메커니즘이 충분할 것입니다.