"조합 자"에 대한 좋은 설명 (비 수학자 용)

Question

누구나 "결합 자"(Y 결합 자 등등 및 가 아닌the company)에 대한 좋은 설명이 있습니까?

재귀 및 고차 함수를 이해하지만 강력한 이론이나 수학 배경이없는 실용적인 프로그래머를 찾고 있습니다.

(참고 : 나는 약 these things 이야기하고있는 것을)

Answer 1

이 좋은 article이다. 코드 예제는 scheme에 있지만 따르기가 어렵지 않아야합니다.

Answer 2

이론에 깊이 관여하지 않는 한, Y 결합기 을 모나드 같은 기능을 가진 깔끔한 트릭으로 간주 할 수 있습니다.

모나드를 사용하면 작업을 체인화 할 수 있으며 Y 결합기를 사용하면 자체 재귀 함수를 정의 할 수 있습니다.

파이썬은 자기 재귀 함수에 대한 지원 내장하고있다, 그래서 당신은 Y 않고 그들을 정의 할 수 있습니다

> def fun(): 
> print "bla" 
> fun() 

> fun() 
bla 
bla 
bla 
... 

fun가 fun 자체 내부에 접근, 그래서 우리는 쉽게 호출 할 수 있습니다.

그러나 파이썬 경우 다른 있었고, fun이 fun 내부 를 액세스 할 수없는 무엇인지?

> def fun(): 
> print "bla" 
> # what to do here? (cannot call fun!) 

용액 fun 인수로 fun 자체를 전달하는 것이다

> def fun(arg): # fun receives itself as argument 
> print "bla" 
> arg(arg) # to recur, fun calls itself, and passes itself along 

및 Y 가능한 것으로한다 :

가

> def Y(f): 
> f(f) 

> Y(fun) 
bla 
bla 
bla 
... 

모든 그것 자체 함수를 호출 않는다 인수로서.

(Y의 정의는 100 % 정확한지는 모르겠지만, 나는 그것이 일반적인 생각 인 것 같아요.)

Answer 3

레지날드 Braithwaite에 (일명 Raganwald)를 통해 루비 콤비에 좋은 시리즈를 쓰고있다 그의 새 블로그에서 homoiconic.

그가 (내 지식)은 Y-콤비 자체에 보이지 않는 동안, 그는 예를 들어, 다른 콤비 살펴 않습니다

• Kestrel
• Thrush
Cardinal
• Obdurate Kestrel
• 다른 기발한 조류

및 몇 가지 게시물 canuse.

Answer 4

나는 이론이 매우 짧지 만, 당신에게 도움이 될만한 상상력을 발휘할 수있는 예를 보여줄 수 있습니다. 가장 단순한 흥미로운 조합은 아마도 "테스트"일 것입니다. 그렇지 않으면 세 번째, 첫 번째 인수에 해당하는 경우

>>> test(tru,"goto loop","break") 
'goto loop' 
>>> test(fls,"goto loop","break") 
'break' 

테스트가 두 번째 인수로 평가

는 파이썬

tru = lambda x,y: x 
fls = lambda x,y: y 

test = lambda l,m,n: l(m,n) 

사용법을 알고 바랍니다.

>>> x = tru 
>>> test(x,"goto loop","break") 
'goto loop' 

전체 시스템은 몇 가지 기본 연결자로 구성 할 수 있습니다.

는

Answer 5

견적 위키 백과 (이 예제는 다소 벤자민 C. 피어스에 의해 종류와 프로그래밍 언어에서 복사) :

이 콤비는 기능 응용 프로그램을 사용하는 고차 함수 이전에 정의 된 연결자를 사용하여 인수에서 결과를 정의합니다.

이제 무엇을 의미합니까? 이것은 결합 자 (combinator)가 입력 (input)이 함수를 인수로 포함하는 함수 (출력은 입력에 의해서만 결정됨)임을 의미합니다.

이러한 기능은 어떻게 보이며 무엇을 위해 사용됩니까? 몇 가지 예를 들면 다음과 같다 :

(f o g)(x) = f(g(x))

여기

o 2 기능과 fg에 걸리는 연결자이고, 그 결과, 즉 g, f o g와 f의 조성물로서의 기능을 리턴한다.

