‘스칼라로 배우는 함수형 프로그래밍-3’ 장 및 여러 레퍼런스를 참고해 작성 했습니다. List 자료 구조로 예제를 만들면서, 함수적 자료구조가 어떤건지설명합니다.
함수적 프로그램은 변수를 갱신하거나 변이 가능한(Mutable) 자료구조를 수정하는 일이 없어야 한다.
함수적 자료구조의 정의
함수적 자료구조란 오직 순순 함수만으로 조작되는 자료구조입니다.
- 순수 함수는 Data를 변경하거나, 기타 부수효과를 수행하는 일이 없어야 합니다.
- 함수적 자료구조는 불변(immutable)입니다.
쉬운 예를 들어보겠습니다.
ex) 3+4 를 하면 7이라는 값이 출력됩니다. 3과 4는 변하지 않고 7이라는 새로운 정수가 생성됩니다. 별것 아닌것 같지만 함수형 자료구조의 핵심입니다. 리스트 형태도 마찬가지입니다. 자료구조가 계속 새로 생성된다면 오버헤드가 크지않을까? 라는 생각을 할 수도 있지만 그렇지 않습니다. (이유는 아래에 설명하겠습니다.)
scala 에서 자료 형식을 도입할 때에는 trait 키워드를 사용합니다.
- trait 키워드로 정의하는 ‘특질(trait)’은 하나의 추상 인터페이스로, 필요하다면 일부 메서드의 구현을 담을 수도 있습니다. Java의 인터페이스 정도로 생각하면 될것 같습니다.
- trait 앞에 sealed를 붙이는 것은 이trait의 모든 구현이 반드시 이 파일 안에 선언되어 있어야 함을 뜻합니다. (즉 상속 혹은 믹스인 을 외부에서 할 수 없다는 말 입니다.)
sealed trait List 다음에 형식 매개변수 [+A]안에 있는 +는 공변[covariant]을 뜻 합니다.
기본적으로 List는 위 그림처럼 LinkedList 구조로 이루어져 있습니다.
패턴부합(PatternMatching)
위와 같은 함수들을 List의 동반객체(companion object)라고 부릅니다.
- 동반객체는 자료 형식의 이름과 같은 object로, 자료 형식의 값들을 생성하거나 조작하는 여러 편의용 함수들을 담는 목적으로 쓰입니다.
예상되는 결과값은??? 3 패턴매칭의 예를 잠깐 살펴봤습니다.
함수적 자료구조의 자료 공유
자료가 불변이라면, 예를 들어 List에 요소를 추가하거나, List에서 요소를 제거하는 함수는 어떻게 작성해야 할까?
- List (xs)의 앞에 새로운 요소 1를 추가하려면 Cons(1, xs)라는 새 List를 생성합니다.
- 함수적 자료구조는 xs를 복사 할 필요 없이 재사용합니다.
이를 자료 공유(data sharing)라고 부릅니다. 자료 공유를 효율적으로 하려면 함수를 좀 더 효율적으로 구현해야 합니다.
- 자료가 변하거나 깨지지 않도록 방어적으로 복사본을 만들 필요가 없습니다.
- myList = Cons(x, xs) 에서 첫 요소를 제거하려면, 꼬리 xs를 반환합니다. 실질적인 제거는 일어나지 않습니다.
- 원래의List은 여전히 사용가능한 상태이며, 이를 두고 함수적 자료구조는 영속적(presistent)이라고 말합니다.
앞서 말 했듯이 함수적 자료구조 에서 기존 List를 조작해 새로운 List를 생성 한다면, 복사 개념이 아니기 때문에 오버헤드가 없다고 할 수 있습니다. 오직 새로 조작되는 부분만 생성하기 때문입니다.
예제 : List와 패턴매칭을 이용해 List의 head와, tail을 추가하는 함수를 각각 만들어 보자.
자료 공유의 효율성
예제 : tail을 일반화해서, List에서 처음 n개의 요소를 제거하는 함수 drop을 구현.
예제 : 주어진 술어와 부합하는 List의 앞 요소들을 제거하는 함수 dropWhile을 구현.
예제 : List의 마지막 요소를 제외한 모든 요소를 반환하는 init을 구현.
init의 경우 List의 제일 마지막까지 List를 순회 해야하기 때문에 수행시간이 효율적이지 않습니다. 순수 함수적 자료구조를 작성의 관건은 자료 공유를 현명하게 활용 하는 방법을 찾아야 한다는 것 입니다. 이 문제를 해결하기 위해서는 List외에 Array, Vector 같은 자료구조를 사용을 권합니다.
고차 함수를 위한 형식 추론 개선
dropWhile같은 고차 함수에는 흔히 익명 함수를 넘깁니다.
인수 f 에 익명 함수를 지정해서 호출하기 위해서는 그 익명 함수의 인수형식을 명시해야합니다.(casting)
x에 Int를 명시적으로 표기하는것은 다소 번거롭습니다. 이럴 경우 인수를 2그룹으로 나누면 scala에서 타입 추론을 통해 타입을 추론 할 수 있습니다. 이런 것을 커링이라고 부릅니다.
예제 : 커링을 이용해 dropWhile을 변경 하라.
List에 대한 재귀와 고차 함수로의 일반화
위 코드 중 sum과 product의 구현은 매우 비슷한 성격을 가지고 있다. 매개변수타입 과 반환 값은 다르지만 로직자체는 매우 유사하다고 볼 수 있습니다. 이런 코드 중복은 부분 표현식들을 추출해서 함수 인수로 대체함으로써 코드를 일반화 하는 것이 항상 가능합니다.
코드에서 sum2는 x + y라고 명시적으로 함수를 구현했지만 product2는 _ * _ 라고 표현했다. 이런 밑줄 표기법은 매개변수들이 한번씩만 사용 될 경우에 사용 할수 있고 기본적으로 왼쪽에서 오른쪽을 순서로 한다.
예제 : foldRight를 이용해서 List의 길이를 계산하라.
예제 : “def foldLeft[A,B](as: List[A], z: B)(f: (B, A) => B): B = “ 를 이용해 foldLeft를 작성해보고 sum과 product를 foldLeft를 사용해 작성해보자.
예제 : foldLeft를 이용해 List(1,2,3) -> List(3,2,1)로 바꾸는 reverse 함수를 작성 하라.
예제 : foldLeft는 foldRight를, foldRight는 foldLeft를 이용해 구현.
예제 : List 2개를 합치는 Append를 구현
그 외에 List 조작 함수들
List를 처리하는 함수를 작성할 때에는 명시적인 재귀함수를 일반화하는 여러 방법을 고려해 보는 습관을 가지는 것이 좋습니다.
예제 : 정수 List의 각 요소에 1을 더해서 목록을 변환하는 함수를 작성하라.(새 List를 돌려주는 순수 함수여야 함.)
예제 : List[Double]을 String으로 변환하는 함수를 작성하라.
예제 : “def map[A,B](as : List[A])(f: A => B): List[B] =” List의 구조를 유지하면서 List의 각 요소를 수정하는 작업을 일반화한 함수 map을 작성하라.
예제 : “def filter[A](as : List[A])(f: A => Boolean): List[A] =” List에서 주어진 조건을 만족하지 않는 요소들을 제거하는 함수 filter를 작성하라.
예제 : “def flatMap[A, B](as : List[A])(f: A => List[B]): List[B] =” map과 비슷하지만 하나의 요소가 아니라, List를 최종 결과 List에 삽입하는 함수 flatMap을 작성하라.
예제 : flatMap을 이용해 filter를 구현하라.
예제 : List 2 개를 받아서 대응되는 요소들을 더한 값들로 이루어진 새 List를 구축하는 함수를 작성하라. 예를 들어 List(1,2,3) 과 List(4,5,6)은 List(5,7,9)가 되어야 한다.
예제 : 위 예제를 정수나 덧셈에 국한되지 않도록 일반화 해라. 함수의 이름은 zipWith로.
스칼라 표준 라이브러리에 List가 있습니다. 그리고 위에 구현한 함수들은 표준 라이브러리들로 정의 되어 있기 때문에, 지금처럼 별도로 구현할 필요없습니다. 표준 라이브러리 버전은 Cons를 ::로 사용하고 있고, 명칭은 콘즈(cons)라고 부릅니다. Cons(x,xs) 는 x ::xs 로 사용합니다.
단순 구성요소들로 목록 함수를 조립할 때의 효율성 손실
List의 한 가지 문제는, 어떤 연산이나 알고리즘을 아주 범용적인 함수들로 표현할 수 있긴 하지만 그 결과로 만들어진 구현이 항상 효율적이지는 않습니다. 같은 입력을 여러 번 훑는 구현이 만들어질 수 있으며, 이른 종료를 위해서는 명시적인 재귀 루프를 작성해야 할 수 있습니다.
예제: ListA가 있다면 다른 ListB가 A에 포함되는 List인지를 구하는 함수를 구하라. (List(1,2,3,4,5)의 서브 List는 List(2,3,4), List(1,2), List(4,5) 등)
위 는 Scala로 작성한 예제들이며 Kotlin으로도 작성해봤습니다.
요약
함수형 자료구조는 여러가지 함수를 통해 데이터를 생성하고 전달합니다. Data를 조작은 그 자리에서 변경하거나 기타 부수효과를 수행하는 일이 없어야 합니다.
함수형 프로그래밍에서 사용되는 자료구조중 가장 일반적인 함수형 자료구조로는 스칼라 표준 라이브러리에서 제공하는 List라는 자료구조가 있습니다. List는 단일 연결구조(LinkedList)이기 때문에 전체 사이즈를 가져오거나, List의 마지막 요소에 접근하는 경우에는 효율적이지 않습니다.
자료구조를 사용하는 목적과 효율을 고려해 적절히 사용하는 습관이 중요 합니다.
# 전체 소스(개인적인 풀이)
