2016-08-11 7 views
6

Y - 연결자

내가 Y에 대해 배우려고 노력 했어요 - 콤비 (즉에 대한 설명뿐만 아니라 아름다운 것)이 wiki에서 예를 건너 왔어요. 주제에 대한 깊이있는 설명은 하스켈이나 파이썬에서 크게 감사 할 것입니다. Pleaaase! Y-Combinator를 사용하는 방법; 왜이 무한 재귀는 9를 반환합니까?

코드

fix :: (a -> a) -> a 
fix f = f (fix f) 

문제

호출되는 함수 fix 반환 fix(\x -> 9)에 적용되고 난 아무 단서 이유가 없다 9; 스택을 따라 가면 f(f ... (fix f) ...)을 시각화합니다. 모든

>> fix (\x -> 9) 
>> 9 

답변

11

첫째 : 당신이 가지고있는 fix 기능은 직접 재귀로 구현 된 고정 소수점 콤비 입니다. Y 연결자는 특정 고정 소수점 결합 자로 에는 구문 재귀가 필요하지 않습니다.fix과 같지만 다른 방식으로 수행했습니다.

궁금하신 분은 how to implement the Y combinator in Haskell 여기를 참조하십시오. 정적 유형의 경우 약간 까다 롭습니다. 작동하려면 재귀 유형이 필요합니다.

두 번째 질문에 대해서는 게으름 덕분에 코드가 작동합니다. (\ x -> 9)에 적용하면 무엇이든, 그 일은 결코 평가받지 못할 것입니다. 이 시도 :

λ> (\ x -> 9) (error "fail") 
9 

fix의 정의에 재귀 호출이 포함되어 있습니다. 당신이 fix의 정의에 (\ x -> 9)와 가장 바깥 f를 교체 할 때 어떻게되는지 봐 : error와 버전과 정확히 같은 논리에 따라

(\ x -> 9) (fix f) 

, 재귀 호출 을 평가 결코 극복하고 그냥 가져 a 9 out.