콤비 네이터 줄이기 Wolfram Mathematica

Question

Mathematica에서 {S, K, I}의 일반 결합 전략을 어떻게 구현할 수 있습니까? 여기 규칙이다 : S [X] [Y] [Z] - [Y] [Z [Y]를] K [X] [Y] [Z] "을 X - 또한> X

우리가 Y 조합 자 (고정 소수점)이므로 Y [a] = a [Ya]].

그리고 우리는 예를 들어, 같은 표현을 "평가"해야한다, S [K] [K] [A] = K [A] ​​[K [A] ​​= A

가지고하는 것이 매우 중요하다 하나의 감소 단계. 따라서 그 결과는 한 번에 여러 번 적용됩니다 ..

의견을 보내 주셔서 감사합니다 !!!

Answer 1

조합자 평가의 한 단계를 수행 할 eval이라는 함수를 정의합시다. 첫째, 우리는 정확히 무엇이 하나의 단계를 구성하는지 고려할 필요가 있습니다. 임의로, 가장 왼쪽에있는 표현을 먼저 평가하고 거기에서 내부적으로 작업 할 것입니다.

ClearAll[eval] 
eval[e_] := Module[{r = eval1[e]}, r /; r =!= e] 
eval[e:f_[g_]] := Module[{r = eval[f][g]}, r /; r =!= e] 
eval[e:f_[g_]] := Module[{r = f[eval[g]]}, r /; r =!= e] 
eval[e_] := e 

규칙이 실제로 표현을 변경하는 경우에만 적용된다는 점에 유의하십시오. 이 정의의 어색함은 Mathematica가 임의로 길게 카레팅 된 인수 목록과 일치하는 패턴 표현식이 없기 때문입니다.

이제 우리는 인식 콤비, S, K 및 나에게 정의 할 수 있습니다 : 매스 매 티카가 렌더링하는

ClearAll[eval1] 
eval1[s[f_][g_][h_]] := f[h][g[h]] 
eval1[k[f_][_]] := f 
eval1[i[f_]] := f 

기호는 소문자로 여기에 주로 방법을 피하기 위해를 내장 기호 I, 허수 단위.

다른 콤비

변수로 간주하고 평가되지 않은 남아있을 것입니다 : 즉 모든 표시의이 evalAll을 정의 할 수 있습니다, 더 흥미로운 경우에

i[f] // eval 

(* f *) 

k[f][g] // eval 

(* f *) 

s[f][g][h] // eval 

(* f[h][g[h]] *) 

:

eval1[e_] := e 

이제 우리는 기본 케이스를 시도 할 수 평가 체인의 단계 :

ClearAll[evalAll] 
evalAll[e_, n_:Infinity] := FixedPointList[eval, e, n+1] // Most // Column 

s[k][k][a] // evalAll 

(* 
s[k][k][a] 
k[a][k[a]] 
a 
*) 

s[s[m][n][r]][k[a][b]][c] // evalAll 

(* 
s[s[m][n][r]][k[a][b]][c] 
s[m][n][r][c][k[a][b][c]] 
m[r][n[r]][c][k[a][b][c]] 
m[r][n[r]][c][a[c]] 
*) 

f[s[i[k]][k][g][i[f]]] // evalAll 
(* 
f[s[i[k]][k][g][i[f]]] 
f[i[k][g][k[g]][i[f]]] 
f[k[g][k[g]][i[f]]] 
f[g[i[f]]] 
f[g[f]] 
*) 

evalAll은 선택적 "count"인수를 사용하여 표시된 단계의 수를 제한합니다.

eval1[y[f_]] := f[y[f]] 

y[f] // evalAll[#, 4]& 

(* 
y[f] 
f[y[f]] 
f[f[y[f]]] 
f[f[f[y[f]]]] 
f[f[f[f[y[f]]]]] 
*) 

...하지만 SKI의 측면에서 같은 시퀀스 표현하는 더 재미 :

Module[{y = s[k[s[i][i]]][s[s[k[s]][k]][k[s[i][i]]]]} 
, evalAll[y[f], 28] 
] 

(* 
s[k[s[i][i]]][s[s[k[s]][k]][k[s[i][i]]]][f] 
k[s[i][i]][f][s[s[k[s]][k]][k[s[i][i]]][f]] 
s[i][i][s[s[k[s]][k]][k[s[i][i]]][f]] 
i[s[s[k[s]][k]][k[s[i][i]]][f]][i[s[s[k[s]][k]][k[s[i][i]]][f]]] 
s[s[k[s]][k]][k[s[i][i]]][f][i[s[s[k[s]][k]][k[s[i][i]]][f]]] 
s[k[s]][k][f][k[s[i][i]][f]][i[s[s[k[s]][k]][k[s[i][i]]][f]]] 
k[s][f][k[f]][k[s[i][i]][f]][i[s[s[k[s]][k]][k[s[i][i]]][f]]] 
s[k[f]][k[s[i][i]][f]][i[s[s[k[s]][k]][k[s[i][i]]][f]]] 
k[f][i[s[s[k[s]][k]][k[s[i][i]]][f]]][k[s[i][i]][f][i[s[s[k[s]][k]][k[s[i][i]]][f]]]] 
f[k[s[i][i]][f][i[s[s[k[s]][k]][k[s[i][i]]][f]]]]    <-- f[...] 
f[s[i][i][i[s[s[k[s]][k]][k[s[i][i]]][f]]]] 
f[i[i[s[s[k[s]][k]][k[s[i][i]]][f]]][i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]] 
f[i[s[s[k[s]][k]][k[s[i][i]]][f]][i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]] 
f[s[s[k[s]][k]][k[s[i][i]]][f][i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]] 
f[s[k[s]][k][f][k[s[i][i]][f]][i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]] 
f[k[s][f][k[f]][k[s[i][i]][f]][i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]] 
f[s[k[f]][k[s[i][i]][f]][i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]] 
f[k[f][i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]][k[s[i][i]][f][i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]]] 
f[f[k[s[i][i]][f][i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]]]  <-- f[f[...]] 
f[f[s[i][i][i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]]] 
f[f[i[i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]][i[i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]]]] 
f[f[i[i[s[s[k[s]][k]][k[s[i][i]]][f]]][i[i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]]]] 
f[f[i[s[s[k[s]][k]][k[s[i][i]]][f]][i[i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]]]] 
f[f[s[s[k[s]][k]][k[s[i][i]]][f][i[i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]]]] 
f[f[s[k[s]][k][f][k[s[i][i]][f]][i[i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]]]] 
f[f[k[s][f][k[f]][k[s[i][i]][f]][i[i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]]]] 
f[f[s[k[f]][k[s[i][i]][f]][i[i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]]]] 
f[f[k[f][i[i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]][k[s[i][i]][f][i[i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]]]]] 
f[f[f[k[s[i][i]][f][i[i[i[s[s[k[s]][k]][k[s[i][i]]][f]]]]]]]] <-- f[f[f[...]]] 
*) 

을 Y 콤비의 직접적인 표현처럼 -이 발산하는 표현에 유용