FPJS | 3. 자료구조는 적게, 일은 더 많이

순수한 함수를 서로 연결하는 방법과 재귀적 사고를 통해
선언적 프로그램을 작성할 수 있다

애플리케이션의 제어 흐름

프로그램이 정답에 이르기까지 거치는 경로를 제어 흐름이라고 한다
명령형 프로그램은 작업 수행에 필요한 전 단계를 노출하여 흐름이나 경로를 자세히 서술한다

선언적 프로그램, 특히 함수형 프로그램은 독립적인 블랙박스 연산들이
최소한의 제어 구조를 통해 연결되어 추상화 수준이 높다
덕분에 코드가 짧아진다
연산을 체이닝하면 간결하면서 물 흐르는 듯한 표현적 형태로 프로그램을 작성할 수 있다
이는 제어 흐름과 계산 로직을 분리할 수 있고 코드와 데이터를 효과적으로 헤아릴 수 있다

메서드 체이닝

여러 메서드를 단일 구문으로 호출하는 OOP 패턴이다
메서드가 모두 동일 객체에 속해 있는 경우 메서드 흘리기라고도 한다
객체지향 프로그램에서 불변 객체에 많이 적용하는 패턴이지만
함수형 프로그래밍에도 잘 맞는다

'Functional Programming'.substring(0, 10).toLowerCase() + ' is fun'
위와 같은 코드를 함수형으로 리팩토링 하면

concat(toLowerCase(substring('Functional Programming', 1, 10)), ' is fun')

이런 식으로 작성할 수 있다
하지만 이렇게 작성하면 가독성이 좋지 않다

함수 체이닝

객체지향은 주로 상속을 통해 코드를 재사용 한다
함수형 프로그래밍은 접근 방법이 다르다
자료구조를 새로 만들어 요건을 충족시키는 것이 아니라
배열 등의 흔한 자료구조를 이용해 다수긔 굵게 나뉜 고계 연산을 적용한다

람다 표현식

함수형 프로그래밍의 람다 표현식(화살표 함수)은 익명 함수를 단축된 구문으로 나타낸다
람다 표현식은 항상 어떤 값을 반환하게 만들어 함수 정의부를 확실히 함수형으로 굳힌다
함수형 프로그래밍은 map, reduce, filter 등 고계함수를 적극 사용하길 권장한다
자바스크립트의 전신이자 원조 함수형 언어인 LISP 의 이름은 리스트 처리기에서 비롯된 것이다
함수형 배열 연산을 지원하는 array extras 함수는 ES5 에도 있지만
함수형 라이브러리인 로대시JS 를 사용하면 유사한 다른 연산도 포괄하는 완전한 솔루션을 만들 수 있다
로대시JS 는 함수형 프로그램을 작성하도록 유도하는 중요 장치를 제공하고 여러 공통 프로그래밍 작업을 처리하는데 유용한 도우미 함수들을 풍성하게 지원한다

로대시JS 는 언더스코어라는 유명 프로젝트에서 파생된 라이브러리로
내부적으로 함수 체인을 우아하게 구축하는 방향으로 재작성되었다

lodash

_map()

로대시의 map 함수는 배열뿐만 아니라 객체에도 사용 가능하고
크로스 브라우징 을 고려하여 작성되어 있다

import _ from 'lodash';

// Lodash를 사용하는 예제
const array = [1, 2, 3];
const doubled = _.map(array, x => x * 2);
console.log(doubled); // [2, 4, 6]

const doubled2 = _(array).reverse().map(x => x * 2);
console.log(doubled2) // [6, 4, 2]

_(array).reverse().map(x => x * 2) 와 같이
언더스코어 괄호로 변수를 감싸면 이후 로대시 함수들을 연결해서 사용할 수 있다

느긋한 함수 체인

FP 의 선언적 모델에 따르면 프로그램이란 순수 함수들을 평가하는 과정으로 볼 수 있다
순수 함수를 쌓아가면 한 눈에 읽히는 코드가 완성된다

