아나모르피즘

Anamorphism
다른 용도는 아나몰포시스(동음이의)를 참조하십시오.
카타모르피즘과혼동해서는 안 된다.

컴퓨터 프로그래밍에서, 무정형성은 이전의 결과에 그 기능을 반복적으로 적용함으로써 시퀀스를 생성하는 기능이다.당신은 어떤 값 A로 시작해서 그것에 함수 f를 적용하여 B를 얻는다.그리고 나서 당신은 C를 얻기 위해 F를 B에 적용하고, 어떤 종료 조건에 도달할 때까지 계속한다.무동형성은 A, B, C 등의 목록을 생성하는 기능이다.초기의 가치를 수열로 전개하는 것으로 무형식을 생각할 수 있다.

위의 비전문가의 설명은 범주 이론에서 더 공식적으로 언급될 수 있다: 동전 귀납형식의 무동형주의는 결합형의 독특한 형태론에 대한 결합형의 할당을 의미한다.이 물체들은 펼쳐지는 대로 기능 프로그래밍에 사용된다.

무아모르피즘의 범주형 이중(반대되는 것으로 알려져 있다)은 카타모르피즘이다.

기능적 프로그래밍에서의 아나몰리시스

기능적 프로그래밍에서 아나모르피즘은 코인 유도 리스트에서 펼쳐지는 개념의 일반화다.형식적으로, 무형식은 특정 유형의 결과를 핵심적으로 구성할 수 있고, 구성의 다음 단일 단계를 결정하는 함수에 의해 매개변수로 지정되는 일반적인 기능이다.

해당 데이터 유형은 functor F의 최대 고정점 ν X . F X로 정의된다.최종 합금형의 보편적 특성에 의해 다른 F-합금형 A → ν X. F X가 있다. A → F. A.따라서 A에 colbgebra 구조 a를 명시함으로써 유형 A _into_의 코인 유도 데이터 유형에서 기능을 정의할 수 있다.

예: 잠재적으로 무한 확장 가능한 목록

예를 들어, 잠재적으로 무한정 목록 유형(고정 유형 값의 요소 포함)은 픽스포인트 [값] = x X . 값 x + 1, 즉 리스트는 값과 추가 목록으로 구성되거나 비어 있다.A(의사-)Haskell-Definition은 다음과 같이 보일 수 있다.

자료 [가치를 매기다] = (가치를 매기다:[가치를 매기다])   []

그것은 functor의 고정점이다.F value, 여기서:

자료 어쩌면 a = 그냥 a   아무 것도 없어요. 자료 F 가치를 매기다 x = 어쩌면 (가치를 매기다, x)

어떤 타입인지 쉽게 알 수 있다.[value]와 이형이다. F value [value], 그리고 따라서[value]고정점이다. (또한 Haskell에서는 최소점과 최대 펑커스의 고정점이 일치하므로 유도목록은 잠재적으로 무한대의 동전 유도목록과 같다.)

리스트에 대한 무형식(당시에는 explay라고 알려져 있다)은 상태 값에서 (잠재적으로 무한히) 리스트를 작성할 것이다.일반적으로, 전개는 국가 가치를 가진다.x그리고 기능f한 쌍의 값과 새 상태를 생성하거나 목록의 끝을 표시하는 싱글톤을 생성한다.그런 다음 무정형성은 첫 번째 시드로 시작하여 목록이 지속되는지 또는 종료되는지 계산하고, 비어 있지 않은 목록의 경우 계산된 값을 무정형성에 대한 재귀 호출로 앞지른다.

하스켈의 정의, 즉 리스트에 대한 무동형성(anamorphism)이라 불리는 것.ana는 다음과 같다.

애나를 달다 :: (주 -> 어쩌면 (가치를 매기다, 주)) -> 주 -> [가치를 매기다] 애나를 달다 f stateOld = 케이스 f stateOld 의             아무 것도 없어요.                -> []             그냥 (가치를 매기다, stateNew) -> 가치를 매기다 : 애나를 달다 f stateNew

우리는 이제 아나(ana)를 사용하여 꽤 일반적인 기능을 구현할 수 있다. 예를 들어 카운트다운:

f :: 인트 -> 어쩌면 (인트, 인트) f 현재의 = 하게 하다 원스몰어 = 현재의 - 1             , in   만일 원스몰어 < 0                    , 그러면. 아무 것도 없어요.                    다른 그냥 (원스몰어, 원스몰어)

이 함수는 정수를 감소시키고 동시에 음수가 될 때까지 출력하며, 어느 지점에서 리스트의 끝을 표시한다.그에 상응하여ana f 3리스트를 계산한다.[2,1,0].

다른 데이터 구조의 무동형성

무동형성은 목록에 대한 두 번째 버전의 아나를 일반화하는 일반적인 패턴에 따라 모든 재귀 유형에 대해 정의될 수 있다.

