Account: please sign in
AA

고계 함수 혹은 고차 함수higer-order functions함수에 적용될 수 있거나 함수로 환산될 수 있는 (절차형 진영의 용어로 말하자면 "함수를 인자로 취할 수 있거나 함수를 리턴할 수 있는") 함수입니다. "~수 있는"이라고 표현하는 이유는, 어떤 특정 함수 f가 함수에 적용되지도 않고 함수로 환산되지도 않더라도, 같은 환경과 설정 하에 있는 다른 함수 g나 h 등 중 고계 함수가 있다면 f도 고계 함수이기 때문입니다.

종류

함수로 환산될 수 있는 함수

어떤 함수 h의 타입이 다음과 같다면:

  • h : D → (A → B)

바로 이 함수 h가 다른 함수로 환산되는 (함수를 리턴하는) 함수입니다. 이 함수는 정의역인 집합 D의 원소 (즉, D 타입의 값) 하나를 인자로 받아서 공변역인 집합 A → B의 원소 (즉, A → B 타입의 값, 즉, A로부터 B로의 함수) 하나를 리턴합니다. 예를 들어, 실제 h의 정의는 다음과 같을 수 있습니다:

  • h : D → (A → B)
    h = { ( 100 ↦ {(10↦3),(20↦1)} ), ( 200 ↦ {(10↦1),(20↦2)} ) }

참고로, h의 타입은 → 연산자의 결합 방향이 우측이므로 다음과 같이 쓸 수도 있습니다:

  • h : D → A → B

함수에 적용될 수 있는 함수

만일 어떤 함수 g의 타입이 다음과 같다면:

  • g : (A → B) → C

바로 이 함수 g가 다른 함수에 적용되는 (다른 함수를 인자로 받는) 함수입니다. 이 함수는 정의역인 집합 A → B의 원소 (즉, A → B 타입의 값, 즉, A로부터 B로의 함수) 하나를 인자로 받아서 집합 C의 원소 (즉, C 타입의 값) 하나를 리턴합니다. 예를 들어, 실제 g의 정의는 다음과 같을 수 있습니다:

  • g : (A → B) → C
    g = { ( {(10↦3),(20↦1)} ↦ 100 ), ( {(10↦1),(20↦2)} ↦ 200 ) }

이미 설명했듯이, g의 타입 선언에 등장하는 괄호는 생략할 수 없습니다.

함수에 적용되어 함수로 환산되는 함수

만일 어떤 함수 i의 타입이 다음과 같다면:

  • i : (A → B) → C → D

이 함수 i는 A로부터 B로의 함수 하나에 적용되어 C로부터 D로의 함수 하나로 환산됩니다.

고계 함수를 인자로 받거나 고계 함수로 환산되는 고계 함수도 생각해볼 수 있습니다. 함수 j : (A → B → A) → (B → A) → A → B 의 정의역과 공변역이 무엇일지, 그리고 그 정의역의 (만일 있다면) 정의역과 공변역, 공변역의 정의역과 공변역은 각각 무엇일지 각자 생각해보시기 바랍니다.

예시

함수의 합성

함수 합성 연산자 ∘ 는 흔히 이항 중위 연산자 형태로 쓰이지만, 두 함수 f, g에 적용되어 (두 함수 f와 g를 인자로 받아서) 합성된 함수로 환산되는 (합성된 함수를 리턴하는) 고계 함수로 볼 수도 있습니다. 단, 그렇다고 해서 ∘ 의 타입이 다음과 같다는 뜻은 아닙니다:

  • ∘ : (A → B) × (C → D) → E → F

왜냐하면, 다음 동치 관계를 가만히 들여다보면:

  • (f ∘ g)(x)  =  f(g(x))

함수 f와 g의 합성이란

  • 합성할 두번째 함수인 g의 계산 결과 값을 첫번째 함수인 f에 인자로 넘겨줘야하기 때문에, f의 정의역과 g의 공변역이 같아야만 하고,
  • 합성된 결과 함수인 (f ∘ g)의 정의역은 합성할 두번째 함수인 g의 정의역과 같아야 하고,
  • 합성된 결과 함수인 (f ∘ g)의 공변역은 합성할 첫번째 함수인 f의 공변역과 같아야하기 때문입니다.

따라서, ∘의 올바른 타입 선언은 다음과 같습니다:

  • ∘ : (C → B) × (A → C) → A → B

함수의 Curried Form

