흥미 위주로 알아보는 일반 재귀 함수

컴퓨터과학에서 이론적으로 다루는 계산 모형이 튜링 기계 말고 다른 것도 있다는 것을 알고 계셨나요?

처음 이 글을 작성했을 때는 어쩌다가 일반 재귀 함수라는 개념을 마주치게 되었는지 구질구질하게 모두 적었었는데, 핵심만 요약하자면 어쩌다가 위키백과에서 Model of computation 항목을 읽게 되었고 제가 몰랐던 수많은 계산 모형을 마주치게 되었다는 것이라고 하겠습니다. 아마 튜링 기계 말고도 람다 계산을 들어보신 분들이 계실 텐데, 튜링 완전하지 않은 것을 포함하면 위키백과에 등재된 계산 모형이 최소 18개나 되리라고 예상하셨던 분은 없을 것이라고 생각합니다. (저도 깜짝 놀랐습니다.)

이 글에서는 지금까지 제시되었던 수많은 계산 모형 중 일반 재귀 함수^{general recursive functions}를 다룹니다. 한국어 위키백과에는 μ-재귀 함수^{μ-recursive functions}라는 제목으로 등재되어 있고 재작성 이전에도 이 용어를 사용했지만, 이번에는 영문 용어를 그대로 번역해 사용합니다. 제가 확실히 이해하고 있는 개념이 아니기 때문에 잘못된 내용이 있을 수 있습니다.

참고로 해당 위키백과 항목에 등재되어 있는 계산 모형을 모두 적으면 다음과 같습니다. 특히 제가 어느 정도 알고 있는 것은 부연 설명을 적고, 튜링 완전하다고 확실히 확인한 것은 굵게 강조했습니다.

• 순차형 모형
  • 유한 상태 기계^{finite-state machines}
    • 어떤 계가 가질 수 있는 유한 개의 상태와 그 상태 사이의 전이로 계의 동작을 나타냅니다. 형식언어론에서의 정규 언어와 동등한 표현력을 가집니다.
  • 포스트 태그 기계^{Post tag machines} ( > 1일 경우 튜링 완전)
  • 푸시다운 오토마타^{pushdown automata}
    • 유한 상태 기계와 비슷하지만 추가로 스택을 사용할 수 있습니다(스택에 밀어넣는다고 해서 푸시다운이라고 합니다). 비결정적 푸시다운 오토마타는 형식언어론에서의 문맥 무관 언어와 동등한 표현력을 가집니다.
  • 레지스터 기계^{register machines}
  • 튜링 기계^{Turing machines}
    • 굳이 설명이 필요하지 않을 것 같습니다.
  • 결정 트리 모형^{decision tree model}
    • n지 선택의 연속으로 생각할 수 있는 알고리즘을 결정 트리로 표현할 수 있습니다. 알고리즘의 시간 복잡도 분석에도 사용할 수 있으며, 대표적으로 비교에 기반한 정렬이 미만의 시간 복잡도를 가질 수 없다는 증명에도 활용됩니다.
• 함수형 모형
  • 추상 재작성 시스템^{abstract rewriting system}
  • 조합자 논리^{combinatory logic}
    • 정해진 수의 인자를 제한된 방법으로 조작하는 정해진 조합자^combinator만을 조합해 연산을 표현합니다. 제한된 버전의 람다 계산으로 생각할 수 있으며, 와 의 두 조합자만으로 튜링 완전함이 알려져 있습니다.
  • 일반 재귀 함수^{general recursive functions}
    • 이 글의 주제입니다.
  • 람다 계산^{lambda calculus}
    • 인자를 직접 조작할 수 없고 다른 함수에 전달만 할 수 있는 순수 단항 함수만을 조합해 연산을 표현합니다. 함수형 프로그래밍의 기초가 되는 모형으로, 컬리 기술 블로그에서 한국어로 다룬 바가 있습니다.