논리를 숨기려면 결합자를 사용할 수 있습니다. 데이터 유형이 NumberUndefined 인 경우 이 숫자 값 Num x 또는 값 Undefined을 취할 수 있습니다. 여기서 x은 Number입니다. 이제 우리는이 새로운 숫자 형에 대해 덧셈, 뺄셈, 곱셈 및 나눗셈을 구성하려고합니다. 의미는 Undefined이 입력 인 경우를 제외하고는 의 경우와 동일하며 출력도 Undefined이어야하며 숫자를 0으로 나누면 출력도 Undefined이됩니다. 모두가 Undefined 입력 값에 관한 같은 논리를 얼마나

Undefined +' num = Undefined 
num +' Undefined = Undefined 
(Num x) +' (Num y) = Num (x + y) 

Undefined -' num = Undefined 
num -' Undefined = Undefined 
(Num x) -' (Num y) = Num (x - y) 

Undefined *' num = Undefined 
num *' Undefined = Undefined 
(Num x) *' (Num y) = Num (x * y) 

Undefined /' num = Undefined 
num /' Undefined = Undefined 
(Num x) /' (Num y) = if y == 0 then Undefined else Num (x/y) 

주의 사항 :

하나는 다음과 같이 지루한 코드를 작성할 수 있습니다. 부서 만 조금 더합니다. 해결 방법은 논리를 결합 자로 만들어 추출하는 것입니다.

comb (~) Undefined num = Undefined 
comb (~) num Undefined = Undefined 
comb (~) (Num x) (Num y) = Num (x ~ y) 

x +' y = comb (+) x y 
x -' y = comb (-) x y 
x *' y = comb (*) x y 
x /' y = if y == Num 0 then Undefined else comb (/) x y 

이

프로그래머가 하스켈 같은 함수형 언어에서의 사용을 소위 Maybe 모나드로 일반화 할 수 있습니다,하지만 난 거기에 가지 않을 것입니다.

Answer 6

곧 Y 결합자는 람다 식 (익명 함수)에 대한 재귀를 구현하는 데 사용되는 고차 함수입니다. 마이크 바니에 (Mike Vanier)의 기사 How to Succeed at Recursion Without Really Recursing을 확인하십시오. 제가 본이 문제에 대한 가장 실용적인 설명 중 하나입니다.

는 또한 SO 아카이브 검사 :

• What is a y-combinator?
• Y-Combinator Practical Example

Answer 7

연결자은 여유 변수와 함수이다. 다른 말로하면 결합 자 (combinator)는 함수 매개 변수에서만 함수 외부의 것에 의존하지 않는다는 것을 의미합니다. a 및 b 모두 함수 매개 변수에 바인딩되어 있기 때문에

위의 경우 합계에서

let sum a b = a + b;; //sum function (lambda) 

이 연결자이다

는 F 번호를 사용하여이 콤비의 나의 이해이다. 이 sum 사용으로

let sum3 a b c = sum((sum a b) c);; 

위 함수는 결합 된 변수 (즉, 그것은 임의의 파라미터로부터 오지 않는다)하지 않다 연결자 아니다.

우리는 단순히 매개 변수의 하나로서 합 기능을 전달하여 SUM3 연결자를 만들 수 있습니다

let sum3 a b c sumFunc = sumFunc((sumFunc a b) c);; 

이 방법 sumFunc은 가을 구속하고, 따라서 전체 함수가 콤비가입니다.

그래서 이것은 조합 자에 대한 나의 이해입니다. 반면에 그들의 중요성은 여전히 ​​나를 벗어난다. 다른 사람들이 지적했듯이, 고정 소수점 연결자는 explicit 재귀없이 재귀 함수를 표현할 수 있습니다. 나는. recusrsive 함수를 호출하는 대신 인수 중 하나로 전달되는 lambda를 호출합니다.

여기 내가 찾은 가장 이해 콤비 유도 중 하나입니다

는

http://mvanier.livejournal.com/2897.html

Answer 8

이 좋은 모양 : 나는 dreamsongs보다 뭔가 좀 더 소개 기대했다 http://www.catonmat.net/blog/derivation-of-ycombinator/