추상화를 하면 자료구조에 영향을 끼치지 않는 방향으로 연산을 바라볼 수 있다
그래서 함수형 프로그래밍은 자료구조보다 연산에 중점을 둔다

_.chain() 함수는 주어진 입력을 원하는 출력으로 변환하는 lodash 연산들을 연결함으로 입력 객체의 상태를 확장한다
임의의 함수를 명시적으로 체이닝 가능한 함수로 만든다

Lodash의 _.chain 함수에서 "느긋한" 함수 체인(lazy chain)은 
최적화된 방법으로 체이닝된 함수를 처리하는 방식입니다. 
느긋한 함수 체인은 성능을 높이기 위해 데이터의 모든 항목을 
한 번에 처리하지 않고, 필요할 때까지 처리를 지연시킵니다.

즉, 체이닝된 함수를 통해 데이터가 필요할 때만 계산되며, 
이를 통해 불필요한 연산을 피하고 성능을 향상시킵니다. 
Lodash는 이를 "느긋한 평가"(lazy evaluation)라고 부릅니다.

데이터로서의 함수

함수형 프로그래밍을 사용하여 명령형 코드를 작성하면
SQL 처럼 어휘만으로 함수가 하는 일이 무엇인지 추론할 수 있다

믹스인

lodash 가 지원하는 믹스인 기능을 응용하면 핵심 라이브러리에 함수를 추가하여 확장 후, 원래 있던 함수처럼 체이닝할 수 있다

자바스크립트 믹스인
믹스인은 특정 형식과 연관된 함수를 부분적으로 추상화한 객체다
그 자체로 쓰이기 보다 다른 객체의 로직을 확장하는 용도로 활용된다

함수형 프로그래밍은 명령형 코드 위에 강력한 추상화를 제공한다
SQL 처럼 데이터를 함수형으로 모형화 할 수 있는데 이를 데이터로서의 함수라고 부른다
선언적으로 어떤 데이터가 출력되어야 하는지 서술할 뿐
어떻게 얻는지는 논하지 않는다
고수준의 추상화로 루프를 대체할 수 있다

재귀적 사고방식

전체 문제를 작은 문제들로 쪼갤 수 있다면
작은 문제를 하나씩 풀어가면서 전체 문제도 풀어낼 수 있다
하스켈, 스킴, 얼랭 등 순수 함수형 프로그래밍 언어는 처음부터 루프 구조가 없어
재귀는 필수적이다

자바스크립트에서도 XML, HTML 등을 파싱하는데 재귀를 다양하게 활용한다

재귀

재귀는 주어진 문제를 자기 반복적인 문제들로 잘게 분해 후
이들을 다시 조합해 문제의 정답을 찾는 기법이다
재귀 함수의 구성 요소

• 기저 케이스 (종료 조건)
• 재귀 케이스 (반복 조건)
  기저 케이스는 재귀 함수가 구체적인 결과를 바로 계산할 수 있는 입력 집합이다
  재귀 케이스는 함수가 자신을 호출하 ㄹ떄 전달한 입력 집합을 처리한다
  함수가 반복될수록 입력 집합이 점점 작아지면서 기저 케이스로 빠지면
  하나의 값으로 귀결된다

재귀적으로 생각하기

reduce 같은 하수를 쓰면 루프는 물론 리스트 크기조차 신경 쓸 필요가 없다
첫 번째 원로슬 나머지 원소들과 순차적으로 더해가며 결괏값을 계산하는
재귀적 사고방식을 적용해야 한다
이 사고방식을 확장하면 수평 사고라고 불리는 일련의 연산을 수행하는 과정으로 바라볼 수 있다

재귀는 변이가 없으므로 더 강력하고 표현적 방식으로 반복을 대체할 수 있다

재귀적 덧셈

function sum(arr) {
	if(_.isEmpty(arr)) return 0
  	return _.first(arr) + sum(_.rest(arr))
}

first 와 rest 로 첫 번쨰 원소와 나머지 원소를 분리할 수 있다

재귀의 성능

