List
이번에 설로인에서 진행한 테크 밋업에서 토스의 한상진님이 발표한 리스트에 대한 새로운 이해라는 세션을 들었습니다. 수학적 개념을 연결시켜서 리스트를 생각해본 적이 없었는데, 그런 사고를 할 수 있다는게 너무 재밌고 신기했습니다. 그래서 그 내용을 다시 한번 공유하면서 해당 세션의 핵심 개념을 파이썬으로 구현하며 정리하려고 합니다.
실무에서 리스트를 다룰 때, 맵/필터/집계 같은 연산을 자주 씁니다. 보통 이미 구현되어 있는 것을 호출해서 쓰지만, 직접 만들어보면 개념이 확실해지고, 병렬·대용량 처리에서 어떤 연산이 안전하고, 어떤 연산은 위험한지 이유를 명확히 이해할 수 있습니다.
항등원 & 결합법칙
우선 리스트와 고차함수로 넘어가기 전에 예전에 배웠던 간단한 수학상식을 이야기해보겠습니다.
•
항등원(Identity): 어떤 연산 ⊕에 대해, e ⊕ x = x ⊕ e = x 를 만족하는 값 e
◦
덧셈의 항등원: 0 (0을 계속 더해도 값이 안 변함)
◦
곱셈의 항등원: 1 (1을 계속 곱해도 값이 안 변함)
•
결합법칙(Associativity): (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)
◦
덧셈 +는 결합적 → 묶는 순서를 바꿔도 결과 동일
◦
뺄셈 은 결합적이지 않음 → 묶는 순서가 바뀌면 결과가 달라짐
이 두 가지가 왜 중요하냐면, fold를 안전하게 쓰려면 “초기값(항등원) + 결합적인 연산” 조합이 필요하기 때문입니다.
항등원이 중요한 이유
•
reduce(=fold)를 쓸 때 빈 입력이 올 수도 있는데, 이때 초기값이 항등원이면 정의가 안전해집니다. (빈 리스트 합 = 0, 빈 리스트 곱 = 1)
•
스트리밍/청크 처리에서 빈 청크가 나와도 항등원을 쓰면 결과를 흐트러뜨리지 않고 합칠 수 있습니다.
결합법칙이 중요한 이유
•
대용량에서 병렬/청크 처리를 하려면 데이터를 나눠서 부분 결과를 만든 뒤 마지막에 합쳐야 하는데, 이때 연산이 결합적이어야 어떻게 나눠도, 어떤 순서로 합쳐도 결과가 동일해지니다.
•
결합법칙이 깨지는 연산(예: 뺄셈)으로 청크를 합치면 결과가 입력 분할 방식에 따라 달라져서 병렬/청크 처리에서는 사용하면 안됩니다.
고차함수(High-Order Function)
고차함수는 함수를 인자로 받거나 함수를 반환하는 함수입니다. 우리가 매일 쓰는 map(f, xs), filter(p, xs), reduce(op, init, xs)는 전형적인 고차함수입니다. 여기서 핵심은 고차함수가 연산을 데이터에서 분리해 추상화한다는 점입니다.
리스트(더 넓게는 이터러블)는 순회 가능한 데이터 구조입니다. 즉, 무엇을 할지(함수)와 무엇을 순회할지(리스트/이터러블)를 조합만 하면 어떤 상황에서도 같은 패턴으로 문제를 풀 수 있습니다.
예를 들어,
•
map은 각 원소에 함수를 적용해 새로운 리스트를 만들고,
•
filter는 조건을 만족하는 원소만 걸러내며,
•
reduce는 모든 값을 하나로 모읍니다.
이 세 가지는 겉보기에는 다른 역할을 하는 것 같지만, 내부적으로는 모두 리스트를 순회하며 어떤 규칙으로 결과를 누적하는 과정을 공유합니다. 그래서 리스트에 고차함수를 적용하면 리스트를 다루는 거의 모든 문제를 한 프레임으로 설명할 수 있게 됩니다.
fold(reduce)
fold는 “초기값 + 누산 함수”로 시퀀스를 한 값으로 누적하는 패턴입니다. 파이썬에선 functools.reduce가 그 자체고, 직접 구현하면 아래처럼 구현할 수 있습니다.
간단한 fold 구현
from typing import Iterable, TypeVar, Callable
T = TypeVar('T') # 입력 요소 타입
U = TypeVar('U') # 누산 타입
def fold(xs: Iterable[T], init: U, op: Callable[[U, T], U]) -> U:
"""
xs: 입력 시퀀스
init: 누산의 초기값(가능하면 해당 연산의 '항등원'이 이상적)
op: 누산 함수 (acc, x) -> acc'
"""
acc = init
for x in xs:
acc = op(acc, x)
return acc
Python
복사
•
init은 가능하면 연산의 항등원을 넣습니다. (예: 덧셈 → 0, 곱셈 → 1)
•
op는 매번 acc와 요소 x를 받아 새로운 acc를 만듭니다.
이렇게 한 번 정의해두면 모든 누산형 연산을 하나의 틀로 일반화할 수 있다는 점입니다. 리스트의 길이를 세는 것도, 합계를 구하는 것도, 조건에 따라 값을 걸러내거나 변형하는 것도 전부 초기값에서 시작해 요소를 하나씩 누적(accumulate)해 가는 과정으로 표현할 수 있습니다.
자주 사용하는 함수를 fold로 구현하기
sum, product, max/min, all/any 같은 집계는 전부 “초기값 + 누산함수(acc, x)” 패턴으로 쓸 수 있습니다. 핵심은 초기값을 연산의 항등원으로 둔다는 점, 그리고 연산이 결합적이어야 청크/병렬에서 안전하다는 점 입니다.
length — 원소 개수 세기
길이는 원소 하나가 들어올 때마다 +1하면 됩니다.
def length(xs):
# 초기값 0에서, 원소를 하나 볼 때마다 +1
return fold(xs, 0, lambda acc, _: acc + 1)
# 사용 예
assert length([10, 20, 30]) == 3
Python
복사
sum — 합계
합계는 원소 하나가 들어올 때마다 해당 원소의 값을 더하면 됩니다.
def sum_via_fold(xs):
return fold(xs, 0, lambda acc, x: acc + x)
assert sum_via_fold([1, 2, 3]) == 6
Python
복사
product — 곱
곱셈은 원소 하나가 들어올 때마다 해당 원소의 값을 곱하면 됩니다.
빈 리스트의 곱은 1로 두는 것이 안전합니다.
def product_via_fold(xs):
return fold(xs, 1, lambda acc, x: acc * x)
assert product_via_fold([2, 3, 4]) == 24
assert product_via_fold([]) == 1 # 항등원 정의 덕분에 안전
Python
복사
map — 값 변형
map은 원소마다 f(x)를 적용해 새 리스트를 만드는 연산입니다.
def map_via_fold(xs, f):
# 빈 리스트에서 시작 → f(x)를 하나씩 추가
return fold(xs, [], lambda acc, x: acc + [f(x)])
assert map_via_fold([1, 2, 3], lambda x: x * 10) == [10, 20, 30]
Python
복사
filter — 조건을 만족하는 값만
p(x)가 True인 원소만 결과 리스트로 보내면 됩니다.
def filter_via_fold(xs, p):
def step(acc, x):
return acc + [x] if p(x) else acc
return fold(xs, [], step)
assert filter_via_fold([1, 2, 3, 4, 5], lambda x: x % 2 == 1) == [1, 3, 5]
Python
복사
all / any — Short-Circuit 없는 기본형
설명
단순히 fold만 쓰면 all과 any를 모두 구현할 수 있지만, 끝까지 돕니다. 모든 연산을 다 도는 것은 매우 비효율적입니다.
def all_via_fold_basic(xs):
# 항등원 True: 모두 True여야 True 유지
return fold(xs, True, lambda acc, x: acc and bool(x))
def any_via_fold_basic(xs):
# 항등원 False: 하나라도 True면 True로 전환
return fold(xs, False, lambda acc, x: acc or bool(x))
assert all_via_fold_basic([True, True, False]) is False
assert any_via_fold_basic([False, False, True]) is True
Python
복사
all / any — Short-Circuit
대용량에서 불필요한 순회를 줄이기 위해서 각 조건을 종료할 수 있는 조건을 같이 넘겨서 중간에 종료되도록 해야 합니다.
def fold_short_circuit(xs, init, step):
"""
step(acc, x) -> (acc', stop?)
stop? == True 이면 즉시 중단
"""
acc = init
for x in xs:
# step은 멈춰야하는지 여부인 stop도 acc와 함께 튜플로 전달해줌
acc, stop = step(acc, x)
if stop:
break
return acc
def any_via_fold(xs):
# True를 만나면 (True, stop=True) → 즉시 종료
return fold_short_circuit(xs, False, lambda acc, x: (True, True) if x else (acc, False))
def all_via_fold(xs):
# False를 만나면 (False, stop=True) → 즉시 종료
return fold_short_circuit(xs, True, lambda acc, x: (False, True) if not x else (acc, False))
assert any_via_fold([False, False, True, False]) is True
assert all_via_fold([True, True, False, True]) is False
Python
복사
any_by / all_by — 조건을 받아서
단순 불리언 대신 pred(x)로 판정하는 버전도 가능합니다.
def any_by(xs, pred):
return fold_short_circuit(xs, False, lambda acc, x: (True, True) if pred(x) else (acc, False))
def all_by(xs, pred):
return fold_short_circuit(xs, True, lambda acc, x: (False, True) if not pred(x) else (acc, False))
assert any_by([1, 3, 8, 5], lambda x: x % 2 == 0) is True
assert all_by(["aa", "ab"], lambda s: s.startswith("a")) is True
Python
복사
subtract — 결합법칙이 깨지면 생기는 일
앞에서 본 sum, product 같은 연산은 모두 결합법칙이 성립하는 안전한 연산입니다. 하지만 subtract(뺄셈)은 그렇지 않습니다. 겉보기에는 잘 작동하지만, 데이터를 나눠서 병렬로 처리할 때 문제가 생깁니다.
def subtract_all(xs: Iterable[int]) -> int:
return fold(xs, 0, lambda acc, x: acc - x)
assert subtract_all([1, 2, 3]) == -6 # 겉으로만 보면 되는 듯 보이지만...
Python
복사
겉으로는 정상처럼 보이지만, 부분 계산을 병렬로 수행하면 결과가 달라집니다.
•
청크1: [1, 2] → ((0-1)-2) = -3
•
청크2: [3] → (0-3) = -3
•
두 결과를 다시 연산으로 합치면 (-3) - (-3) = 0
즉, 원본 전체를 한 번에 처리했을 땐 -6, 부분 계산 후 합치면 0이 나옵니다.
이 차이는 결합법칙이 성립하지 않기 때문입니다. 뺄셈은 (a - b) - c ≠ a - (b - c)이므로, 어떤 순서로 묶고 나누느냐에 따라 결과가 달라집니다. 그래서 병렬·분산·청크 단위 처리가 필요한 상황에서는 반드시 결합적인 연산만 사용해야 하고, 연산의 시작점(초기값)은 그 연산의 항등원이어야 합니다. 이 두 가지를 만족해야만 데이터를 나누어 처리하더라도 결과가 일관되게 유지됩니다.
fold의 장점 - 병렬/청크 처리
대부분의 데이터 처리는 결국 큰 입력을 여러 조각으로 나누고, 각 조각을 독립적으로 계산한 뒤, 결과를 합치는 과정을 거칩니다. 이때 결합법칙이 성립하는 연산을 사용하면 놀라운 일이 일어납니다.
1.
분할 정복(Chunking)
a.
데이터를 여러 청크로 나눠 각각 fold를 적용합니다.
2.
독립 처리(Parallelization)
a.
각 청크는 서로 영향을 주지 않고 병렬로 계산할 수 있습니다.
3.
재결합(Combination)
a.
각 부분 결과를 다시 같은 연산으로 fold하면, 전체 결과와 완전히 동일합니다.
이 과정이 가능한 이유는 fold가 결합법칙을 보존하기 때문입니다. 즉, fold를 한 번에 돌리든, 여러 번 나눠 돌려 다시 합치든 결합적 연산에서는 항상 동일한 결과를 얻습니다.
마무리
이번 글의 핵심은 리스트를 다룬다는 건, 단순히 데이터를 순회하는 게 아니라 이터러블 위에서 연산을 조립하는 사고방식으로 전환하는 것이라고 생각합니다.
고차함수는 연산을 데이터에서 분리해 추상화하고, 리스트(이터러블)는 순회라는 공통 인터페이스를 제공합니다. 여기에 항등원과 결합법칙 같은 수학적 법칙을 더하면, 우리가 작성하는 로직은 단순한 코드가 아니라 일관된 결과를 보장하는 구조로 바뀝니다.
이번 세션에서 가장 인상 깊었던 건, 단순히 기술을 배운 것이 아니라 사고의 축이 달라졌다는 점이었습니다. 데이터 구조의 성질, 함수적 추상화, 수학적 법칙을 겹쳐서 생각하는 관점이 결국 데이터를 더 안정적이고 예측 가능하게 다루는 힘으로 이어진다고 느꼈습니다.
이런 사고는 데이터 엔지니어에게 특히 중요합니다. 대용량 데이터를 여러 청크로 나누고, 병렬로 처리하고, 다시 합칠 때 연산이 결합적이지 않거나 항등원이 명확하지 않다면 결과는 달라질 수 있습니다. 결국 수학적 사고는 추상적인 개념이 아니라, 데이터 처리의 안정성과 예측 가능성을 보장하는 실질적인 도구입니다.
이번 세션을 통해 fold나 병렬 처리 같은 기법의 원리뿐 아니라, 데이터를 다룰 때 “결과의 일관성”을 중심으로 사고해야 한다는 점을 다시 느꼈습니다. 이런 관점은 단순히 리스트를 다루는 코드뿐 아니라, 메시지 큐, 로그 스트림, 데이터 파이프라인 같은 다양한 데이터 시스템에도 같은 원리를 적용해볼 수 있을 것 같습니다.