임의의 함수 u : X×Y→Z에 대해서, 그에 '상응하는' 고계 함수 c : X→Y→Z를 u의 curried form 혹은 curried function이라고 합니다. 반대로, 이 경우 u는 c의 uncurried form이 됩니다. 또한, u를 c로 변환하는 과정을 currying이라고 하고 그 반대를 uncurrying이라고 하며, 임의의 이항 함수에 대해 currying과 uncurrying은 아주 간단한 알고리즘에 의해 자동으로 이루어집니다.

윗 단락에서 '상응한다'는 말의 의미는 두 함수의 최종 결과가 같다는 뜻입니다. 이를 정형적으로 설명하는 가장 간단한 방법은 임의의 u : X×Y→Z에 대해

  • c : X → Y → Z
    c = λx.λy.u 〈x,y〉

인 c가 바로 u와 상통하는 함수라고 설명하는 것이지만, 아직 lambda-calculus를 살펴보지 않았으니 집합과 다이어그램으로 설명해보겠습니다:

예를 들어, 세 집합 A = {a1, a2}, B = {b1, b2}, C = {c1, c2}가 있을 때, 함수

  • f : A × B → C
    f = {((a1,b1),c2), ((a1,b2),c1), ((a2,b1),c1), ((a2,b2),c1)}

의 curried form인 f'은 다음과 같은 함수입니다:

  • f' : A → B → C
    f' = { (a1, {(b1,c2), (b2,c1)}), (a2, {(b1,c1), (b2,c1)}) }

이 f와 f'을 각각 arrow mapping diagram으로 비교해보면 다음과 같습니다:
currying.png

Uncurried form인 임의의 함수를 그 함수의 curried form으로 바꿔주는 변환 함수 curry의 타입은 다음과 같고:

  • curry : (A × B → C) → A → B → C

반대로 curried form인 임의의 함수를 그 함수의 uncurried form으로 바꿔주는 변환 함수 uncurry의 타입은 다음과 같습니다:

  • uncurry : (A → B → C) → A × B → C

이들 두 함수의 정의는 λ-calculus를 다룬 이후에 다시 설명하거나 숙제/시험 문제로 출제될 수도 있습니다.

고계 함수의 부분 적용

어떤 고계 함수를 어떤 인자에 적용한 결과(환원 값, 리턴 값)가 아직 어딘가에 더 적용할 수 있는 함수이 적용을 부분 적용partial application이라고 하고, 그렇지 않으면 완전 적용full application이라고 합니다.

예를 들어, 바로 위에서 예시로 들었던 다음과 같은 고계 함수가 있을 때:

  • f' : A → B → C
    f' = {(a1, {(b1, c2), (b2, c1)}), (a2, {(b1, c1), (b2, c1)})}

이 함수의 부분 적용은 다음과 같고:

  • f' a2 : B → C
    f' a2 = {(b1, c1), (b2, c1)}

완전 적용은 다음과 같습니다:

  • f' f2 b1 : C
    f' f2 b1 = c1

A → B → C 가 사실은 A → (B → C)였다는 사실과 함께 생각하기 바랍니다. 이는 juxtapositioning이 좌측우선결합을 하는 반면 → 연산자는 우측우선결합을 하는 이유이기도 합니다.

프로그래밍 언어에서의 활용

Haskell, ML, Lisp, Scheme 등의 함수형 언어들 뿐만 아니라 Python 등 일부 절차형 언어에도 내장되어있는 map 함수는 첫번째 인자로 받은 함수를 두번째 인자로 받은 "나열들"의 각 원소에 적용시킵니다.

예를 들어, 정수들의 리스트 l = [2,3,5,7,11,13,17]의 각 원소들을 일괄적으로 3씩 증가시키고 싶을 경우, 만일 이 언어의 내장 덧셈 함수 add

  • add : Z × Z → Z

타입이라면 이를 활용할 수 없으며, 따로 다음과 같은 함수를 정의하여:

  • inc3 : Z → Z

다음과 같이 이용하거나:

  • map inc3 l = [5,6,8,10,14,16,20]

혹은 (아직 설명하지 않은) λ-term으로 아래와 같이 함수를 구성해야 하는 반면:

  • map (λx.add (3,x)) l = [5,6,8,10,14,16,20]

만일

  • add : Z → Z → Z

타입이라면 이를 그대로 활용하여 다음과 같이 계산할 수 있습니다:

  • map (add 3) l = [5,6,8,10,14,16,20]

참고: map의 타입을 설명하려면 먼저 타입 생성자(타입을 인자로 받아서 타입를 리턴하는 함수)를 설명해야 하지만, 일단은 타입 생성자 설명을 생략하고 예시로서 보여드립니다:

  • map : (A → B) → List A → List B

여기서 List가 대표적인 타입 생성자입니다:

  • List : TypeType