재귀와 반복문의 성능 차이는 미비해졌다
컴파일러는 영리하게 루프를 최적화 할 수 있도록 진화했고
ES6 부터는 꼬리 호출 최적화가 추가되어 성능에는 큰 차이가 없다

꼬리 호출 최적화는 사파리 브라우저를 사용하는 경우에만 해당되는 이야기이므로 여전히 재귀 함수 사용에 주의해야 한다

꼬리 호출 최적화

컴파일 단계에서 재귀 함수 호출의 메모리 사용을 줄이고 성능을 향상시키기 위해 사용되는 기술
꼬리 호출은 함수가 자신을 호출한 후 더 이상 추가 작업을 수행하지 않고
추가 작업을 실행하지 않고 호출 결과를 바로 반환하는 형태를 말한다

전통적인 재귀 함수의 동작 방식은
재귀 호출의 가장 깊은 곳까지 가면서 각각의 스택 프레임을 생성하며
호출 스택에 추가했다가 가장 깊은 곳부터 역순으로 함수가 실행되면서 돌아온다
꼬리 호출 최적화가 적용되면
가장 깊은 곳까지 가면서 각각의 함수가 호출되며 값을 계산하고, 호출된 함수가 이전 호출의 스택 프레임을 재사용하며
가장 깊은 곳에서 함수의 결과를 반환함과 함께 종료된다

호출 스택도 하나만 사용되고, 과정도 반으로 줄어드는 것으로 보인다

V8 엔진은 기본적으로 꼬리 호출 최적화를 지원하도록 설계되었지만
실제로는 지원하지 않는다고 한다 (구현 했으나 제거되었다고 함)
반복문이나 명시적인 스택 사용 같은 대체 방법을 사용하여 재귀 함수를 최적화 하는 방안도 고려해봐야 한다
현재 꼬리 호출 최적화를 지원하는 유일한 엔진은 Safari
컴파일 단계에서 지원하는 것이기 때문에 자바스크립트 엔진에서 지원하지 않으면
ES6 구문을 사용하더라도 꼬리 호출 최적화는 적용되지 않는다

트램폴린 기법

재귀 호출을 반복문으로 변환하여
함수가 직접 자신을 호출하지 않고 다음에 실행할 함수를 반환하도록 구현한다
이렇게 하면 새로운 스택 프레임을 생성하지 않고
기존의 스택 프레임을 재사용할 수 있어 메모리 관리에 좋다

팩토리얼 예제

function trampoline(fn) {
  return function(...args) {
    let result = fn(...args);
    while (typeof result === 'function') {
      result = result();
    }
    return result;
  };
}

function factorial(n, acc = 1) {
  if (n === 0) {
    return acc;
  } else {
    return () => factorial(n - 1, n * acc);
  }
}

const trampolinedFactorial = trampoline(factorial);
console.log(trampolinedFactorial(5)); // 출력: 120

책에서는 함수형 프로그래밍에 대해 집중하기 위해 재귀 함수가 무조건 좋은 것으로만
표현되어 있지만 실상은 그렇지 않다 항상 조심해야 한다
그렇다고 이 책이 나쁜 책이냐하면 절대 아니다

재귀적으로 정의한 자료구조

배열처럼 평탄한 자료구조를 파싱할 때 쓰는 함수형 기법은 트리 구조 데이터에 적절하지 않다
자바스크립트 언어는 내장 트리 객체를 지원하지 않으므로
트리 자료구조의 경우에는 노드 기반의 자료 구조를 만들어 사용해야 한다
트리는 루트 노드가 포함된 재귀적인 자료구조로
메인 로직은 자식을 추가하는 메서드에 있다
한 노드에 자식을 추가할 때 자식 노드의 부모 참조를 함께 추가해줘야 한다
재귀 알고리즘은 루트부터 모든 자식 노드를 타고 내려가면서 전위 순회 하는데
자기 반복적 특성 때문에 꼭 루트에서 시작하지 않더라도 같다

변이 및 부수효과 없는 자료형을 다룰 때 데이터 자체를 캡슐화하여
데이터에 접근하는 방법을 통제하는 것이 함수형 프로그래밍의 관건이다