문서 보기문서 편집수정 내역 고차 함수 (덤프버전으로 되돌리기) [include(틀:다른 뜻1, other1=수학적인 의미, rd1=다항함수)] [include(틀:프로그래밍 언어 문법)] [목차] == 정의 == 어떤 [[프로그래밍 언어]]의 함수 구현에서 함수를 인자로 넘길 수 있거나 반환할 수 있을 때 함수를 일급 객체(first-class object, 언어 내부에서 값으로 표현되고 전달될 수 있는 자료형[* 예를 들면 정수, 실수, 문자, 객체의 주소 등. (언어에 따라 문자열이 포함될 수 있거나 그렇지 않다. 예를 들어 [[C(프로그래밍 언어)|C]]나 [[C++]]에서는 문자열은 문자 배열의 주소이거나 문자 배열을 감싸는 객체의 주소로 나타내기 때문에 문자열 그 자체를 값으로 사용할 수 없으므로 일급 객체가 아니다.)])로 취급한다고 하고, 함수를 인자로 받거나 결과로 반환하는 함수를 고차함수(高次函數)라 한다. 수학의 [[범함수]]와 맥락이 비슷하다. == 주요 용어 == === [[람다식|익명 함수]] (匿名函數, Anonymous function) === 별도로 이름을 붙여 정의하거나 변수에 대입되지 않고 함수를 호출하거나 반환할 때 상수 표현식으로 작성된 함수를 말한다. [[#s-3.2|설명 예제 2]]의 greeting 함수와 [[#s-3.3|설명 예제 3]]의 curry 함수가 반환하는 함수가 바로 익명 함수다. 반대로 이름이 있는 함수는 기명함수(旣名函數)라고 한다.[* 예를 들면 [[수학]]의 [[삼각함수]]들이 대표적인 기명 함수다.] === 일차 함수 (一次函數, First-order function) === [[#s-1|고차 함수]]가 아닌 함수를 말한다. [[#s-3.1|설명 예제 1]]의 increase 함수와 [[#s-3.2|설명 예제 2]]의 greeting 함수가 반환하는 함수, [[#s-3.3|설명 예제 3]]의 add 함수와 curry 함수가 반환하는 함수는 고차 함수가 아니므로 일차 함수이다. == 설명 예제 == === 함수를 인자로 하여 호출할 수 있는 함수 === 아래의 apply 함수는 함수를 인자로 받을 수 있으므로 고차 함수다. ==== [[C++]] 구현 ==== {{{#!syntax cpp #include #include using namespace std; int increase(int); int apply(function, int); int main(int argc, char **argv) { cout << apply(increase, 9) << endl; // 10 return 0; } int increase(int value) { return value + 1; } int apply(function fx, int value) { return fx(value); } }}} ==== [[JavaScript]] 구현 ==== {{{#!syntax javascript const increase = value => value + 1; const apply = (fx, value) => fx(value); console.log(apply(increase, 9)); // 10 }}} ==== [[PHP]] 구현 ==== {{{#!syntax php $value + 1; $apply = fn($fx, $value) => $fx($value); echo $apply($increase, 9); //10 }}} ==== [[Java]] 구현 ==== {{{#!syntax java package wiki.namu.example; import java.util.function.Function; public class Main { public static final Function INCREASE = value -> value + 1; public static void main(String[] args) { System.out.println(apply(INCREASE, 9)); // 10 } public static int apply(Function fx, int value) { return fx(value); } } }}} === 함수를 결과로 반환하는 함수 === 아래의 greeting 함수는 결과로 함수를 반환하므로 고차 함수다. ==== C++ 구현 ==== {{{#!syntax cpp #include #include #include using namespace std; function greeting(const string &); int main(const int argc, const char **argv) { auto korean_greeting = greeting("안녕"); auto english_greeting = greeting("Hello"); cout << korean_greeting("세계") << endl; // 안녕, 세계! cout << english_greeting("world") << endl; // Hello, world! return 0; } function greeting(const string &message) { return [message](const string &name) -> string { return message + ", " + name + "!"; }; } }}} ==== JavaScript 구현 ==== {{{#!syntax javascript const greeting = message => name => `${message}, ${name}!`; const koreanGreeting = greeting("안녕"); const englishGreeting = greeting("Hello"); console.log(koreanGreeting('세계')); // 안녕, 세계! console.log(englishGreeting('world')); // Hello, world! }}} ==== [[PHP]] 구현 ==== {{{#!syntax php fn($name) => "{$message}, {$name}!"; $koreanGreeting = $greeting("안녕"); $englishGreeting = $greeting("Hello"); echo $koreanGreeting('세계'); // 안녕, 세계! echo $englishGreeting('world'); // Hello, world! }}} ==== Java 구현 ==== {{{#!syntax java package wiki.namu.example; import java.util.function.Function; public class Main { public static final Function> GREETING = message -> name -> message + ", " + name + '!'; public static void main(String[] args) { Function koreanGreeting = GREETING.apply("안녕"); Function englishGreeting = GREETING.apply("Hello"); System.out.println(koreanGreeting.apply("세계")); // 안녕, 세계! System.out.println(englishGreeting.apply("Hello")); // Hello, world! } } }}} === 함수를 인자로 하여 호출할 수 있고 결과로 함수를 반환하는 함수 === 다음의 예제는 다변수 함수의 일부 인수를 정적으로 정하는 currying 구현을 나타낸다. 아래의 curry 함수는 함수를 인자로 하여 호출할 수 있고 결과로 함수를 반환하므로 고차 함수다. ==== C++ 구현 ==== {{{#!syntax cpp #include #include using namespace std; int add(const int &, const int &); function curry(const function &, const int &); int main(const int argc, const char **argv) { auto add_10 = curry(add, 10); cout << add_10(5) << endl; // 15 } int add(int value_x, int value_y) { return value_x + value_y; } function curry(const function &fx, const int &value_x) { return [fx, value_x](const int &value_y) -> int { return fx(value_x, value_y); }; } }}} ==== JavaScript 구현 ==== {{{#!syntax javascript const add = (valueX, valueY) => valueX + valueY; const curry = (fx, valueX) => valueY => fx(valueX , valueY); const addTen = curry(add, 10); console.log(addTen(5)); // = 15 }}} ==== [[PHP]] 구현 ==== {{{#!syntax php $valueX + $valueY; $curry = fn($fx, $valueX) => fn($valueY) => $fx($valueX , $valueY); $addTen = $curry($add, 10); echo $addTen(5); // = 15 }}} ==== Java 구현 ==== {{{#!syntax java package wiki.namu.example; import java.util.function.Function; import java.util.function.BiFunction; public class Main { public BiFunction add = (valueX, valueY) -> valueX + valueY; public BiFunction, Integer, Function> curry = (fx, valueX) -> valueY -> fx.apply(valueX, valueY); public static void main(String[] args) { Function addTen = curry.apply(add, 10); System.out.println(addTen.apply(5)); // 15 } } }}} == 활용 예제 == 일반적으로 함수형 프로그래밍 패러다임을 지원하는 언어에서는 다양한 고차 함수가 내부적으로 제공되거나 라이브러리로 사용할 수 있도록 되어 있다. 아래에서는 일부 고차 함수를 직접 구현한다. === 수열의 합과 곱에 대한 추상화 === 고차 함수 fold [* [[자료구조]]를 접는다고 생각하면 된다.]를 활용한 추상화를 통해 코드의 가독성과 재활용성을 높이는 예제이다. ==== 일반적인 구현 ==== 1에서 10까지 정의된 자연수열을 순회하여 합과 곱을 구한다. {{{#!syntax cpp #include #include using namespace std; int main(const int argc, const char **argv) { const array sequence = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int summation = 0; int production = 1; for (const int &i : sequence) { summation += i; production *= i; } cout << summation << endl; // 55 cout << production << endl; // 3628800 return 0; } }}} ==== 1단계 : 함수의 재활용 ==== 합 연산과 곱 연산을 별도의 함수로 만들어 재활용할 수 있게 한다. {{{#!syntax cpp #include #include using namespace std; template int get_summation(const array &, const int & = 0); template int get_production(const array &, const int & = 1); int main(const int argc, const char **argv) { const array sequence = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; cout << get_summation(sequence) << endl; // 55 cout << get_production(sequence) << endl; // 3628800 return 0; } template int get_summation(const array &sequence, const int &initial_value) { int result = initial_value; for (const int &i : sequence) { result += i; } return result; } template int get_production(const array &sequence, const int &initial_value) { int result = initial_value; for (const int &i : sequence) { result *= i; } return result; } }}} ==== 2단계 : 고차 함수 정의 ==== 별도로 정의한 합 연산과 곱 연산에서 연산자를 제외한 공통된 부분을 고차 함수로 묶는다. {{{#!syntax cpp #include #include #include using namespace std; template int fold(const array &, const function &, const int &); int main(const int argc, const char **argv) { const array sequence = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; auto add = [](const int &value_x, const int &value_y) -> int { return value_x + value_y; }; auto multiply = [](const int &value_x, const int &value_y) -> int { return value_x * value_y; }; cout << fold(sequence, add, 0) << endl; // 55 cout << fold(sequence, multiply, 1) << endl; // 3628800 return 0; } template int fold(const array &sequence, const function &fx, const int &initial_value) { int result = initial_value; for (const int &i : sequence) { result = fx(result, i); } return result; } }}} ==== 3단계 : 인자 형식 일반화 ==== 이전 단계의 fold 함수는 정수 배열의 연산만 가능했다. 이를 모든 형식에 적용할 수 있게 일반화한다. {{{#!syntax cpp #include #include #include using namespace std; template return_type fold(const array &, const function &, const return_type &); int main(const int argc, const char **argv) { const array sequence = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; function add = [](const int &value_x, const int &value_y) -> int { return value_x + value_y; }; function multiply = [](const int &value_x, const int &value_y) -> int { return value_x * value_y; }; function(const string &)> join = [](const string &connector) -> function { return [connector](const string &value_x, const int &value_y) -> string { return value_x + to_string(value_y) + connector; }; }; cout << fold(sequence, add, 0) << endl; // 55 cout << fold(sequence, multiply, 1) << endl; // 3628800 cout << fold(sequence, join(","), string("")); // 1,2,3,4,5,6,7,8,9,10, return 0; } template return_type fold(const array &sequence, const function &fx, const return_type &initial_value) { auto result = initial_value; for (const type &i : sequence) { result = fx(result, i); } return result; } }}} === [[메르센 소수|메르센 수열의 소수 수열]] 구하기 === 많은 프로그래밍 언어에서 일반적으로 많이 쓰이는 map[* mapping은 자료 구조와 규칙에 따른 계산을 하는 함수를 입력받아 각 항목에 대해 계산된 자료 구조를 반환한다.]과 filter[* filtering은 자료 구조와 조건부 처리를 하는 함수를 입력받아 각 항목에 대해 조건부 처리된 자료 구조를 반환한다.]를 구현한다. ==== 일반적인 구현 ==== 아래에서는 자연수열을 정적으로 입력하였다. 필요하다면 다른 컨테이너를 사용해 동적으로 임의의 수열을 생성할 수 있다. 메르센 수를 구하는 함수와 소수 판별 함수는 재귀 호출 최적화 및 상황에 따라 컴파일 타임에 값을 연역할 수 있도록 상수 표현식으로 작성되었다. [* C++의 상수 표현식은 인라이닝을 암시하여 인자가 적당히 작을 경우 별도의 함수 구문과 호출 구문을 생성하지 않는다.] {{{#!syntax cpp #include #include #include using namespace std; constexpr size_t mersenne(const size_t &); constexpr bool is_prime(const size_t &, const size_t & = 3); int main(const int argc, const char **argv) { const array natural_sequence = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; vector mersenne_sequence; vector prime_sequence; for (const auto &i : natural_sequence) { mersenne_sequence.push_back(mersenne(i)); } for (const auto &i : mersenne_sequence) { if (is_prime(i)) { prime_sequence.push_back(i); } } for (const auto &i : prime_sequence) { cout << i << endl; // 3, 7, 31, 127 } return 0; } constexpr size_t mersenne(const size_t &n) { return n > 0 ? 2 * mersenne(n - 1) + 1 : 0; } constexpr bool is_prime(const size_t &n, const size_t &i) { return n > 1 ? n & 1 ? n % i || i * i > n ? i * i > n ? true : is_prime(n, i + 2) : false : n == 2 : false; } }}} ==== 고차 함수 정의 및 사용 ==== 각 수열을 계산하는 부분을 고차 함수을 이용해 정의하였다. {{{#!syntax cpp #include #include #include using namespace std; using namespace placeholders; constexpr size_t mersenne(const size_t &); constexpr bool is_prime(const size_t &, const size_t & = 3); template vector map(const vector &, const function &); template vector filter(const vector &, const function &); int main(int argc, const char **argv) { const vector natural_sequence = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; auto mersenne_sequence = map(natural_sequence, function(mersenne)); auto prime_sequence = filter(mersenne_sequence, function(bind(is_prime, _1, 3))); for (const auto &i : prime_sequence) { cout << i << endl; // 3, 7, 31, 127 } return 0; } constexpr size_t mersenne(const size_t &n) { return n > 0 ? 2 * mersenne(n - 1) + 1 : 0; } constexpr bool is_prime(const size_t &n, const size_t &i) { return n > 1 ? n & 1 ? n % i || i * i > n ? i * i > n ? true : is_prime(n, i + 2) : false : n == 2 : false; } template vector map(const vector &sequence, const function &fx) { vector mapped; for (const type &i : sequence) { mapped.push_back(fx(i)); } return mapped; } template vector filter(const vector &sequence, const function &fx) { vector filtered; for (const type &i : sequence) { if (!fx(i)) { continue; } filtered.push_back(i); } return filtered; } }}} [[분류:프로그래밍]][[분류:프로그래밍 이론]][[분류:컴퓨터 공학]]캡챠되돌리기