개체를 가리키는 Visitor 모드는 F 개수에 따라 다릅니다.μChurch encoding을 통한 재귀성

어딘가에서 대상(OOP)을 위한 Visitor 모드에 대해 이야기했기 때문에 함수형 프로그래밍의 필기용을 정리하고 싶습니다.
(트위터에 쓰면 너무 길어요. 여기 정리해주세요)
2021/01/10 EDIT:
Church(Boehm – Berarducci)는 인코딩과 Vister 모드의 구체적인 사례에 대해 쉽게 이해할 수 있으니 참고하십시오.

Haskell for all: The visitor pattern is essentially the same thing as Church encoding

개요

OOP의 Visitor 모드는 함수형 프로그래밍에서 F 대수를 기반으로 한다μChurch encoding을 통해 재귀속
즉
정보

F代数 = F a -> a 

μChurch encoding 반복
응용 함수

μF = ∀a. (F a -> a) -> a

의 결과a에 해당한다.

해설

OOP이든 함수형이든 회귀 계산으로서'귀속된 데이터 구조'를 어떻게'해석'하여 계산 결과를 냅니까?그러니까
각자의 프로그래밍 스타일 중의'문법','해석','결과'에 관하여

OP(Visitor)에서

문법=문법 인터페이스와 실현

e.g. interface Node , class Node1 , class Node2

설명=설명인터페이스와실현

e.g. Visitor<A> = (visit1: Node1 -> A, visit2: Node2 -> A)

결과 = accept→visit→accept→.상호 귀속 계산

함수 유형

문법=닫힌것과 e.g.data F x = Node1' | Node2' x x

해석=F대수F a -> a

결과=fold(μF와 F 대수)의 귀속 계산

여기서 Visitor의 유형에 주목하면 이 사용형의 성질(보편성)
쓸 수 있다(Node1 + Node2) -> A.(+는 Either 직선 및 유형)
또 Visitor 모드에 따른 계산class Node1에는 Node2의'귀속 구조'외에 계산 결과를 얻는'해석'도 포함됐다.
이것을 함수 형식으로 해석하면 Recursion Scheme라는 기술을 사용하여 다음 3가지 기본 요소로 분해할 수 있습니다.

귀속자체=μ

귀속문법 제외=닫기F

귀속된 문법의 해석이 포함되지 않음=F대수F a -> a

Recursion Scheme에 따르면F 적용μ 내용을 μF로 쓰면 귀속문법Node1 + Node2과 같다.즉Visitor = μF -> A, 문법μF에 대한 응용 해석Visitor을 보면 계산 결과A를 얻을 수 있다.
이는 초반 개요에서 F대수F a -> a와 μF를 사용해 얻은 이야기a와 같다.
사실 후자의 이 계산은 일반적으로Catamorphism(권적)이라고 하는데 다음과 같은 계산을 한다.

-- NOTE: fold, reduce とも呼ばれる
catamorphism : (F a -> a) -> μF -> a

이걸 그림으로 표현하면 이런 느낌이에요.

참조: Recursion Schemes - haskell-shoen

여기서 궁금한 것은 F a -> a와μF가 구체적으로 어떻게 작용하는가?그러니까
여기는 Church encoding의 등장 시간입니다.
Church encoding에 대한 자세한 설명은 이번 생략에서 귀속적인 데이터형μF에 대해 내부에서 원형catamorphism의 기능에 따라 함수화(인코딩)하면 다음과 같이 쓸 수 있다μF.

μF = ∀a. (F a -> a) -> a

이후 F대수(해석)F a -> a와 문법μF = (F a -> a) -> a의 작용에 대해 간단한'함수 응용'을 통해a를 얻을 수 있다.
Visitor 모드에서 구문μF은 해석Visitor에 적용되지만 Church encoding을 사용합니다.μ귀속에서 함수로 인코딩된 문법μF은 함수 응용 측면에(F대수 기반의 해석F a -> a에 완전히 상반되어 흥미롭다.

총결산

OP의 Visitor 모드는 "문장 구조의 해석"을, 함수 유형은μ역귀와 F 대수(μF, F a -> a)가 분해되어 Church encoding→응용 함수와 같다.

P.S.

P.S.Visitor 모드에서는 구문Node으로서 Visitor=해석된 인터페이스를 알아야 하지만 함수 유형은 방향에 의존할 필요가 없습니다.
P.S. 이 이슈와 관련해 Expression Problem 등 장단점이 자주 나오지만, 함수형 프로그래밍에서 Open Union(Extensible variants)을 가져오면 피할 수 있다.
P.S. 요즘 컴백하는 기분.