• 동시성 모형
  • 행위자 모형^{actor model}
  • 세포 자동자^{cellular automata}
    • 격자 위의 '세포'들이 인접한 세포들과 영향을 주고받아 상태를 전이시킵니다. 잘 알려진 세포 자동자 중 튜링 완전한 것으로는 콘웨이의 생명게임^{Conway's Game of Life}, 와이어월드^Wireworld, 특정한 초기 상태에서 시작하는 Rule 110 등이 있습니다.
  • Interaction nets
    • 하나 이상의 포트가 있는 여러 종류의 노드와 노드 사이를 잇는 회로로 연산을 표현합니다. 두 노드가 주 포트^{principal port}로 연결되어 있으면 정해진 규칙에 따라 회로가 변형되며, 모형의 특성상 병렬 처리가 쉽습니다. 조합자 논리와 비슷하게 세 종류의 노드만으로 튜링 완전함이 알려져 있습니다.
  • Kahn process networks
  • 논리 회로^{logic gates}
  • Petri nets
  • 프로세스 계산^{process calculi}
    • 동시성을 띠는 계를 람다 계산과 비슷한 방식으로 형식화하는 여러 가지 모형을 가리키는 개념입니다.

원시 재귀 함수

일반 재귀 함수를 통째로 이해하기 전에 더 작은 개념인 원시 재귀 함수^{primitive recursive functions}를 먼저 다루어 보겠습니다. 이 계산 모형에서는 세 종류의 대상을 다룹니다.

• 0 이상의 정수로 값을 나타냅니다. 이 글에서는 그냥 '자연수'라고 하겠습니다.¹
• 세 가지 기본 함수로 기초적인 연산을 나타냅니다.
  • 모든 함수는 순수함수이며, 자연수를 입력받아 자연수를 출력합니다.
  • 함수마다 입력으로 받는 자연수의 개수는 정해져 있습니다. 자연수 에 대해 매개변수가 개인 함수를 변수^n-ary함수라고 합니다.
• 여러 함수를 조합하는 연산자로 복잡한 연산을 나타냅니다.

다음에 해당하는 함수만을 원시 재귀 함수라고 합니다. 대문자는 함수, 소문자는 자연수를 나타냅니다.

• 기본 함수
  • 상수 함수
    • 다변수 버전의 상수함수입니다. 개의 매개변수를 받고 항상 을 함숫값으로 가집니다.
  • 다음 수 함수
    • 매개변수에 1을 더하는 1변수함수입니다.
  • 사영 함수/항등 함수 ()
    • 다변수 버전의 항등함수입니다. 개의 매개변수를 받고 그 중 번째 매개변수를 함숫값으로 가집니다.
• 기본 함수를 다음 연산자를 사용해 유한 번 조합한 것
  • 합성 연산자
    • 다변수 버전의 함수 합성입니다. 변수함수 과 개의 변수함수 에 대해 변수함수 은 다음과 같이 계산합니다.
    • 일 때는 오른쪽 피연산자의 괄호를 생략하기도 합니다.
  • 원시 재귀 연산자 (로, rho)
    • 제한적인^bounded 반복을 수행하는 연산자입니다. 변수함수 와 변수함수 에 대해 변수함수 는 다음과 같이 계산합니다.

세 가지 기본 함수는 설명하지 않고 넘어가도 될 것이라고 생각합니다. 두 가지 연산자는 바로 이해하기 쉽지 않을 수 있으니 부연 설명을 해보겠습니다.

합성 연산자

다변수 버전의 함수 합성입니다. 변수함수 과 개의 변수함수 에 대해 변수함수 은 다음과 같이 계산합니다.

학교에서 함수를 배울 때 아마 함수의 합성()을 같이 배울 것입니다. (설마 그동안 교육과정에서 빠지지는 않았겠죠?) '여러 가지 작업을 순차적으로 한다'는 것을 표현하는 것은 정말 중요하기 때문에 원시 재귀 함수에서도 합성 연산자를 포함하고 있습니다.

의 양쪽 피연산자가 1변수함수일 때는 보통의 함수 합성이 됩니다.

오른쪽 피연산자를 다변수함수로 일반화하는 것까지도 역시 문제가 없습니다.

그런데 왼쪽 피연산자를 확장하려고 하면 문제가 발생합니다. 은 변수함수인데, 위의 식을 그대로 두면 에 전달할 인자가 하나밖에 없게 됩니다.

그렇다고 해서 을 모든 인자에 똑같이 복제하면 모든 매개변수의 값이 똑같아지기 때문에 다변수함수를 쓰는 이유가 없어집니다.

그 대신 원시 재귀 함수 모형에서는 오른쪽 피연산자로 오는 함수 개수를 왼쪽 함수의 항수에 맞추는 해결책을 사용합니다. 이렇게 하면 인자의 개수도 일치하고 각 매개변수에 서로 다른 인자를 전달할 수도 있습니다.

그렇게 쓸모가 있는 것은 아니지만, 왼쪽 피연산자로 0변수함수가 오는 것도 가능합니다. 기존 문헌에서는 이 경우를 어떻게 표기하는지 모르겠는데, 이 글에서는 합성한 함수의 항수를 알 수 있도록 오른쪽 피연산자의 괄호 안에 을 표기합니다.

이론은 충분히 다뤘으니 합성 연산자를 사용해 간단한 함수를 만드는 예시를 살펴보겠습니다.

• 2를 더하는 함수:
• 3을 더하는 함수:
• 함숫값이 1인 2변수 상수 함수:
  • 위와 같은 원리로 , , 만을 사용해 임의의 을 만들 수 있기 때문에 일부 자료에서는 기본 함수에서 을 빼고 만 포함하는 경우도 있다고 합니다.
• 두 매개변수의 자리 바꾸기:
• 빈 매개변수 자리에 기본값 넣기:

물론 지금 할 수 있는 것은 원하는 자연수 만들기, 정해진 값만큼 더하기, 자리 바꾸기뿐이기 때문에 이 이상 할 수 있는 것이 별로 없습니다. 그 대신 다음으로 알아볼 연산자는 합성보다 훨씬 강력합니다.

원시 재귀 연산자

제한적인^bounded 반복을 수행하는 연산자입니다. 변수함수 와 변수함수 에 대해 변수함수 는 다음과 같이 계산합니다.

원하는 값()에 원하는 함수()를 매개변수로 주어지는 횟수()만큼 반복하고 싶다면 연산자를 어떻게 정의하는 것이 좋을까요? 아마 이런 정의가 가장 먼저 떠오르지 않을까 싶습니다. 아직 진짜 가 아니기 때문에 아래 첨자를 붙였습니다.

그런데 위와 같은 방식으로 정의하면 가능한 모든 에 대해 규칙이 하나씩, 즉 무한개 있는 꼴이니 예쁘지 않습니다. 다행히 다음 방법을 사용해 규칙을 2개로 줄일 수 있습니다.

첫 매개변수에 아무 자연수를 대입하면 첫 번째 정의와 같은 결과가 나온다는 것을 알 수 있습니다. 사실은 이것만으로 이미 진짜 와 똑같은 표현력을 가짐이 알려져 있지만, 사용의 편의성을 위해 몇 가지 기능을 추가해 보겠습니다.

우선 일 때의 베이스 케이스를 자체가 아니라 에 베이스 케이스 함수()를 적용한 값이 되도록 일반화할 수 있습니다.

이제 매개변수 가 항상 함수에 인자로 전달되기 때문에 매개변수의 개수를 원하는 만큼 늘릴 수 있습니다.

마지막으로 함수를 보다 쉽게 작성할 수 있도록 와 를 에도 전달하도록 수정할 수 있습니다.

바로 이 가 원시 재귀 연산자 입니다. 지금까지의 설명을 요약하자면 는 일종의 for문으로 생각할 수 있습니다. JavaScript로 표현하면 다음과 같습니다.

const rho = (B, R) => (n, ...args) => {
	let acc = B(...args);
	for(let i = 0; i < n; i++)
		acc = R(i, acc, ...args);
	return acc;
};

참고로 설명에서 사용한 함수 이름 와 은 각각 Base의 B, Recursive의 R입니다.

원시 재귀 함수의 예시

원시 재귀 연산자를 사용하는 가장 간단한 예시로는 덧셈을 들 수 있겠습니다. 보통 페아노 공리계를 사용하는 산술 체계에서는 덧셈을 다음과 같이 정의합니다.

이 정의를 그대로 로 옮길 수 있습니다.

로 옮기면 다음과 같습니다.

이 식이 실제로 성립하는지 2 + 7을 넣어서 확인해 보겠습니다.

정말 원하는 값이 나왔네요!

곱셈도 비슷하게 정의할 수 있습니다.

이대로 거듭제곱도 정의할 수 있지만, 방향을 조금 돌려 봅시다. 재귀 연산자를 사용할 때 간과하기 쉬운 점은 재귀를 분기로도 사용할 수 있다는 점입니다. 예를 들어서 Haskell에서 자료구조가 비어 있는지 확인하는 함수인 null은 다음과 같이 정의되어 있습니다. (foldr이 원시 재귀 연산자 역할을 합니다.)

null :: Foldable t => t a -> Bool
null = foldr (\_ _ -> False) True

베이스 케이스는 True이고, 재귀 함수는 인자를 무시하고 False를 반환하는 함수입니다. 즉, 원소가 없을 때는 \_ _ -> False를 단 한 번도 적용하지 않기 때문에 True, 원소가 있을 때는 \_ _ -> False가 적용되어 있기 때문에 그 아래에 뭐가 몇 층으로 있든 상관없이 False가 됩니다.

이 원리를 똑같이 응용해서 원시 재귀 함수로도 주어진 인자가 0인지 확인할 수 있습니다.

아니면 다음과 같이 일반적인 분기도 구현할 수 있습니다. 0은 거짓, 나머지는 참으로 판정합니다.

예를 들어서 , 입니다.

위와 같이 함수를 조합해서 사칙연산, 나머지, 거듭제곱, 비교, 제곱근, 소수 판정(!)과 번째 소수(!!) 등의 연산을 구현할 수 있다고 합니다. 원시 재귀 함수로 자연수 이외의 대상을 조작하고 싶다면 원하는 대상에 괴델 수를 부여해 그 수를 통해 간접적으로 조작하는 등의 방법을 사용할 수 있습니다.

굳이 왜 이렇게까지 하나요?

글을 재작성하기 전에는 솔직히 원시 재귀 함수 모형을 보면서 '람다 계산처럼 함수에 함수 전달도 못 하는 경직된 모형'이라는 인상을 받았는데, 좀 더 조사해보고 나니 이 모형은 수학책에 나오는 특정한 꼴의 재귀적인 함수 정의를 형식화한 것으로도 이해할 수 있었습니다. 위에서 소개했던 덧셈의 정의를 다시 예로 들어 보겠습니다.

위에서는 아무런 설명 없이 이 두 규칙을 그대로 로 옮겼는데, 잘 생각해보면 위의 정의와 원시 재귀 정의 사이에 연관성이 있다는 것을 알 수 있습니다.

• 기본 함수 는 좌변에 주어진 변수에 대응한다.
  • 2번째 줄에서 재귀적으로 주어지는 도 여기에 포함됩니다.
• 연산자 는 인 경우와 인 경우로 나누어서 정의하는 것에 대응한다.

이외에도 다른 식을 원시 재귀 함수로 옮긴 것들을 살펴보면 다음의 연관성을 찾아볼 수 있습니다.

• 기본 함수 는 상수에 대응한다.
• 연산자 는 함수의 중첩 호출에 대응한다.

이런 원리를 이해한다면 원시 재귀의 규칙을 만족하는 수식을 기계적으로 원시 재귀 정의로 바꿀 수 있습니다. 예를 들어 이 식을 변환해 볼까요? (과 는 과 로 주어져 있다고 가정합니다. 이 두 함수는 원시 재귀로 구현할 수 있습니다.)

1. 왼쪽 인자에 대해 분기하므로 를 사용한다.
2. 왼쪽 인자가 0인 경우에는 함숫값이 이므로 를 사용한다.
   • 의 규칙에 의해 현재 쓸 수 있는 인자는 이므로 입니다.
3. 왼쪽 인자가 0이 아닌 경우에는 함숫값이 함수이므로 를 사용한다.
4. 의 왼쪽 인자는 함수이므로 를 사용한다.
5. 의 인자는 이전 단계의 재귀 결과 이므로 를 사용한다.
   • 의 규칙에 의해 현재 쓸 수 있는 인자는 , , 이고, 이 중 를 사용하므로 입니다.
6. 의 오른쪽 인자는 함수이므로 를 사용한다.
7. 의 왼쪽 인자는 이므로 를 사용한다.
   • 의 규칙에 의해 현재 쓸 수 있는 인자는 , , 이고, 이 중 를 사용하므로 입니다.
8. 의 오른쪽 인자는 4~5에서 이미 다뤘으므로 같은 함수를 사용한다.

복잡하다고 하면 부정할 수는 없겠지만, 그래도 이게 바로 위에서 잠깐 언급했던 나머지 연산입니다! 재귀 함수 모형이 계산 모형 3대장 중 가장 먼저 나온 데는 이유가 있었네요.²

원시 재귀 함수의 한계

솔직히 저도 글 재작성 목적으로 조사를 하면서 그냥 소수 판정은 몰라도 번째 소수를 구하는 연산까지 원시 재귀일 것이라고는 상상도 하지 못했습니다. 이렇게 상수함수, 다음 수 함수, 사영함수, for문과 순차 실행만으로 생각보다 다양한 연산을 표현할 수 있지만, 모든 연산을 표현하는 것까지는 아쉽게도 불가능합니다.

튜링 기계를 기억하시나요? 어떤 튜링 기계든 모사할 수 있는, 즉 튜링 기계와 같은 표현력을 가지는 계산 모형을 튜링 완전하다고 합니다. 주어진 튜링 기계가 언젠가 정지하는지 판정하는 문제를 정지 문제^{halting problem}라고 하는데, 이 문제를 일반적인 경우에서 풀 수 있는 알고리즘은 존재하지 않음³이 알려져 있습니다(이런 성질을 결정불가능^undecidable이라고 합니다). 단적인 예로 상태가 개인 튜링 기계 중 정지하는 것만 추려서 가장 오래 동작하는 것을 찾는 바쁜 비버 게임이 있는데, 1962년에 처음 제안된 이후 증명일 기준으로 12년 뒤인 1974년에 4상태 바쁜 비버를, 62년 뒤인 2024년 7월이 되어서야 5상태 바쁜 비버를 찾을 수 있었습니다.

모든 튜링 기계를 모사할 수 있다면 그 연산이 언젠가는 정지하는지도 일반적으로 알 수 없어지기 때문에 튜링 완전한 계산 모형이라면 그 모형 버전의 정지 문제가 결정불가능해야 하는데, 잘 생각해보면 위에서 제시한 모든 기본 함수와 연산자는 유한한 자연수를 인자로 받고 유한 단계만큼 연산해 유한한 값을 반환하는 것을 알 수 있습니다. 즉, 원시 재귀 함수로는 모든 연산을 표현할 수 없습니다.

계산 가능하지만 원시 재귀가 아닌 함수가 있을까요? 멀리 가지 않아도 아래와 같은 아주 간단한 정의를 가지는 아커만 함수가 원시 재귀가 아님이 알려져 있습니다.

프로그래밍을 배우셨다면 원하는 언어로 금방 구현할 수 있을 것이라고 생각합니다. 원본의 형태와 가장 비슷하게 정의할 수 있는 Haskell로는 다음과 같이 작성할 수 있습니다.⁴

ack :: Integer -> Integer -> Integer
ack 0 n = n + 1
ack m' 0 = ack (m' - 1) 1
ack m' n' = ack (m' - 1) (ack m' (n' - 1))

원시 재귀 함수로 표현할 수 없는 함수는 일반 재귀 함수로 표현할 수 있습니다. 다행히 원시 재귀 함수에서 연산자를 딱 하나만 추가하면 됩니다.

일반 재귀 함수

새로운 연산자를 바로 소개해 드리겠습니다. 아래 새로운 연산자 이외에 기존 정의가 바뀌는 점은 없습니다.

• 최소화 연산자 (뮤, mu)
  • 무제한^unbounded 반복을 수행하는 연산자입니다. 변수함수 에 대해 변수함수 의 값은 을 만족하는 가장 작은 로 정의됩니다.

원시 재귀 연산자를 for문에 비유할 수 있다면, 최소화 연산자는 while문에 비유할 수 있습니다. 역시 JavaScript로 표현하면 다음과 같습니다.

const mu = F => (...args) => {
	for(let i = 0;; i++)
		if(F(i, ...args) != 0)
			return i;
};

구체적인 예시는 아니지만, 소수에 대해서만 0을 반환하는 1변수함수 이 있다면 의 값은 2가 됩니다.

위의 정의에서 꺼림칙한 점을 느낀 분들도 있을 것입니다. 만약에 주어진 가 어떤 경우에도 0을 반환하지 않는다면 어떻게 될까요? 이때는 함숫값이 없습니다!!! 🥳🥳🥳

🥳은 반어적인 의미의 🥳이기도 하지만, 축하할 일이기도 합니다. 일반 재귀 함수는 튜링 완전한 계산 모형임이 알려져 있고, 함숫값이 정의되지 않는 경우는 튜링 완전성에서 비롯한 영광의 상처라고 생각할 수도 있습니다. 이렇게 함숫값이 정의되지 않을 수도 있는 함수를 부분함수^{partial function}라고 하고, 간단한 예를 들면 가 있습니다.

아커만 함수 만들기

글을 처음 작성했을 때는 일반 재귀 함수 모형에 대한 직관이 충분하지 않아서 예시를 직접 만들지 못했는데, 그동안 경험이 쌓여 실제로 시도해볼 수 있게 되었습니다. 위에서 원시 재귀 함수가 아닌 것으로 소개한 아커만 함수를 일반 재귀 함수로 만들어 보겠습니다. 아커만 함수의 정의를 다시 적어 보겠습니다.

구현을 위해 다음과 같은 계획을 세웠습니다.

1. 주어진 깊이만큼만 재귀하는 원시 재귀 아커만 함수를 만든다.
2. 주어진 깊이가 아커만 함수를 계산하는 데 충분한지 확인하는 함수를 만든다.
3. 최소화 연산자에 2.의 함수를 적용해 필요한 깊이를 구한다.
4. 구한 깊이를 1.에 전달해 함숫값을 구한다.

그런데 이렇게 계획을 세우고 다른 프로그래밍 언어로 개념 증명 코드까지 짰지만 정작 그걸 재귀 함수로 옮기는 것은 하지 못했습니다. 일상적으로 쓰는 재귀적으로 정의되는 함수와 달리 일반 재귀 함수에서는 재귀하면서 마음대로 인자를 바꿀 수 없다는 사실을 잊고 있었기 때문입니다... 설명을 위해 원시 재귀 연산자 의 정의를 한 번만 더 가져와 보겠습니다.

변수함수 와 변수함수 에 대해 변수함수 는 다음과 같이 계산합니다.

이 정의를 주의깊게 보면 추가로 전달되는 는 재귀를 진행하는 내내 고정되어 있으며, 값이 바뀌는 인자는 에 전달되는 처음 두 인자뿐입니다. 그 중에서도 첫 번째는 루프 인덱스의 역할을 하고, 두 번째는 에서 시작해서 을 거친 값만 사용할 수 있기 때문에 마음대로 조작할 수 없으며, 그나마 자유롭게 쓸 수 있는 두 번째 인자에 어떻게든 모든 정보를 욱여넣었다고 해도 계산이 '상향식'으로 이루어지기 때문에 '미래를 예측'해서 나중에 필요할 인자를 미리 계산하는 것 역시 불가능합니다. 이대로는 방법이 없는 걸까요?

오래 기다리셨죠...? 진짜로 구현이 가능한 계획을 세우고 무려 2달 뒤에 구현을 마쳤습니다. 저도 이렇게 오래 걸릴 줄은 몰랐습니다.

1. 아커만 함수의 함숫값을 배열로 표현한다.
2. 미완성된 아커만 함수 배열을 조금씩 확장하는 함수를 만든다.
3. 아커만 함수 배열에 원하는 값이 있는지 확인하는 함수를 만든다.
4. 최소화 연산자에 2.와 3.의 함수를 적용해 필요한 재귀 깊이를 구한다.
5. 구한 깊이를 2.와 3.에 전달해 실제로 함숫값을 구한다.

괴델 수 부여하기

배열을 조작하기로 했다면 배열을 자연수로 나타낼 수 있어야 합니다. 우선 필요한 대상을 타입으로 표현해 봅시다.

-- Haskell 스타일 의사코드입니다.

-- 기본 불린 타입
data Bool
	= False
	| True

-- 기본 자연수 타입
data Nat;

-- 값이 없을 수도 있음
data Maybe a
	= Nothing
	| Just a

-- 두 개의 값
-- 하이라이터가 깨져서 부득이하게 이렇게 작성합니다. 원래 의도는 `(a, b)`입니다.
data Pair a b = Pair a b

-- 아래의 두 타입은 상호 재귀로 표현합니다.
-- 원소가 하나 이상 있는 배열
type NonEmpty a = Pair a (List a)
-- 원소가 없을 수도 있는 배열
type List a = Maybe (NonEmpty a)

은 그냥 , 을 쓰면 됩니다. 의 자연수 표현도 , 로 하면 됩니다. 는 좀 더 어렵네요. 자연수 2개를 자연수 1개로 나타내는 게 가능할까요?

다행히 위키백과에서 정확히 그 역할을 하는 짝짓기 함수^{pairing function}를 찾을 수 있었습니다. 이 글에서 사용할 칸토어 짝짓기 함수는 다음과 같은 정의를 가집니다.

인 와 의 쌍은 다음과 같이 찾을 수 있습니다.

위의 함수를 사용해 타입의 값 도 로 표현할 수 있습니다. (참고로 제곱근을 버림한 값을 구하는 함수도 원시 재귀입니다.)

와 는 와 만 사용해 정의했으므로 두 타입의 자연수 표현을 그대로 가져와 쓸 수 있습니다. 예를 들어 타입의 = 는 = 이 됩니다.

아커만 함수 배열

아커만 함수를 2차원 배열로 표현해 봅시다. 아커만 함수는 1번째 인자 에 더 민감하게 반응하므로 을 바깥 차원으로 두어서 으로 정의하는 편이 더 편리할 것입니다. 아커만 함수 배열을 조작할 때는 이전 원소의 값이 계산에 필요한 경우가 많기 때문에 대신 값이 하나라도 있음이 보장되는 타입을 사용하겠습니다.