2017년 2월 7일 (화) 11:57에 Maintenance script님의 편집

2017-02-07T11:57:54Z

새 문서

[목차]

== 정의 ==
어떤 함수 F가 하나 이상의 인자(argument)로서 함수를 받거나, 결과값(return value)으로 함수를 돌려주는 경우 그 함수 F를 고차 함수라고 한다. 아래 [[JavaScript|자바스크립트]] 예제들을 보자.
-----
[anchor(정의예제1)](1) 아래에서 함수 {{{#green apply}}}는 함수를 인자로 받으므로 '''고차 함수'''이다.{{{#!syntax javascript
function inc(n) {
return n + 1;
}

function apply(f, v) {
return f(v);
}

const m = apply(inc, 9); // m = 10
}}}
----
[anchor(정의예제2)](2) 아래에서 함수 {{{#green greeting}}}은 함수를 결과값으로 돌려주고 있으므로 '''고차 함수'''이다.{{{#!syntax javascript
function greeting(msg) {
return function(who) {
return `${msg}! ${who}`;
}
}

const hello = greeting("hello");
const helloToAlice = hello("alice"); // helloToAlice = "hello! alice"

const annyeong = greeting("안녕");
const annyeongToAlice = annyeong("alice"); // annyeongToAlice = "안녕! alice"
}}}
----
[anchor(정의예제3)](3) 아래에서 함수 {{{#green curry}}}는 함수를 인자로 받고 또 결과값으로 함수를 돌려준다. 따라서 '''고차 함수'''이다.{{{#!syntax javascript
function add(a, b) {
return a + b;
}

function curry(f, a) {
return function(b) {
return f(a, b);
}
}

const add7 = curry(add, 7);
const retval = add7(8); // retval = 15
}}}

