효모형성(컴퓨터과학)

컴퓨터 과학, 특히 기능 프로그래밍에서 히로모르피즘은 재귀적 함수로서, 무아모르피즘의 구성(처음에는 결과 집합을 형성하며, '언폴딩(unfolding)'이라고도 한다)에 이어 카타모르피즘(이러한 결과를 최종 반환 값으로 접는다)에 해당한다.이 두 개의 재귀 계산을 하나의 재귀 패턴으로 융합하면 중간 데이터 구조를 구축할 수 없다.이것은 프로그램 최적화 전략인 삼림 벌채의 한 예다.관련 유형의 기능은 변성인데, 변성형(catamorphism)은 무동형(anamorphism)이 뒤따른다.

형식 정의

$효모형{\displaystyle }$ h${\displaystyle }$: ${\displaystyle A}$→ C ${\displaystyle h:$$A\rightarrow C}$은(는) 별도의 무동형 및 강직형 부분으로 정의할 수 있다$$.

아나모르픽 부분은 ${\displaystyle \mathrm{단항함수}}$ $g{\displaystyle }$: A${\displaystyle }$→ ${\displaystyle B}$ ${\displaystyle \times }$ ${\displaystyle A}$ ${\displaystyle g:$$반복{\displaystyle }$ 적용("접지 해제")에$$ 의해 B ${\displaystyle B}$의 요소 목록을 정의하는$$ $A\오른쪽$ 화살표 $B\time$ A$}$ 및 조건 $p{\displaystyle }$ :${\displaystyle }$A${\displaystyle }$→ ${\displaystyle \text{Boolean}}$ ${\$종료 조건을 제공하는$$ $A\rightarrow$ {\$text{$Boolean$}.$

강직형 부분은 접힘에 대한$$ 초기 값 $c{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle C}$ ${\displaystyle c\in$ C$}$과 이항 연산자${\displaystyle }$operator${\displaystyle }$: ${\displaystyle B}$ ${\displaystyle \times }$ C${\displaystyle }$→ ${\displaystyle C}$ ${\displaysty \oplus$:접는 데 $사용$된 B$\time C\rightarrow C}$

따라서 hylomphism.

${\displaystyle h\,a={\displaysty}c&{\mbox}c&{\mbox{pox}{{pox}}만약에 }p\,a\,\,where\,(b,a')=g\,a&{\mbox}\end{case}}}}}}}$

정의될 수 있다($p{\displaystyle }$ ${\displaystyle p}$ $$& $g{\displaystyle }$ ${\displaystyle g}$의 적절한 정의 필요).$$

표기법

위의 hylomphism의 약칭은 $h{\displaystyle }$=${\displaystyle }$[${\displaystyle }$( ${\displaystyle c}$ ,${\displaystyle \oplus }$)${\displaystyle }$,${\displaystyle }$( ${\displaystyle g}$, ${\displaystyle p}$) ${\displaystyle ]}$ ${\displaystyle h=[!][![[(c,\oplus$ ), $(g,p)]\]}$이다$.$

실생활에서의 히로모르프리즘

목록

목록은 선형 계산 과정을 자연스럽게 반영하기 때문에 일반적인 데이터 구조다.이러한 프로세스는 반복적인 (반복적인) 함수 호출에서 발생한다.따라서 이 목록을 단일 결과로 축소하기 전에 중간 결과의 임시 목록을 생성할 필요가 있는 경우가 있다.

흔히 접하는 효모형의 한 예는 정론적 요인함수다.

요인의 :: 정수 -> 정수 요인의 n     n == 0 = 1     n > 0 = n * 요인의 (n - 1) 

앞의 예(하스켈, 순기능 프로그래밍 언어)에서 주어진 유효한 입력에 적용되는 이 함수가 리스트에 선형 콜 트리의 이형성을 발생시킨다는 것을 알 수 있다.예를 들어, n = 5를 지정하면 다음과 같은 결과가 나온다.

요인 5 = 5 * (계속 4) = 120 요인 4 = 4 * (계속 3) = 24 요인 3 = 3 * (계속 2) = 6 요인 2 = 2 * (계속 1) = 2 요인 1 = 1 * (계속 0) = 1 요인 0 = 1 요인 0 = 1

이 예에서 프로세스의 무아모르픽 부분은 목록에 이형화된 콜 트리의 생성이다.[1, 1, 2, 3, 4, 5]. 그렇다면 이 리스트의 요소들의 산출물의 계산은 격동이다.Thus, in the notation given above, the factorial function may be written as ${\displaystyle {\text{factorial}}=[\![(1,\times ),(g,p)]\!]}$ where ${\displaystyle g\ n=(n,n-1)}$ and ${\displaystyle p\ n=(n=0)}$.

나무들

그러나 '하이로모르퍼시즘'이라는 용어는 리스트의 이형성에 따라 작용하는 기능에만 적용되는 것은 아니다.예를 들어, hylopphism은 또한 그 후에 붕괴되는 비선형 콜 트리를 생성함으로써 정의될 수 있다.그러한 함수의 예로는 피보나치 수열의 n항을^th 생성하는 함수가 있다.

 피보나치 :: 정수 -> 정수  피보나치 n      n == 0 = 0      n == 1 = 1      n > 1 = 피보나치 (n - 2) + 피보나치 (n - 1) 

트리를 호출하다fibonacci 4.

이 함수는 유효한 입력에 다시 적용되며 비선형 호출 트리를 생성한다.오른쪽 예에서, 콜 트리는 다음을 적용하여 생성된다.fibonacci입력에 따라 기능하다.4.

이번에 아나몰피즘은 콜 트리가 잎사귀 노드가 있는 나무에 이형화된 생성이다. 0, 1, 1, 0, 1그리고 이 잎의 마디들의 총합인 강직성.

참고 항목

• 형태론
• F-알게브라의 형태론
  • 초기 대수학에서 대수학으로: 카타모르피즘
  • 합금에서 최종 합금까지: 아나모르피즘
  • 강형사상 확장: 파라모프리즘
  • 아나모르피즘 사상의 확장:아포모르피즘

참조

• Erik Meijer; Maarten Fokkinga; Ross Paterson (1991). "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire" (PDF). pp. 4, 5.

외부 링크

• 하스켈의 율로모르페시즘
• 하스켈의 더 많은 율로모르프스