고차 함수
더 많은 작업
- Higher-order function; HOF; 고차 함수; 고계 함수
- 함수를 인자로 받거나 함수를 결과로 돌려주는 함수
고차 함수(高次函數, higher-order function, HOF)는 다음 두 조건 가운데 적어도 하나를 만족하는 함수다.
- 하나 이상의 함수를 인자로 받는다.
- 함수를 결과로 반환한다.
이 조건을 하나도 만족하지 않는 보통 함수는 일차 함수(first-order function)라고 한다. 수학의 일차 함수(선형 함수)와는 다른 말이다. 어떤 언어에서 함수를 인자로 넘기고, 반환하고, 변수에 담을 수 있으면 그 언어는 함수를 일급 객체(first-class object)로 다룬다고 하며, 고차 함수는 이런 일급 함수 위에서 자연스럽게 쓰인다.
map, filter, reduce처럼 자료를 다루는 반복 패턴을 함수 하나로 묶어 코드 중복을 줄이고, "무엇을 할지"와 "어떻게 순회할지"를 떼어 놓는 것이 고차 함수의 핵심 쓸모다. 함수형 프로그래밍의 중심 도구이지만, 오늘날에는 콜백 함수, 이벤트 처리, 정렬 비교 함수, 파이썬 데코레이터, Java Stream API처럼 거의 모든 주류 언어에서 쓰인다.
1930년대 알론조 처치(Alonzo Church)가 만든 람다 대수(λ-calculus)는 함수 정의와 적용만으로 계산을 표현하는 형식 체계다.[1] 타입이 없는 람다 대수에서는 모든 값이 함수이므로 모든 함수가 고차 함수다. 대부분의 함수형 언어가 바탕으로 삼는 타입 있는 람다 대수에서, 함수 하나를 인자로 받는 고차 함수는 (τ₁ → τ₂) → τ₃ 꼴의 타입을 가진다. 함수 타입의 화살표가 몇 겹으로 중첩되는지를 함수의 차수(order)라고 하며, 인자에 함수가 없으면 1차, 1차 함수를 받으면 2차인 식이다.
일급 함수는 언어의 성질이고, 고차 함수는 그 성질을 이용한 함수의 종류다. 일급 함수가 있는 언어에서는 고차 함수를 그냥 쓸 수 있고, 함수를 반환하면 대개 클로저가 만들어진다. 일급 값이란 정수나 객체 주소처럼 언어 안에서 값으로 표현되어 전달·저장·반환될 수 있는 것을 말한다. 예를 들어 C에서 함수 자체는 일급 값이 아니지만 함수 포인터는 값이므로, 표준 라이브러리 qsort처럼 함수 포인터를 받아 고차 함수를 흉내 낸다. 같은 이유로 C의 문자열도 문자 배열의 주소로만 다룰 수 있어 문자열 자체가 일급 값은 아니다.
고차 함수는 익명 함수(람다)와 함께 쓰이는 경우가 많다. 익명 함수는 이름을 붙여 정의하거나 변수에 대입하지 않고 호출·반환하는 자리에서 식으로 적는 함수이고, 이름이 있는 함수는 기명 함수라고 부른다. 둘은 개념이 다르다. 익명 함수는 문법이고, 고차 함수는 함수를 다루는 방식이다.
| 이름 | 하는 일 | 파이썬 | 자바스크립트 | Haskell | Java Stream |
|---|---|---|---|---|---|
| map | 각 원소에 함수를 적용한 새 컬렉션 | map(f, xs) | xs.map(f) | map f xs | stream.map(f) |
| filter | 조건 함수가 참인 원소만 남김 | filter(p, xs) | xs.filter(p) | filter p xs | stream.filter(p) |
| fold / reduce | 초깃값과 이항 함수로 컬렉션을 값 하나로 접음 | functools.reduce(f, xs, init) | xs.reduce(f, init) | foldl f z xs, foldr f z xs | stream.reduce(init, f) |
| scan | fold의 중간 결과를 모두 남김(누적 합 등) | itertools.accumulate | 없음 | scanl | 없음 |
| flatMap | 각 원소를 컬렉션으로 바꾼 뒤 이어 붙임 | 컴프리헨션 | xs.flatMap(f) | concatMap, >>= | stream.flatMap(f) |
| sort(비교 함수) | 비교 규칙을 함수로 받아 정렬 | sorted(xs, key=f) | xs.sort(cmp) | sortBy cmp xs | sorted(comparator) |
| compose | 함수 합성 | 직접 작성 | 직접 작성 | f . g | f.compose(g), f.andThen(g) |
| apply / call | 함수를 인자에 적용 | f(*args) | f.apply(this, args) | f $ x | f.apply(x) |
fold는 이름 그대로 자료 구조를 접는다고 생각하면 된다. foldl은 왼쪽부터, foldr은 오른쪽부터 접으며, 연산이 결합 법칙을 만족하지 않으면 결과가 다르다. 파이썬 3에서는 reduce가 내장 함수에서 빠져 functools 모듈로 옮겨졌고, map과 filter가 리스트 대신 지연 계산하는 반복자를 돌려주게 되었다.[2] 정렬 알고리즘이 비교 함수를 받게 하면 정렬 알고리즘과 원소 비교 규칙을 떼어 놓을 수 있다.
const increase = value => value + 1;
const apply = (fx, value) => fx(value); // fx를 받으므로 고차 함수
apply(increase, 9); // 10
increase x = x + 1
apply f x = f x
main = print (apply increase 9) -- 10
const greeting = message => name => `${message}, ${name}!`;
const hello = greeting("안녕"); // 함수를 돌려받는다
hello("세계"); // "안녕, 세계!"
#include <functional>
#include <string>
std::function<std::string(const std::string&)> greeting(std::string message) {
return [message](const std::string& name) { // message를 값으로 붙잡은 람다
return message + ", " + name + "!";
};
}
// greeting("Hello")("world") == "Hello, world!"
twice는 함수 f를 받아 f를 두 번 적용하는 새 함수를 돌려준다. 같은 f에 twice를 여러 번 쓸 것이라면 값보다 함수를 돌려주는 편이 낫다.
def twice(f):
def result(x):
return f(f(x))
return result
plus_three = lambda i: i + 3
g = twice(plus_three)
print(g(7)) # 13
@twice # 데코레이터 문법: g = twice(g)와 같다
def g(i):
return i + 3
print(g(7)) # 13
import java.util.function.Function;
static Function<Integer, Integer> twice(Function<Integer, Integer> f) {
return f.andThen(f);
}
twice(i -> i + 3).apply(7); // 13
fn twice(f: impl Fn(i32) -> i32) -> impl Fn(i32) -> i32 {
move |x| f(f(x))
}
fn main() {
let g = twice(|i| i + 3);
println!("{}", g(7)); // 13
}
twice :: (a -> a) -> (a -> a)
twice f = f . f
main = print (twice (+3) 7) -- 13
Func<Func<int, int>, Func<int, int>> twice = f => x => f(f(x));
Func<int, int> plusThree = i => i + 3;
Console.WriteLine(twice(plusThree)(7)); // 13
커링(currying)은 인자 여러 개를 받는 함수를, 인자를 하나씩 받아 다음 함수를 돌려주는 함수의 사슬로 바꾸는 것이다. f(x, y)를 f(x)(y)로 쓰는 식이다. 논리학자 하스켈 커리(Haskell Curry)의 이름에서 왔으며, 모제스 쇤핑켈(Moses Schönfinkel)이 먼저 같은 착상을 발표한 것으로 알려져 있다. 부분 적용(partial application)은 인자 일부를 미리 채워 나머지를 받는 함수를 만드는 것으로, 커링된 함수에 인자를 일부만 주면 부분 적용이 된다. 커링을 구현하는 함수는 함수를 받아 함수를 돌려주므로 그 자체가 고차 함수다.
const add = (x, y) => x + y;
const curry = (fx, x) => y => fx(x, y); // 부분 적용
const addTen = curry(add, 10);
addTen(5); // 15
Haskell과 ML 계열에서는 모든 함수가 기본적으로 커링되어 있어, add x y = x + y를 정의하면 add 10이 곧 10을 더하는 함수다. 파이썬은 functools.partial, C++는 std::bind나 람다, Java는 Function<A, Function<B, C>> 타입으로 같은 일을 한다.
함수 합성은 함수 여러 개를 이어 하나의 함수로 만드는 고차 연산이다. Haskell의 (.) 연산자(f . g), F#의 >>와 << 연산자, Java의 Function.compose·andThen이 있다. 인자를 드러내지 않고 함수 합성만으로 정의를 적는 방식을 무인자(point-free) 스타일이라고 한다.
const compose = (...fns) => x => fns.reduceRight((acc, f) => f(acc), x);
const slugify = compose(s => s.replace(/\s+/g, "-"), s => s.trim(), s => s.toLowerCase());
slugify(" Hello World "); // "hello-world"
수열의 합과 곱을 구하는 코드는 연산자만 빼면 똑같다. 공통 부분을 fold 하나로 묶으면 연산만 바꿔 끼워 재사용할 수 있고, 원소 타입과 결과 타입을 일반화하면 문자열 이어 붙이기 같은 다른 일에도 그대로 쓸 수 있다.
def fold(seq, fx, init):
result = init
for x in seq:
result = fx(result, x)
return result
seq = range(1, 11)
fold(seq, lambda a, b: a + b, 0) # 55
fold(seq, lambda a, b: a * b, 1) # 3628800
fold(seq, lambda s, n: s + f"{n},", "") # '1,2,3,4,5,6,7,8,9,10,'
map과 filter를 이어 쓰면 "자연수로 메르센 수를 만들고 그 가운데 소수만 고른다" 같은 처리를 반복문 없이 적을 수 있다.
def is_prime(n):
return n > 1 and all(n % d for d in range(2, int(n ** 0.5) + 1))
mersenne = map(lambda n: 2 ** n - 1, range(1, 11))
print(list(filter(is_prime, mersenne))) # [3, 7, 31, 127]
Haskell에서는 map과 filter 자체를 재귀로 몇 줄에 정의할 수 있다.
map _ [] = []
map f (x:xs) = f x : map f xs
filter _ [] = []
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xs
대규모 데이터 처리의 맵리듀스도 map과 reduce라는 고차 함수의 이름과 발상을 가져왔다.
- 함수 포인터: C, C++, Fortran, Pascal은 함수의 주소를 넘길 수 있다. 아래는 임의의 함수를 받아 정적분의 근삿값을 구하는 C 코드다. 다만 함수 포인터는 환경을 붙잡지 못해 클로저가 아니다.
double integral(double f(double), double a, double b, int n) {
double sum = 0, dt = (b - a) / n;
for (int i = 0; i < n; ++i)
sum += f(a + (i + 0.5) * dt);
return sum * dt;
}
double square(double x) { return x * x; }
/* integral(square, 0, 1, 100) ≈ 0.333325 */
- 객체: 일급 함수가 없는 객체 지향 언어에서는 메서드 하나짜리 인터페이스와 객체가 함수를 대신한다. Java 8 이전의 익명 클래스로 만든 Comparator, Runnable이 그 예이며, GoF 디자인 패턴의 전략(Strategy)·명령(Command) 패턴이 같은 발상이다. 객체를 정의하고 만드는 코드가 늘고 실행 부담도 약간 있다.
- 매크로: 비슷한 효과를 낼 수 있지만 변수 포획 문제를 피하기 어렵고, 코드가 중복되며 타입 검사가 약하다.
- 동적 코드 평가(eval): 코드 문자열을 실행 중에 평가한다. 정적 타입 검사를 받지 못하고, 실행 시 컴파일·해석 비용이 들며, 입력을 섞으면 코드 주입 위험이 있다.
- 탈함수화(defunctionalization): 함수 값 대신 "어떤 함수인지"를 나타내는 자료 구조를 넘기고, apply 함수가 이를 보고 알맞은 동작을 고른다. C++ 템플릿과 함수 오버로딩으로 구현할 수 있다.
- 콜백 함수와 이벤트 처리: 버튼 클릭, 타이머, 비동기 I/O 완료 시 실행할 함수를 넘긴다. addEventListener, setTimeout, Promise.then이 모두 고차 함수다.
- 데코레이터와 미들웨어: 함수를 받아 로깅·캐싱·인증을 덧씌운 새 함수를 돌려준다. 파이썬은 2.4에서 @ 데코레이터 문법을 들여왔다.[3] Express 같은 웹 프레임워크의 미들웨어도 같은 구조다.
- 메모이제이션: 함수를 받아 결과를 기억하는 함수를 돌려준다. 파이썬 functools.lru_cache가 대표적이다.
- 컬렉션 파이프라인: Java Stream, C# LINQ, Kotlin 컬렉션 함수, 자바스크립트 배열 메서드, 스파크의 변환 연산.
- UI 구성 요소 재사용: React에서 컴포넌트를 받아 기능을 더한 새 컴포넌트를 돌려주는 함수를 고차 컴포넌트(higher-order component, HOC)라고 부른다.[4]
- 제어 구조 만들기: 재시도, 트랜잭션, 자원 해제(파일을 열고 함수를 실행한 뒤 반드시 닫기) 같은 틀을 함수로 만들고 본문만 인자로 받는다.
- 1930년대: 처치의 람다 대수가 함수를 인자와 결과로 쓰는 계산을 형식화했다.
- 1958~1960년: 존 매카시(John McCarthy)의 LISP가 함수를 인자로 받는 maplist 같은 함수를 제공했다.[5]
- 1960년대: APL이 함수를 받아 새 함수를 만드는 연산자(operator, 예: 축약 /)를 두었다.
- 1970~1980년대: ML, Scheme, Miranda 같은 함수형 언어가 고차 함수를 핵심으로 삼았고, 1990년 Haskell이 이를 이었다.
- 2000~2010년대: C# 3.0(2007)의 람다와 LINQ, C++11(2011)의 람다와 std::function, Java 8(2014)의 람다와 Stream API가 나오며 주류 언어에서도 고차 함수가 일상이 되었다.[6]
- 실행 비용: 함수를 값으로 넘기면 함수 객체와 클로저를 할당하고 간접 호출을 해야 한다. Kotlin 문서는 고차 함수의 이 비용을 설명하며, inline 함수로 람다를 호출 지점에 펼쳐 없애는 방법을 제공한다.[7] JIT 컴파일러나 C++ 템플릿은 인라이닝으로 이 비용을 크게 줄인다.
- 가독성: 고차 함수를 겹겹이 중첩하거나 무인자 스타일을 지나치게 쓰면 오히려 읽기 어렵다.
- 지연 계산: 파이썬 3의 map·filter, Java Stream은 지연 계산되므로, 결과를 소비하기 전까지 함수가 실행되지 않고 한 번 소비한 반복자는 다시 쓸 수 없다.
- 부작용: map이나 filter에 넘기는 함수가 바깥 상태를 바꾸면 실행 순서나 병렬 실행에 따라 결과가 달라질 수 있다. 가능하면 순수 함수를 넘긴다.
- 함자와 혼동: 범주론의 함자(functor)나 고차 타입(higher-kinded type)과는 다른 개념이다.
- ↑ Alonzo Church, "An Unsolvable Problem of Elementary Number Theory", American Journal of Mathematics 58(2), 1936
- ↑ What's New In Python 3.0
- ↑ PEP 318: Decorators for Functions and Methods
- ↑ Higher-Order Components, React 문서
- ↑ John McCarthy, "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I", CACM 3(4), 1960
- ↑ The history of C#, Microsoft Learn
- ↑ Inline functions, Kotlin 문서