예를 들어, 트리 데이터 구조를 위한 확장

 자료 나무 a = 잎 a   나뭇가지 (나무 a) a (나무 a)

다음과 같다

 애나를 달다 :: (b -> 어느 쪽이든 a (b, a, b)) -> b -> 나무 a  애나를 달다 비굴하게 굴다 x = 케이스 비굴하게 굴다 x 의                    왼쪽 a          -> 잎 a                    맞다 (l, x, r) -> 나뭇가지 (애나를 달다 비굴하게 굴다 l) x (애나를 달다 비굴하게 굴다 r)

재귀적 유형과 그것의 무동형성 사이의 관계를 더 잘 보기 위해, 주목하라.Tree그리고List다음과 같이 정의할 수 있다.

 뉴타입의 리스트 a = 리스트 {언컨스 :: 어쩌면 (a, 리스트 a)}   뉴타입의 나무 a = 나무 {언노드 :: 어느 쪽이든 a (나무 a, a, 나무 a))}

와의 유사점.ana이름을 바꿔서 나타나다b다음과 같은 유형:

 뉴타입의 리스트 a = 리스트 {언컨스 :: 어쩌면 (a, 리스트 a)}  애너리스트 ::       (list_a       -> 어쩌면 (a, list_a)) -> (list_a -> 리스트 a)   뉴타입의 나무 a = 나무 {언노드 :: 어느 쪽이든 a (나무 a, a, 나무 a))}  애나트리 ::       (tree_a       -> 어느 쪽이든 a (tree_a, a, tree_a)) -> (tree_a -> 나무 a)

이러한 정의로 유형 생성자에 대한 인수는 첫 번째 인수의 반환 유형과 동일한 유형을 갖는다.ana, 형식에 대한 재귀적 언급과 함께b.

역사

프로그래밍의 맥락에서 아나모르피즘의 개념을 도입한 최초의 간행물 중 하나는 에릭 메이저 등이 [1]쓴 바나나, 렌즈, 봉투, 철조망을 이용한 종이 기능 프로그래밍인데, 이것은 스퀴골 프로그래밍 언어의 맥락에 있었다.

적용들

다음과 같은 함수iterate무정형성의 예들이다. zip['a'',b'',c'라고 하는 한 쌍의 목록을 가져오고, [1,2,3]과 같이 [('a',1,1),('b',2),('c',3)] 쌍의 목록을 반환한다. Iterate어떤 물건, x, 함수 f를 그런 것들로 가져가고, f의 반복적인 적용으로부터 오는 무한 리스트, 즉 리스트[x, (f x), (f x)), (f x)), (f (f (f x)), ...]를 반환한다. 

 지퍼를 채우다 (a:로서) (b:bs) = 만일 (로서==[])    (bs ==[])   -'또는'이라는 뜻이다.                       , 그러면. [(a,b)]                       다른 (a,b):(지퍼를 채우다 로서 bs)     반복하다 f x = x:(반복하다 f (f x))

이것을 증명하기 위해, 우리는 우리의 일반적인 전개를 사용하여 둘 다 구현할 수 있다.ana, 간단한 재귀 루틴 사용:

 지퍼2 = 애나를 달다 말뚝을 뽑다 지느러미     어디에     지느러미 (로서,bs) = (로서==[])    (bs ==[])      말뚝을 뽑다 ((a:로서), (b:bs)) = ((a,b),(로서,bs))   반복2 f = 애나를 달다 (\a->(a,f a)) (\x->거짓의)

하스켈과 같은 언어에서는 추상적인 기능도 한다.fold,unfold그리고ana위에서 주어진 정의에서 본 바와 같이, 단지 정의된 용어일 뿐이다.

범주 이론의 무형식

범주 이론에서, 무정형성은 격동형성의 범주형 이중성이다(그리고 격동형은 무정형의 범주형 이중성이다).

그것은 다음과 같은 것을 의미한다.(A, 핀)이 일부 범주의 일부 엔도프터 F를 자체로 만드는 최종 F-석탄이라고 가정하자.Thus, fin is a morphism from A to FA, and since it is assumed to be final we know that whenever (X, f) is another F-coalgebra (a morphism f from X to FX), there will be a unique homomorphism h from (X, f) to (A, fin), that is a morphism h from X to A such that fin . h = Fh . f.그리고 그러한 각각의 f에 대해 우리는 독특하게 지정된 형태론 h를 ana f로 나타낸다.

즉, 위와 같이 F, A, 지느러미가 고정되어 있는 경우 다음과 같은 정의 관계를 갖는다.

표기법

문헌에서 발견되는 ana f의 표기법은[( ) 이다 사용된 괄호는 렌즈 괄호로 알려져 있으며, 그 후에 아나모르페시즘을 렌즈라고 부르기도 한다.

참고 항목

참조

  1. ^ Meijer, Erik; Fokkinga, Maarten; Paterson, Ross (1991). "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire". CiteSeerX 10.1.1.41.125. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)

외부 링크