상호 재귀 함수에 대한 고정 소수점 결합 자?

Question

상호 재귀 함수의 튜플을 생성하기위한 고정 소수점 연결자가 있습니까? 나는. 나는 Y-Combinator와 같은 것을 찾고 있지만 여러 "재귀 적"* 함수를 사용하며 함수의 튜플을 반환 할 것입니까?

* : 보통의 Y-Combinator 방식으로 논증으로서 자신과 (형제 자매)를 취하도록 작성 되었기 때문에 실제로 재귀 적이 아닙니다.

Answer 1

찾고있는 생물은 Y * 조합 자입니다. this page by oleg-at-okmij.org 근거로

나는 Clojure의에 Y *를 포팅 :

(defn Y* [& fs] 
    (map (fn [f] (f)) 
    ((fn [x] (x x)) 
     (fn [p] 
     (map 
      (fn [f] 
      (fn [] 
       (apply f 
       (map 
        (fn [ff] 
        (fn [& y] (apply (ff) y))) 
        (p p))))) 
      fs))))) 

상호 재귀 함수의 고전적인 예는 그래서 여기에 짝수/홀수 인 예입니다

(let 
    [[even? odd?] 
    (Y* 
    (fn [e o] 
     (fn [n] 
     (or (= 0 n) (o (dec n))))) 
    (fn [e o] 
     (fn [n] 
     (and (not= 0 n) (e (dec n))))) 
    ) 
    ] 
    (do 
    (assert (even? 14)) 
    (assert (odd? 333)) 
    )) 

당신이 할 수있는 충분히 큰 인수를 사용하면 쉽게이 함수를 사용하여 스택을 날려 버릴 수 있으므로 스택을 전혀 소비하지 않는 완전성과 같은 예를 들어 여기에 trampolined 버전이 있습니다 :

Lambder

-)

;

(let 
    [[even? odd?] 
    (Y* 
    (fn [e o] 
     (fn [n] 
     (or (= 0 n) #(o (dec n))))) 
    (fn [e o] 
     (fn [n] 
     (and (not= 0 n) #(e (dec n))))) 
    ) 
    ] 
    (do 
    (assert (trampoline even? 144444)) 
    (assert (trampoline odd? 333333)) 
    )) 

Y * 콤비 내가 지켜봐 주시기 바랍니다, lambder.com 곧 블로그거야있는 모나드 파서, 상호 재귀 정의를 정의하기위한 매우 유용합니다

Answer 2

나는 이것에 대해 완전히 확신하지 못합니다. 나는 여전히 공식적인 증명을 찾으려하고있다. 하지만 나에게는 당신이 필요 없다고 생각됩니다. 하스켈에서 , 당신은 같은 경우 :

수정 : (A -> A) - =

주요 {X가하자의 x>은
수정 f는 =하게 X = FX합니다. .. y ...; Y = ... X ...}

X

에서 당신은 FST $ $ \ (X, Y)를 수정 =

주에 주요 다시 작성할 수 있습니다 -> (... y를 .. ., ... x ...)

그러나 내가 말했듯이 나는 이것에 대해 100 % 확실하지 않습니다.

Answer 3

다음 웹 페이지에서는 상호 재귀를위한 고정 소수점 연결자 (다변 고정점 결합 자)에 대해 자세히 설명합니다. 지금까지 가장 간단한 조합을 도출합니다 . http://okmij.org/ftp/Computation/fixed-point-combinators.html#Poly-variadic

는 참조의 편의를 위해, 여기 하스켈 (한 줄)

fix_poly:: [[a]->a] -> [a] 
fix_poly fl = fix (\self -> map ($ self) fl) 
    where fix f = f (fix f) 

여기에 간단한 polyvariadic 콤비입니다 그 것이다 계획, 엄격한 언어

(define (Y* . l) 
    ((lambda (u) (u u)) 
    (lambda (p) 
     (map (lambda (li) (lambda x (apply (apply li (p p)) x))) l)))) 

에서하세요 예제와 더 많은 토론은 웹 페이지를 참조하십시오.