이형 및 에프-대수

그래서 나는 종종”이형성”과”재귀 체계”라는 말을 듣습니다. 그게 뭔데?

이형(또는 취미)는 함수형 프로그래밍에서 접기 개념의 일반화입니다. 주어진 에프-대수 및 재귀 데이터 구조 이형성은 데이터 구조를 재귀 적으로 평가하여 값을 생성합니다.

에프 대수학이란? 먼저 몇 가지 코드 예제를 표시 할 수 있습니까?

설정이 그렇게 간단하지 않습니다. 식을 나타내기 위해 다음과 같은 데이터 구조가 있다고 가정해 보겠습니다:

간단한 표현식은 다음과 같이 보일 수 있습니다:

식 데이터 구조 만 갖는 것은 쓸모가 없으며 물론 결과를 평가하고 얻는 함수가 필요합니다:

이것은 이형성 일반화가 들어오는 곳입니다:

🤨, 그러나 점은 무엇 이는가? 당신은 함수에 인수를 적용?

그것은notReallyCata이기 때문입니다. 실제cata함수는 일반적이며 특정 데이터 구조 또는 평가자 함수에 의존하지 않습니다. 참조,재귀 데이터 구조를 만든 다음 그 위에 접는 것은cata가 일반화하려고하는 일반적인 패턴입니다.

좋아,그럼 진짜 범인은 어떻게 생겼어?

🤯

그래서 우리는notReallyCata로 시작했습니다. 이 클릭 할 때까지 우리는 나중에 구현을 분해합니다. 그러나 이제Expression예제를 계속하겠습니다. 첫째,우리는 형식 매개 변수를 도입하여 재귀를 제거해야합니다:

Expression에 대한 모든 참조는a형식 매개 변수로 대체되므로 데이터 구조가 더 이상 재귀적이지 않습니다.

유형 생성자 끝에F이 있는 이유는 무엇입니까?

다행 당신이 물었다-그ExpressionF가 될 수있는 힌트입니다Functor:

멋진 것은 없으며 구조를 보존하는 래핑 된 값에 일부 기능을 적용하는 것입니다.

왜 우리가 그것을 필요로하는지 확실하지 않음🤔

지금은 말이 안 되지만,조금 후에 할 것이다. 이제 식을 만드는 방법은 변경되지 않았습니다(생성자 이름 제외):

그러나 결과 유형은 다릅니다:

expr 모든 것을 단일Expression로 축소하고exprF은 표현 트리의 중첩 수준에 대한 정보를 인코딩합니다. 평가에 대해 말하면,이것은 우리가 평가를 구현하는 방법에 대해 갈 수있는 방법입니다ExpressionF:

원래evalExpr와의 주요 차이점은evalExprF(ExpressionF는 재귀 적 호출이 없다는 것입니다.). 또한 평가자가 단일 수준 표현식으로만 작업할 수 있음을 의미합니다:

그리고 이것에 컴파일하지 않을 것입니다:

단순히exprF이ExpressionF Int를 소비하고ExpressionF (ExpressionF Int)를 밀고 있기 때문입니다.

작동시키기 위해 다른 평가자를 정의 할 수 있습니다.:

당신이 깊이 중첩 된 표현식을 가지고 있다면 어떨까요?

예,임의의 중첩 식의 경우이 방법은 확장 할 수 없습니다—각 추가 중첩 수준은 특수 함수를 작성해야합니다.

이 중첩을 새로운 유형으로 일반화하는 방법이 있습니다.:

수정? 많은 작업을 수행하지 않는 재귀 데이터 구조처럼 보입니다. 그것은 어떻게 유용?

먼저 등호 앞의 식을 살펴보겠습니다. 이 매개 변수에는 종류* -> *이 있습니다. 예를 들어Int또는Bool을 제공하는Fix을 구성 할 수 없으며Maybe,List또는…ExpressionF와 같아야합니다. 이것이ExpressionF에 대한 유형 매개 변수를 도입 한 이유입니다. 다음,등호 후 우리는 기본적으로f의 값을 구성하는 식f (Fix f)형식의 단일 인수를 복용Fx단일 형식 생성자가 있습니다. Maybe의 경우Maybe (Fix Maybe)이되고 그 다음 모든 것이Fx로Fix Maybe유형으로 래핑됩니다.