== 관련 개념 ==
=== 익명 함수 (Anonymous function) ===
명칭 그대로 이름을 갖지 않는 함수이다. 위의 고차 함수 정의 섹션의 [[#정의예제2|예제 (2)]]의 함수 greeting과 [[#정의예제3|예제 (3)]]의 함수 curry가 {{{#green 결과값으로서 돌려주는 함수}}}같은 것들이 바로 익명 함수다. 더 자세한 내용은 별도의 [[람다식|익명 함수]] 문서를 참조하자.
=== 일차 함수 (First-order function) ===
일차 함수는 고차 함수를 제외한 모든 함수를 가리킨다. 위의 고차 함수 정의 섹션의 [[#정의예제1|예제 (1)]]의 함수 {{{#green inc}}}, [[#정의예제2|예제 (2)]]의 함수 {{{#green hello}}}와 {{{#green annyeong}}} 그리고 [[#정의예제3|예제 (3)]]의 함수 {{{#green add}}} 및 {{{#green add7}}}은 고차 함수가 아니므로 일차 함수이다.
=== 일등급 시민으로서의 함수 (Function as first-class citizen) ===
일등급 함수(First-class function)이라고도 한다. 어떤 [[프로그래밍 언어]]가 함수를 인자로 전달하고, 결과값으로 반환하고, 변수에 대입하는 등의 행위를 허용할 때 그 언어가 "함수를 일등급 시민으로서 대접한다"라고 말한다.

== 활용[* 예제들은 [[C++]]로 쓰여졌다. 이 문서를 보는 사람들 중에는 명령형 프로그래밍의 관점을 가지신 분들이 더 많으리라 예상되어 --번잡하고 추한 문법에도 불구하고-- 부득이하게 [[C++]]를 골랐다. 양해 바랍니다.] ==
[[함수]]나 [[수|수(數)]]를 어떻게 활용할 것인가를 생각해보면 그 가능성은 무궁무진하다. '''고차''' 함수 역시 마찬가지다. --아래의 예제들은 무한 속의 한톨 모래알만큼이다.--
=== 예제 하나 ===
'''고차 함수'''는 추상화를 좀 더 간편한 방법으로 가능하게 한다. 추상화는 장황하고 반복적인 코드를 줄여준다. 줄어든 코드는 [[프로그래머]]를 인간답게 만든다. 무엇보다도 추상화된 코드는 아름답다. 고차 함수 {{{#green fold}}}[* fold는 우리말로 접는다는 뜻이다. 배열이나 리스트와 같은 선형 데이터 구조를 맨 왼쪽 혹은 맨 오른쪽 원소부터 하나씩 접어 나가는 걸 상상해 보라. 트리나 그래프 등과 같은 비선형 구조도 어디서부터 시작해서 어떠한 순서로 접을지만 규정해 준다면 접지 못할 이유는 없다.]를 직접[* 많은 [[프로그래밍 언어]]들이 언어 내부(internal)에 혹은 라이브러리의 형태로 전형적으로 많이 쓰이는 자료구조에 연계된 고차 함수들(map,fold,filter,partition,group,sort,span,scan,take....)을 제공해 준다. 뿐만 아니라 고차 함수와 고차 함수를 합성(composition)한 고차 함수, 고차 함수와 자주 쓰이는 [[#s-2.2|일차 함수]]를 결합한 함수를 미리 마련해 두고 있다. __물론 고차 함수가 자료 구조와 반드시 연계되어야만 하는 것은 아니다.__] 구현하면서 추상화를 진행해 보자.
----
[anchor(추상화예제0)]'''추상화 前''': 정수 배열을 순회하며 총합과 총곱을 구해보자
{{{#!syntax cpp
int main(int argc, char** argv) {
int array[] = {1,2,3,4,5,6,7,8,9,10};
int stop = 10;
int sum = 0, product = 1;

for (int i = 0; i < stop; i++) {
sum = sum + array[i];
product = product * array[i];
}
// sum = 55, product = 3628800

return 0;
}
}}}
----
[anchor(추상화예제1)]'''추상화 1단계''': sum과 product 연산을 별도의 함수로 만들어 재활용할 수 있게 하자
{{{#!syntax cpp
int sum(int array[], size_t stop, int identity) {
int retval = identity;

for (int i = 0; i < stop; i++)
retval = retval + array[i];

return retval;
}

int product(int array[], size_t stop, int identity) {
int retval = identity;

for (int i = 0; i < stop; i++)
retval = retval * array[i];

return retval;
}

int main(int argc, char** argv) {
int array[] = {1,2,3,4,5,6,7,8,9,10};

int sum_result = sum(array, 10, 0);
// sum_result = 55
int product_result = product(array, 10, 1);
// product_result = 3628800

return 0;
}
}}}
----
[anchor(추상화예제2)]'''추상화 2단계''': [[#추상화예제1|추상화 1단계]]의 {{{#green sum}}}과 {{{#green product}}} 함수를 서로 비교해보자. 다른 점은 오직 (+)와 (*)뿐이다. 이제 '''고차 함수'''가 등장할 차례다.
{{{#!syntax cpp
// fold 함수는 두개의 정수를 받아 정수를 돌려주는 함수를 "f"라는 파라미터명으로 받는 고차 함수다.
// 파라미터:
// array : 정수 배열
// stop : 연산의 종착 인덱스(대개는 배열의 길이와 동일할 것이다)
// f : 폴딩(folding)에 사용될 바이너리 함수
// identity: 폴딩에 사용될 최초값
int fold(int array[], size_t stop, int(*f)(int, int), int identity) {
int retval = identity;

for (int i = 0; i < stop; i++)
retval = f(retval, array[i]); // 인자로 받은 f 함수는 이곳에서 쓰인다.

return retval;
}
}}}정의한 고차함수 {{{#green fold}}}를 써먹어 보자.{{{#!syntax cpp
int sum(int a, int b) { return a + b; }
int product(int a, int b) { return a * b; }

int main(int argc, char** argv) {
int array[] = {1,2,3,4,5,6,7,8,9,10};

int sum_result = fold(array, 10, sum, 0);
// sum_result = 55; 고차 함수인 fold에 sum 함수를 넘겨주었음에 주목하자
int product_result = fold(array, 10, product, 1);
// product_result = 3628800; 이번엔 함수 fold에 prodct 함수를 넘겨주었다.

return 0;
}
}}}* {{{#green fold}}} 함수를 별도의 라이브러리로 만들어 놓는다든가 하면 얼마나 편리할까!
----
[anchor(예제3)]'''추상화 3단계''': 그런데 [[#추상화예제2|추상화 2단계]]의 {{{#green fold}}} 함수는 정수 배열에 대한 연산만 가능하다. 모든 형의 배열에 대해 가능하도록 추상화해 보자.[* 추상화를 '''적극''' 지원하는 [[프로그래밍 언어]]들은 명칭 그리고 내부구현은 다르지만 [[C++]]의 template과 하는 역할이 사실상 동일한 기능을 제공해 준다.]
{{{#!syntax cpp
template<typename T, typename R> // T는 배열에 들어있는 엘리먼트의 형을, R은 최종 결과값의 형을 대변한다.
R fold(T array[], size_t stop, R(*f)(R, T), R identity) {
R retval = identity;

for (int i = 0; i < stop; i++)
retval = f(retval, array[i]);

return retval;
}
}}}이제 형에 대한 추상화까지 마친 {{{#green fold}}} 함수를 이용해 보자.[anchor(추상화예제3메인)]{{{#!syntax cpp
#include <string>
using std::string;
using std::to_string;

int sum(int a, int b) { return a + b; }
int product(int a, int b) { return a * b; }
string stringify(string s, int n) { return s + to_string(n); }

int main(int argc, char** argv) {
int array[] = {1,2,3,4,5,6,7,8,9,10};

int sum_result = fold(array, 10, sum, 0);
// sum_result = 55
int product_result = fold(array, 10, product, 1);
// product_result = 3628800
string stringified_result = fold(array, 10, stringify, string(""));
// stringified_result = string("12345678910")

return 0;
}
}}}
----
'''추상화 번외''': [[#추상화예제3메인|추상화 3단계]]의 {{{#green fold}}} 함수와 ({{{#green sum}}}, {{{#green product}}} 그리고 {{{#green stringify}}}) 함수들과 각 연산의 identity를 하나로 묶은 함수들을 만들 수 있진 않을까. [[Closure|클로저(Closure)]]를 이용해 보자.
{{{#!syntax cpp
// 파라미터:
// f : 폴딩(folding)에 사용될 바이너리 함수
// identity: 폴딩에 사용될 최초값
template<typename T, typename R>
auto foldop(R(*f)(R,T), R identity) {
// 익명 함수를 반환한다.
// 반환되는 익명함수가 자신의 외부 함수인 foldop 함수의 인자들(f, identity)을 품고 있다가 자신이 호출되었을 때 사용함에 주목하자.
return [f, identity](T array[], int stop) {
return fold(array, stop, f, identity);
};
}
}}}이제 {{{#green foldop}}} 함수와 그것이 반환하는 [[Closure|클로저]]를 활용해 보자.{{{#!syntax cpp
int main(int argc, char** argv) {
int array_pos[] = {1,2,3,4,5,6,7,8,9,10};
int array_neg[] = {-10,-9,-8,-7,-6,-5,-4,-3,-2,-1};

auto foldsum = foldop(sum, 0);
auto foldproduct = foldop(product, 1);
auto foldstringify = foldop(stringify, string(""));

int sum_pos = foldsum(array_pos, 10);
// sum_pos = 55
int sum_neg = foldsum(array_neg, 10);
// sum_neg = -55
int product_pos = foldproduct(array_pos, 10)
// product_pos = 3628800
int product_neg = foldproduct(array_neg, 10);
// product_neg = 3628800
string stringified_pos = foldstringify(array_pos, 10);
// stringified_pos = string("12345678910")
string stringified_neg = foldstringify(array_neg, 10);
// stringified_neg = string("-10-9-8-7-6-5-4-3-2-1")

return 0;
}
}}}

[[분류:수학]][[분류:프로그래밍]]

고차 함수 - 편집 역사

2017년 2월 7일 (화) 11:57에 Maintenance script님의 편집