"Combinators"에 대한 좋은 설명

"Combinators"에 대한 좋은 설명 (수학자가 아닌 경우)

---

누구든지 "조합기"( 회사가 아닌 Y 조합기 등)에 대한 좋은 설명을 얻었 습니까?

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

(참고: 나는 이러한 것들 에 대해 이야기하고 있습니다 )

---

이론에 깊이 빠져 있지 않다면 Y 결합자를 모나드와 같은 기능을 갖춘 깔끔한 트릭으로 간주할 수 있습니다.

Monad를 사용하면 작업을 연결할 수 있고 Y 결합자를 사용하면 자기 재귀 함수를 정의할 수 있습니다.

Python에는 자체 재귀 함수에 대한 지원이 내장되어 있으므로 Y 없이 정의할 수 있습니다.

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

> fun()
bla
bla
bla
...

funfun자체 내부에서 액세스 할 수 있으므로 쉽게 호출할 수 있습니다.

그러나 Python이 다르고 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% 맞는지는 모르겠지만 일반적인 생각이라고 생각합니다.)

---

Reginald Braithwaite(일명 Raganwald)는 자신의 새 블로그인 homoiconic 에서 Ruby의 결합자에 대한 훌륭한 시리즈를 작성했습니다 .

그는 (내가 아는 한) Y-combinator 자체를 보지 않지만, 예를 들어 다음과 같은 다른 결합자를 봅니다.

• 황조롱이
• 개똥 지빠귀
• 추기경
• 완고한 황조롱이
• 다른 기발한 새들

당신이 방법에 대한 몇 가지 게시물 수 사용 을.

---

인용 위키피디아:

결합자는 함수 응용 프로그램과 이전에 정의된 결합자를 사용하여 인수의 결과를 정의하는 고차 함수입니다.

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

그러한 기능은 어떻게 생겼으며 무엇을 위해 사용됩니까? 여기 몇 가지 예가 있어요.

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

여기서 o2 개 함수에 소요 연결자이다 f하고 g, 조성물 및 결과를 반환하는 함수 f로를 g즉이 f o g.

결합자를 사용하여 논리를 숨길 수 있습니다. 우리는 데이터 유형이 말 NumberUndefined, NumberUndefined숫자 값을 취할 수 Num x또는 값 Undefined, xA는입니다 Number. 이제 이 새로운 숫자 유형에 대해 더하기, 빼기, 곱하기 및 나누기를 구성하려고 합니다. 시맨틱이들에 대한 것과 동일한 Number경우를 제외하고 Undefined는 입력이며, 출력은이어야 Undefined하고 숫자로 나눈 0출력도이다 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)

모두가 Undefined입력 값 과 관련하여 동일한 논리를 갖는 방법에 주목하십시오 . 나눗셈만 조금 더 하면 됩니다. 해결책은 논리를 결합자로 만들어 추출하는 것입니다.

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프로그래머가 Haskell과 같은 함수형 언어에서 사용하는 소위 모나드 로 일반화할 수 있지만 거기에는 가지 않겠습니다.

---

결합자는 자유 변수 가 없는 함수입니다 . 이는 무엇보다도 결합자가 함수 외부의 것에 의존하지 않고 함수 매개변수에만 의존한다는 것을 의미합니다.

F#을 사용하여 이것은 결합자에 대한 나의 이해입니다.

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

상기 경우 모두 합계 때문에 연결자이다 a및 b함수 파라미터에 결합된다.

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

위의 함수는 sum바운드 변수가 아닌(즉, 매개변수에서 가져오지 않은) 를 사용하므로 결합자가 아닙니다.

sum 함수를 매개변수 중 하나로 전달하여 sum3을 결합자로 만들 수 있습니다.

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

이 방법 sumFunc은 바인딩 되어 있으므로 전체 함수가 결합자입니다.

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

다음은 내가 찾은 가장 이해하기 쉬운 결합자 파생물 중 하나입니다.

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

---

이것은 좋은 것 같습니다 : http://www.catonmat.net/blog/derivation-of-ycombinator/

---

나는 이론에 대해 매우 부족하지만 당신에게 도움이 될 수 있는 나의 상상력을 펼칠 수 있는 예를 당신에게 줄 수 있습니다. 가장 간단한 흥미로운 결합자는 아마도 "테스트"일 것입니다.

파이썬을 알기를 바랍니다

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

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

용법:

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

test는 첫 번째 인수가 참이면 두 번째 인수로 평가하고, 그렇지 않으면 세 번째 인수로 평가합니다.

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

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

(이 예제는 Benjamin C. Pierce의 유형 및 프로그래밍 언어에서 어느 정도 복사되었습니다.)

---

이것은 좋은 기사 입니다. 코드 예제는 체계에 있지만 따르기 어렵지 않아야 합니다.

---

간단히 말해서 Y 결합자는 람다 식(익명 함수)에서 재귀를 구현하는 데 사용되는 고차 함수입니다. Mike Vanier의 How to Succeed at Recursion Without really Recursing 기사를 확인하십시오. 이것은 내가 본 문제에 대한 가장 실용적인 설명 중 하나입니다.

또한 SO 아카이브를 스캔하십시오.

• y-combinator 란 무엇입니까?
• Y-Combinator 실제 예

ReferenceURL : https://stackoverflow.com/questions/97637/good-explanation-of-combinators-for-non-mathematicians