형식 생성자가 형식 자체와 자체 참조와 동일한 이름을 가질 수 있기 때문에 형식 서명이 처음에는 읽기가 혼란 스럽습니다. 그러나 더 높은 차수 유형을 데이터 구조로 래핑하는 것보다 훨씬 더 많은 것은 없습니다. unfix은Fx와 반대이며,이 모든 것은Fx에 대한 패턴 일치이며 래핑 된 값을 반환합니다.

이제 표현 트리의 모든ExpressionF를Fix ExpressionF로 바꿉니다. Fx가 있거나없는 표현식을 구성 할 때의 차이를 확인하십시오-앞에 추가 할 필요가 있다는 점을 제외하고는 기본적으로 동일합니다Fx $:

‘고정’버전의 결과 유형은Fix ExpressionF이므로 재귀 표현으로 돌아 왔지만 이제 비 재귀 데이터 구조를 다시 얻으려면unfix함수를 사용해야합니다.

Fix의 이점은 무엇입니까? 원래Expression유형과 동일한 접근 방식 인 것처럼 보이지만 이제이 이상한Fix과unfix넌센스가 있습니까?

예,하지만 우리는 접는 과정을 일반화하려고 노력하고 있으며,나중에 논의 할Fix및Algebra과 같은 추가 추상화를 도입해야합니다. 나와 함께 곰,그것은 나중에 더 의미가 있어야합니다.

그래서 우리는’고정 된’데이터 구조를 가지고 있습니다.

주어진Fix ExpressionF우리가 그것으로 할 수있는 유일한 일은unfix을 생산하는 것입니다ExpressionF (Fix ExpressionF):

반환 된ExpressionF는ValueF,AddF또는MultF중 하나 일 수 있으며Fix ExpressionF를 유형 매개 변수로 사용할 수 있습니다. 패턴 매칭을 수행하고 다음에 수행 할 작업을 결정하는 것이 합리적입니다:

예,Expression에 대한 첫 번째 재귀 평가기와 동일하게 보이며unfix로 표현식을 풀 필요가 있습니다. 어차피Fix은 왜 그럴까?

여기 열쇠가 있습니다: 우리는ExpressionF에 대한 원래의’수정없는’평가자를 다시 사용하고 어떻게 든Fix ExpressionF구조 위에 배포 할 것입니다. 그래서 두 개의 인수를 복용 함수해야합니다-평가자 및 구조를 평가하는:

구현을 알아 봅시다-첫 번째 논리적 인 일은unfix을 사용하여ExpressionF를 얻은 다음evaluator:

분명히 이것은 작동하지 않습니다,evaluator은ExpressionF Int가 아니라ExpressionF (Fix ExpressionF)을 기대합니다. 그런데ExpressionF가Functor이라는 것을 기억하십니까? 우리는fmap을 사용하여 표현 트리의 내부 수준에 동일한 프로세스를 적용 할 수 있습니다:

잠시 시간을내어 무슨 일이 일어나는지 생각해보십시오:우리는 재귀 함수almostCata evaluator을fmap에 전달하고 있습니다. 현재 표현식이AddF또는MultF이면이 함수는 한 단계 더 깊게 전달되고fmap이 다시 호출됩니다. 이것은ValueF에 도달 할 때까지 발생합니다.ValueF에 매핑하면ExpressionF Int유형의 값이 반환되고 정확히evaluator함수가 수락하는 것입니다.

almostCata을 보면 실제로ExpressionF또는Int유형에 특정한 것이 없으며 이론적으로 일부 유형 매개 변수f로 일반화 될 수 있음을 알 수 있습니다. 우리가 사용하고 있기 때문에 유일한 제약 조건은f에 대한Functor인스턴스를 가져야합니다fmap:

그리고 그것은cata의 최종 버전입니다. 다음은 몇 가지 사용 예제와 함께 전체 구현입니다:

나는 그 멋진 것 같아요. 그러나 왜 상점?

범주 이론과 함수형 프로그래밍의 많은 개념은 꽤 추상적이며 때로는 특정 아이디어에 대한 즉각적인 실제 적용을 찾기가 어렵습니다. 그러나 추상화 및 일반화를 찾는 것은 임시 구현이 필요한 문제에 대한 패턴 및 우아한 솔루션을 찾는 데 유용합니다.

그건 그렇고,우리의ExpressionF -> Int함수를Functor f => (f a -> a)으로 일반화함으로써 우리는 또 다른 중요한 개념을 발견했습니다. 기본적으로 에프-대수는 펑터f,일부 유형a및 평가자 함수f a -> a의 트리플입니다. 여기서a은 다형성이 아니며Int또는Bool과 같은 구체적인 유형이어야하며 캐리어 유형이라고합니다. 모든 엔도 펑터에 대해f를 기반으로 여러 에프 대수를 만들 수 있습니다. 우리의 표현식을 예로 들어 보겠습니다-엔도 펑터f은ExpressionF,a은Int,평가자는evalExprF입니다. 그러나 우리는 캐리어 유형을 변경하고 더 많은 대수를 생성 할 수 있습니다:

그것은cata로 전달 될 수있는 다른 평가자입니다.

예,우리는 다른 캐리어 유형을 선택하고 구현을 선택하고 있습니다. 그러나 트릭이—우리가 될 우리의 캐리어 유형을 선택하여 만들 수있는 모든 평가자의 어머니가있다…Fix ExprF.

Int또는Bool로 평가하는 것은 완전히 의미가 있지만이initialAlgebra은 무엇을 평가합니까? 내 평가자의 결과로Fix이 필요한 경우는 언제입니까?

물론 당신은 당신 자신과 같은 것을 쓰지 않을 것입니다. 사실,우리는 이미 그러한 평가자에 대한 구현을 가지고 있으며 정확히Fx생성자입니다:

대기,Fx는 평가자입니까? 그건 미친 짓이야.

예,할 수있는 가장 간단한 일을 수행합니다. 다른 모든 평가자(algebra0,algebra1)는 식을 줄임으로써 일부 값을 생성했지만(예:합계 또는 연결)Fx는 데이터를 잃지 않고 식을 래핑합니다.

이것이 우리가 처음에Fix을 도입 한 이유입니다—먼저Fx를 사용하여 원래 데이터 구조를 초기 대수Fix f로 평가 한 다음cata를 사용하여’실제’평가는fmap에서 발생합니다.

범주 이론의 관점에서 볼 때,동일한 엔도 펑터를 기반으로 한 모든 대수가 범주를 형성합니다. 이 범주에는 캐리어 유형을Fix f로 선택하여 만든 초기 대수 인 초기 객체가 있습니다. 당신이 깊은 범주 이해를 얻으려면 내가보기 엔 체크 아웃하는 것이 좋습니다 바토시 밀레프스키에 의해 몇 가지 좋은 블로그 게시물이 있습니다.

아직 이해하기가 꽤 어렵습니다.

개념을 완전히 이해하지 못한다고 생각합니다.Fix과cata를 스스로 다시 구현하고 가능한 데이터 구조와 대수에 대해 생각해보십시오. 예를 들어,String는 재귀 적으로 표현 될 수 있으며(String의Char머리와 꼬리),문자열의length는cata로 계산할 수 있습니다. 여기에 추가 읽기에 대한 몇 가지 훌륭한 리소스입니다:

• 이해 에프 대수와 약간 다른 에프 대수 바르토시 밀레프스키
• 크리스 존스
• 롭 노리스의 픽스 포인트 유형을 사용한 순수 함수형 데이터베이스 프로그래밍
• 하스켈 위키의 이형성
• 자레드의 실제 재귀 체계 토빈