예외를 던지는 것은 부수 효과이며 바람직하지 않은 동작이다.

예외를 던진다는 것은 제어 상실을 의미한다.
예외가 던져지면 호출 스택을 거슬로 올라가며 catch되거나 처리되지 않아 crash가 나거나 한다. 

이런 상황은 복잡도가 높아지게 만드는 원인이다.

함수형 프로그래밍에서는 실패와 예외를 일반적인 값으로 표현할 수 있다. 그리고 오류 처리를 하는 고차함수를 작성해 처리한다. 
이렇게 하면 참조투명성을 유지할 수 있다. 

4.1 예외를 던지는 것의 문제점

fun failingFn(i: Int): Int {
    val y : Int = throw Exception("boom")
    return try {
        val x = 42 + 5
        x + y
    } catch (e: java.lang.Exception) {
        43
    }
}

이 함수에서는 예외를 던지고 있다. try 블럭에서 던진 예외가 아니기 때문에 프로그램이 종료될 것이다.

y를 치환할 수 있을까? y를 throw Exception()으로 치환한다면 

fun failingFn(i: Int): Int {
    return try {
        val x = 42 + 5
        x + throw Exception("boom")
    } catch (e: java.lang.Exception) {
        43
    }
}

try 블럭 안에서 예외가 발생하고 catch에서 예외가 처리되어 43이라는 결과가 반환될 것이다. 

이렇듯 예외는 참조투명하지 않을 수 있고, 문맥에 의존적이다. 따라서 단순한 추론이 어려워진다. 

또한 failingFn의 반환타입은 Int는 이 함수에서 예외가 발생한다는 것을 알려주지 못한다.
예외가 발생한다는 사실은 런타임에 알 수 있다. 

4.2 예외에 대한 문제가 있는 대안

다음의 함수는 리스트의 평균을 계산하는 함수이다. 리스트가 비어있으면 평균을 계산할 수 없어 예외를 던진다.

fun mean(xs: List<Double>): Double =
    if (xs.isEmpty()) {
        throw ArithmeticException("mean of empty list!")
    } else {
        xs.sum() / xs.size
    }

이 함수는 Partial function(부분함수)이다.

부분함수는 입력 중 일부에 대해 결과가 정의되지 않은 함수이다. 
위 함수 역시 예외가 던져지면 호출부에서 액션을 처리해야하기 때문에 빈 리스트가 들어왔을 때 결과가 정해지지 않았다 라고 볼 수 있다. 

해결법 1 - 센티넬 값

예외를 던지는 대신에 Double 타입의 가짜 값을 반환하는 방법이다.

Double.NaN 타입을 만들어 반환하거나, null 값을 반환하게 할 수 도 있다. 

이 방식은 이런 단점이 있다.

  • 오류가 조용히 전파됨. 호출한 쪽에서 조건 검사를 잊을 수 있음
  • 호출 지점에서 if를 사용해 항상 확인해야함 -> 보일러 플레이트 코드 증가
  • 다형적인 코드에 적용할 수 없다. 모든 타입을 아우르를 센티넬 값이 존재하지 않을 수 있다. 
  • 호출하는 쪽에서 정책이나 호출 규약을 지키도록 요구한다. mean 함수의 적절한 사용법은 호출자가 호출만 하는 것이다.

해결법 2 - 디폴트 값 제공

fun mean(xs: List<Double>, onEmpty: Double) =
	if (xs.isEmpty()) onEmpty else xs.sum() / xs.size

이렇게 호출 할 때 디폴트 값을 주게 할 수도 있다. 

이럴 경우

  • 호출하는 쪽에서, 함수 결과가 없는 경우(디폴트 값을 주는 경우)가 언제인지 이해해야한다.
  • 디폴트 값이 Double로 한정된다.
  • mean이 정의되지 않았을 때 특정 동작을 수행하게 하고 싶다면, 디폴트 값으로는 처리할 수 없다. 

 

4.3 Option으로 성공 상황 인코딩 하기

함수의 반환타입에 함수가 결과를 제공하는지, 실패나 예외상황인지를 명시적으로 표현하는 방법이다.
이 방법은 호출하는 쪽으로 오류 처리 전략을 미룬다고 할 수도 있다. 

이 때 사용하는 타입이 Option이다.

sealed class Option<out A>
data class Some<out A>(val get: A) : Option<A>()
object None : Option<Nothing>()

None은 정의 안됨, Some은 정의 됨을 표현한다. 

fun mean(xs: List<Double>): Option<Double> =
    if (xs.isEmpty()) {
        None
    } else {
        Some(xs.sum() / xs.size)
    }

Option을 사용하면 이렇게 mean을 정의할 수 있다. 반환 타입으로 결과 없음을 표시할 수 있게 되었다.

Option에  대한 기본함수

 Option은 3장에서 정의한 List에 원소가 하나만 들어가는 타입이라고 생각할 수 있다. 

List의 함수는 Option에도 상응하는 함수가 존재한다. 이런 함수들을 확장 함수로 구현해보자.

fun <A, B> Option<A>.map(f: (A) -> B): Option<B> =
    when (this) {
        is None -> None
        is Some -> Some(f(this.get))
    }

fun <A, B> Option<A>.flatMap(f: (A) -> Option<B>): Option<B> =
    when (this) {
        is None -> None
        is Some -> f(this.get)
    }

fun <A> Option<A>.getOrElse(default: () -> A): A =
    when (this) {
        is None -> default()
        is Some -> this.get
    }

fun <A> Option<A>.orElse(ob: () -> Option<A>): Option<A> =
    when (this) {
        is None -> ob()
        is Some -> this
    }

fun <A> Option<A>.filter(f: (A) -> Boolean): Option<A> =
    when (this) {
        is None -> None
        is Some -> {
            if (f(get)) this
            else None
        }
    }

기본적인 함수들을 구현해봤다. 이런 고차함수를 사용하는 시나리오를 살펴보자.

map

data class Employee(
    val name: String,
    val department: String,
    val manager: Option<String>
)

fun lookupByName(name: String): Option<Employee> = TODO()
fun timDepartment(): Option<String> =
    lookupByName("Tim").map { it.department }

timDepartment는 lookupByName으로 Option<Employee>를 받아 Employee의 department를 반환해주는 함수이다. 

timDepartment는 lookupByName의 결과를 검사할 필요가 없다. None이면 map의 결과도 None이기 때문이다. 

val unwieldy: Option<Option<String>> = 
	lookupByName("Tim").map {it.manager}

manager attribute로 map을 수행하면 Option<Option<String>>자료형이 나온다. 이런 상황에서 Option<String>을 반환받고 싶다면 flatMap을 사용하면 된다. 

val manager: Option<String> = lookupByName("Tim")
	.flatMap { it.manager }

filter

fiilter를 사용하면 성공적인 값이 술어를 만족하지 않을 때 성공을 실패로 변환할 수 있다. 

일반적으로 Option은 map, flatMap, filter 를 사용해서 변환한 후 getOrElse를 써서 오류 처리를 한다.

val dept: String = lookupByName("Tim")
    .map { it.department }
    .filter { it != "Accounts" }
    .getOrElse { "UnEmployed" }

이 식에서 Tim이 존재하지 않거나, department가 Accounts가 아니라면 default값인 "UnEmployed"를 반환하게 했다. 

각 연산에서 실패한다고 예외가 발생하지 않는다. 실패를 뜻하는 Option 타입인 None을 반환할 뿐이다.

그리고 각 단계마다 None을 검사하지 않는다. 변환과 연산을 다 적용한 후 마지막에 None 검사를 하면 되는 것이다. 

연습문제 4.2

flatMap을 이용해 variance 함수를 구현하라. 시퀀스의 평균이 m 이면 분산(variance)는 (x-m)^2의 평균이다. 
mean 함수를 사용해 구현할 수 있다.

fun mean(xs: List<Double>): Option<Double> =
    if (xs.isEmpty()) {
        None
    } else {
        Some(xs.sum() / xs.size)
    }
    
fun variance(xs: List<Double>): Option<Double> =
    mean(xs).flatMap { m ->
        mean(xs.map { x -> (x-m).pow(2) })
    }

 4.3.2 Option 합성, 끌어올리기, 예외기반 API 감싸기

Option 자료형을 사용하기 시작했으면 전체 코드기반을 Option으로 바꿔야할까?
파라미터나 반환타입을 모두 Option<A>이런식으로 바꿔야하는 것일까?

아니다. 일반함수를 끌어올려서 Option에 대한 함수로 만들 수 있다. 

Option의 확장함수인 map을 보자.

fun <A, B> Option<A>.map(f: (A) -> B): Option<B> =
    when (this) {
        is None -> None
        is Some -> Some(f(this.get))
    }

map을 사용하면 Option<A> 타입에 (A) -> B 함수를 사용해서 Option<B>를 얻을 수 있다. 

(A) -> B를 Option<A> -> Option<B>로 변환한다고 볼 수 있다.

fun <A, B> lift(f: (A) -> B): (Option<A>) -> Option<B> =
    { oa -> oa.map(f) }

val toInt: (Option<Double>) -> Option<Int> =
    lift { it.toInt() }

fun main() {
    println(toInt(Some(12.3)))
}

Double.toInt() 대신 Option<Double>.toInt()를 만들 필요가 없다. 있던 함수를 끌어올리면 된다. 

예제

자동차 보험회사의 웹사이트를 구현한다고 하자.
사용자가 자신의 정보(나이, 과속 티켓 개수)를 넣으면 보험 할인률을 계산해주는 페이지를 만들고 싶다.  

fun insuranceRateQuote(
    age: Int,
    numberOfSpeedingTickets: Int
): Double = TODO()

이렇게 정보를 넣으면 할인률(Double)을 반환해주는함수가 있다. 이 함수만 호출하면 된다. 

하지만 사용자 입력 폼은 문자열을 받기 때문에 정수로 파싱해야한다. 
정수가 아닌 문자열이 들어오면 NumberFormatException 발생시킨다. 

먼저 예외가 발생하면 None을 반환해주는 catches 함수를 작성하자.

fun <A> catches(a: () -> A): Option<A> =
    try {
        Some(a())
    } catch (e: Throwable) {
        None
    }

catches 함수를 사용해 타입 캐스팅 에러처리를 할 수 있다.

fun parseInsuranceRateQuote(age: String, speedingTickets: String) : Option<Double> {
    val optAge: Option<Int> = catches { age.toInt() }
    val optTickets: Option<Int> = catches { speedingTickets.toInt() }
    
    return insuranceRateQuote(optAge, optTickets) // !! 에러
}

exception을 잡는 것은 성공했지만, insuranceRateQuote는 Option 타입을 인자로 받지 않기 때문에 그대로 전달 할 수 없다. 
Option을 사용할 수 있게 끌어올려야한다. 

연습문제 4.3

두 Option 값을 이항함수를 통해 조합하는 제네릭 함수 map2를 작성하라. 두 Option 중 어느 하나라도 None이면 반환값도 None이다.

fun <A, B, C> map2(a: Option<A>, b: Option<B>, f: (A, B) -> C): Option<C> = 
    if (a is Some && b is Some) {
        Some(f(a.get, b.get))
    } else {
        None
    }
    
fun <A, B, C> map2(a: Option<A>, b: Option<B>, f: (A, B) -> C): Option<C> = 
    a.flatMap {  aa ->
        b.map {  bb ->
            f(aa, bb)
        }
    }

map2 함수를 이용해 parseInsuranceRateQuote를 구현할 수 있다. 

fun parseInsuranceRateQuote(age: String, speedingTickets: String) : Option<Double> {
    val optAge: Option<Int> = catches { age.toInt() }
    val optTickets: Option<Int> = catches { speedingTickets.toInt() }
    
    return map2 (optAge, optTickets) { a, t ->
    	insuranceRateQuote(a, t) 
    }
}

이렇게 하면 기존 insuranceRateQuote를 변경하지 않고도 Option 타입을 사용할 수 있다.

4.3.3. for comprehension 사용하기

map2 함수에서 flatMap과 map을 연쇄적으로 호출해 Option 값을 뽑아냈다.
이런 연산을 더 보기 쉽게 명령형 코드처럼 만들어주는 것이 for comprehension이다.

코틀린의 기본 요소로는 제공되지 않고 Arrow라는 라이브러리에서 지원된다. 코드를 보면 다음과 같다. 

fun <A,B,C> map2(oa: Option<A>, ob: Option<B>, f: (A, B) -> C) = 
	Option.fx {
    	val a = oa.bind()
        val b = ob.bind()
        f(a,b)
    }

이렇게 bind()를 통해 사용할 수 있다. 컴파일러는 각 식을 flatMap으로 바꾸고, 마지막 식은 결과를 돌려주는 map 함수로 변환한다.

fun <A, B, C> map2(a: Option<A>, b: Option<B>, f: (A, B) -> C): Option<C> = 
    a.flatMap {  aa ->
        b.map {  bb ->
            f(aa, bb)
        }
    }

위에서 정의한 map2 함수보다 읽기 편한 것을 볼 수 있다. 

 

4.4 성공과 실패를 Either로 인코딩하기

Option사용한 예외처리 방식은 실패와 예외를 일반적인 값으로 표현하는 것이었다.

하지만 Option은 예외적인 상황에서 무엇이 잘못된 것인지 알려주지 못한다. None을 반환할 뿐이다.

어떤 예외가 발생했는지 알고싶다면, Either 타입을 사용할 수 있다. 

sealed class Either<out E, out A>
data class Left<out E>(val value: E) : Either<E, Nothing>()
data class Right<out A>(val value: A) : Either<Nothing, A>()

Option 과 마찬가지로 sealed 클래스를 상속받는 2 가지 타입이 있지만, Either는 두 타입 모두 값을 유지한다는 데 차이점이 있다.

Right는 성공을 나타내고 Left는 실패를 나타낸다.

fun mean(xs: List<Double>): Either<String, Double> =
    if (xs.isEmpty())
        Left("mean of empty list!")
    else
        Right(xs.sum() / xs.size)

fun safeDiv(x: Int, y: Int): Either<Exception, Int> =
    try {
        Right(x / y)
    } catch (e: Exception) {
        Left(e)
    }
    
fun <A> catches(a: () -> A) : Either<Exception, A> =
    try {
        Right(a())
    } catch (e: Exception) {
        Left(e)
    }

이렇게 Either를 사용해 함수를 정의할 수 있다.

fun main() {
    val toInt: Either<Exception, Int> = catches1 { 
        "123".toInt()
    }
    when (toInt) {
        is Right -> {
            println(toInt.value)
        }
        is Left -> {
            toInt.value.printStackTrace()
        }
    }
}

사용할 때는 타입매칭을 통해 성공 실패 케이스를 구분해준다.

 

데이터를 검증하기 위해 Either 사용하기

data class Name(val value: String)
data class Age(val value: Int)
data class Person(val name: Name, val age: Age)

fun mkName(name: String): Either<String, Name> =
    if (name.isBlank()) Left("Name is empty.")
    else Right(Name(name))

fun mkAge(age: Int): Either<String, Age> =
    if (age < 0) Left("Age is out of range")
    else Right(Age(age))

fun mkPerson(name: String, age: Int): Either<String, Person> =
    map2(mkName(name), mkAge(age)) { n, a -> Person(n, a) }

이렇게 객체를 생성하는 메소드를 만들고 Either를 반환하게 만들었습니다. 

mkName과 mkAge를 사용해서 Person 객체를 만들때 따로 에러처리를 해주지 않아도 됩니다. 

fun main() {
    println(mkPerson("", 12))
    println(mkPerson("", -1))
    println(mkPerson("d", -1))
    println(mkPerson("John", 12))
}

각 케이스에 맞춰 에러처리가 되는 것을 볼 수 있습니다. 

함수형 프로그래밍에서는 변수를 갱신하거나 가변 데이터 구조를 변경하지 않는다고 얘기했다.

그러면 어떤 유형의 데이터 구조를 사용해야할까?

3.1  함수형 데이터 구조 정의하기

함수형 데이터 구조는 순수함수만으로 조작된다. 순수함수는 제자리에서 데이터를 변경하거나 부수 효과를 만들어내면 안된다.

불변이어야한다. 빈 리스트는 영원히 비어있고 변하면 안된다. 
리스트 두 개를 이어붙이면 원래 리스트 2개는 그대로 있고 새로운 리스트가 생겨야한다.

변경을 못한다면 데이터 복사를 더 많이 해야한다는 것일까? "아니다."

함수형 데이터 구조의 예시로 단일 연결 리스트를 보자. 

sealed class List<out A>

object Nil : List<Nothing>()
data class Cons<out A>(val head: A, val tail: List<A>) : List<A>()

sealed 클래스로 List를 만들고 빈리스트를 의미하는 Nil과 데이터를 담고있는 Cons를 정의했다. 

Cons는 첫 번째 원소 head와 나머지 원소 리스트인 tail로 이뤄진다. 

List에 타입 파라미터로 <out A>를 사용해 다형적인 데이터 타입을 만들었다.
out은 타입 파라미터가 공변적이라는 것이다.  X가 Y의 자식 클래스라면 List<X>도 List<Y>의 하위타입이라는 것이다. 

https://yoonda.tistory.com/22

 

[Kotlin] Generics 공변성, 반공변성(out, in)

Kotlin에서 List, Map, Set같은 Collections 클래스를 사용할 때, List 이런식으로 제네릭 타입을 지정할 수 있다. 제네릭을 사용하면 타입 안정성을 얻을 수 있다. 하지만 제네릭으로 지정한 타입 이외에

yoonda.tistory.com

 

val nil: List<Double> = Nil
val a1: List<Int> = Cons(1, Nil)
val a2: List<String> = Cons("a", Cons("b", Nil))

이런식으로 데이터를 만들 수 있다.

Nil은 List<Nothing> 타입이다. Nothing은 모든 타입의 하위타입이므로, 어떤 타음의 리스트로도 캐스팅 될 수 있다. 

이제 이 함수형 데이터 타입을 이용하면, Nil일 때와 Cons 일 때를 구분해서 동작을 하게 할 수 있다. 이를 위해 사용되는 패턴 매칭에 대해 알아보자. 

3.2 함수형 데이터 구조 다루기

List를 쉽게 생성할 수 있는 of 함수를 만들자.

sealed class List<out A> {
    companion object {
        fun <A> of(vararg aa: A): List<A> {
            val tail = aa.sliceArray(1 until aa.size)
            return if (aa.isEmpty()) Nil else Cons(aa[0], of(*tail))
        }
    }
}

val list = List.of(1, 2, 3, 4, 5, 6)

가변인자와 Spread 연산자를 이용해서 of함수를 정의하였다. 
List라는 자료구조 자체가 tail로 List 형을 갖고있는 재귀적인 타입이므로, 생성하는 연산도 재귀함수로 작성하였다. 
재귀적인 자료구조에 대한 연산은 재귀적으로 작성하는 것이 일반적이다. 

코틀린에서는 when을 통해 매칭을 할 수 있다. 

fun sum(ints: List<Int>): Int = 
    when (ints) {
        is Nil -> 0
        is Cons -> ints.head + sum(ints.tail)
    }

fun product(doubles: List<Double>): Double =
    when (doubles) {
        is Nil -> 0.0
        is Cons -> doubles.head + product(doubles.tail)
    }

이런 식으로 원소들의 합과 곱을 계산하는 함수를 정의할 수 있다. 

3.3 함수형 데이터 구조 안의 데이터 공유

함수형 데이터 타입은 데이터가 불변이다. 바꿀 수 없다면, 리스트에 원소를 추가하거나 삭제는 어떻게 해야할까?

기존 리스트 xs가 있다면 Cons(1, xs) 처럼 앞에 붙이거나 xs.tail을 해서 첫 번째 요소를 제외한 리스트를 반환할 수 도 있다. 

불변이기 때문에 참조가 같아도 된다. 다른 곳에서 변경될 일이 없기 때문이다. 

두 리스트를 이어붙이는 함수를 보자.

fun <A> append(a1: List<A>, a2: List<A>): List<A> = 
    when (a1) {
        is Nil -> a2
        is Cons -> Cons(a1.head, append(a1.tail, a2))
    }

a1의 마지막 포인터를 바꿀 수 없기 때문에 a1의 원소들을 다 복사해야한다. a1을 다 복사하고 나면 a2로 참조만 하면 되므로 시간복잡도는 a1의 길이에 따라 결정된다. 

연습문제 3.1

List의 첫 번째 원소를 제거하는 tail함수 구현. 상수 시간에 끝나야 함.

fun <A> tail(xs: List<A>): List<A> =
    when (xs) {
        is Nil -> Nil
        is Cons -> xs.tail
    }

연습문제 3.2

리스트의 첫 원소를 다른 값으로 대치

fun <A> setHead(xs: List<A>, x: A): List<A> =
    when (xs) {
        is Nil -> Nil
        is Cons -> Cons(x, xs.tail)
    }

연습문제 3.3

tail을 일반화한 drop을 작성하라. 리스트의 앞에서부터 n개의 원소를 제거한다. 

fun <A> drop(l: List<A>, n: Int): List<A> =
    if (n == 0) l else drop(tail(l), n - 1)

연습문제 3.4

dropWhile을 구현하라. List의 맨 앞부터 주어진 술어를 만족하는 연속적인 원소를 삭제한다. 

fun <A> dropWhile(l: List<A>, f: (A) -> Boolean): List<A> =
    when (l) {
        is Nil -> Nil
        is Cons -> {
            if (f(l.head)) {
                dropWhile(l.tail, f)
            } else {
                l
            }
        }
    }

연습문제 3.5

마지막 원소를 제외한 리스트를 반환하는 init함수를 정의하라.

fun <A> init(l: List<A>): List<A> = 
    when (l) {
        is Nil -> Nil
        is Cons -> {
            if (l.tail is Nil) {
                Nil
            } else {
                Cons(l.head, init(l.tail))
            }
        }
    }

3.4 고차함수로 일반화

fun sum(ints: List<Int>): Int = 
    when (ints) {
        is Nil -> 0
        is Cons -> ints.head + sum(ints.tail)
    }

fun product(doubles: List<Double>): Double =
    when (doubles) {
        is Nil -> 0.0
        is Cons -> doubles.head + product(doubles.tail)
    }

앞에서 본 sum과 product는 거의 차이가 없다.

이 함수들을 고차함수로 일반화 해보자.

fun <A, B> foldRight(xs: List<A>, z: B, f: (A, B) -> B): B =
    when (xs) {
        is Nil -> z
        is Cons -> f(xs.head, foldRight(xs.tail, z, f))
    }

fun sum2(ints: List<Int>): Int =
    foldRight(ints, 0) { a, b -> a + b }

fun product2(dbs: List<Double>): Double =
    foldRight(dbs, 1.0) { a, b -> a * b }

foldRight라는 값을 누적해서 계산하는 함수를 일반화하였다.

Nil이면 z라는 Cons는 f로 치환해 치환모델을 적용할 수도 있다. 

Cons(1, Cons(2, Nil)) -> f(1, f(2, z))

foldRight(Cons(1, Cons(2, Cons(3, Nil))), 0, { x, y -> x + y })
-> 1 + foldRight(Cons(2, Cons(3, Nil)), 0, {x, y -> x + y })
-> 1 + 2 + foldRight(Cons(3, Nil), 0, {x, y -> x + y})
-> 1 + 2 + 3 + foldRight(Nil, 0, {x, y -> x + y})
-> 1 + 2 + 3 +0

코틀린 표준 라이브러리의 리스트

코틀린의 기본 라이브러리 List는 read only인 List와 읽기 쓰기가 가능한 MutableList가 존재한다. 
하지만 내부적으로는 모두 가변 리스트(java의 ArrayList)를 사용한다. 

이로 인해 순수함수가 읽기 전용 List 를 다뤄도 데이터 오염이 발생할 수 있다. 

3.5 트리

앞에서 살펴본 함수형 데이터 타입인 List는 ADT(Algebraic Data Type; 대수적 데이터 타입)에 속한다.

ADT는 하나 이상의 데이터 생성자로 정의된 데이터 타입을 뜻한다.

Algebraic Data Type 이란?

ADT는 다른 자료형의 값을 가지는 자료형이다. 

예를 들어 아래와 같은 데이터 클래스가 있다. 

data class Person(val name: String, val age: Int, val email: String)

String, Int 자료형의 값을 가지는 Person 자료형이다. 

그리고 kotlin 의 enum과 sealed class 도 ADT라고 할 수 있다.

enum class Job {
    DOCTOR, OFFICER, DEVELOPER
}

sealed class Programmer {
    data class MobileProgrammer(val language: String): Programmer()
    data class ServerProgrammer(val language: String): Programmer()
}

enum과 sealed 클래스는
Job = DOCTOR or OFFICER or DEVELOPER,
Programmer = MobileProgrammer or ServerProgrammer 와 같이 or로 표시할 수 있다.

이런 타입을 합타입이라고 한다.

Person의 경우 name, age, email 등의 값이 정해져 있는 게 아니다. 
name: String 의 개수 * age: Int의 개수 * email: String의 개수 로 표현된다. 

이런 타입을 곱타입이라고 한다.

 

앞에서 정의한 List와 아래 Tree 등이 ADT에 속한다.

sealed class Tree<out A>
data class Leaf<A>(val value:A) : Tree<A>()
data class Branch<A>(val left: Tree<A>, val right: Tree<A>) : Tree<A>()

 

 

 

대수적 데이터 타입이(algebraic data type)이란? With Kotlin

함수형 프로그래밍을 공부하면 대수적(algebraic)이라는 표현을 접하게 됩니다. 아는것 같았지만.. 막상 설명하라고 하면 못하는… 항상 애매하게, 두리뭉실하게 넘어가다가 이번에 정리를 합니다

medium.com

2.1 고차 함수

함수형 프로그래밍에서는 함수도 값처럼 다룰 수 있다.

Int, String, List.. 처럼 함수 역시 변수에 대입하거나, 데이터 구조(Collections)에 저장하거나, 함수의 파라미터나 반환타입으로 사용할 수 있다는 뜻이다. 

고차 함수는 파라미터나 반환타입으로 함수를 사용하는 함수를 말한다. 

예제

이제 고차함수를 작성하는 예제를 보자.

어떤 정수의 대해 절대값과 팩토리얼을 계산해서 "The absolute value of -7 is 7" 이런 문자열을 반환해주는 함수이다. 

처음에는 고차함수를 사용하지 않은 형태를 보곘다. 

object Exam2_2 {
    private fun abs(n: Int) =
        if (n < 0) -n
        else n

    private fun factorial(i: Int): Int {
        fun go(n: Int, acc: Int): Int =
            if (n <= 0) acc
            else go(n - 1, n * acc)
        return go(i, 1)
    }

    fun formatAbs(x: Int): String {
        val msg = "The absolute value of %d is %d"
        return msg.format(x, abs(x))
    }

    fun formatFactorial(x: Int): String {
        val msg = "The factorial of %d is %d"
        return msg.format(x, factorial(x))
    }
}

fun main() {
    println(Exam2_2.formatAbs(-42))
    println(Exam2_2.formatFactorial(7))
}

factorial 함수는 내부 함수를 정의해서 재귀적으로 해결하였다. 
변수를 하나 두고 값을 누적계산할 수 도 있지만, 순수 함수로 만드려면 값을 변이할 수 없다. 

재귀 함수를 통해 factorial을 순수함수로 작성할 수 있다. 

 private fun factorial(i: Int): Int {
    tailrec fun go(n: Int, acc: Int): Int =
        if (n <= 0) acc
        else go(n - 1, n * acc)
    return go(i, 1)
}

factorial 함수는 return에서 함수를 호출하기만 하므로 꼬리 재귀로 콜스택을 줄일 수 있다. 
코틀린에서는 tailrec이라는 키워드를 사용해 꼬리 재귀함수라고 컴파일러에게 알려줄 수 있다.

다시 순수함수 얘기로 돌아가자.

포맷팅된 문자열을 반환해주는 formatAbs와 formatFactorial은 거의 같다. 두 함수를 일반화 해보자.

fun formatResult(name: String, n: Int, f: (Int) -> Int): String {
    val msg = "The %s of %d is %d."
    return msg.format(name, n, f(n))
}

이렇게 f라는 함수를 인자로 받는 함수를 정의할 수 있다. 이제 abs, factorial모두 이 함수를 통해 포맷팅된 문자열을 반환받을 수 있다. 

사용은 함수 인자 부분에 Callable Reference(자바의 메소드 참조)나 람다를 넘겨 사용할 수 있다.

fun main() {
    println(Exam2_2.formatResult("absolute value", -42, Exam2_2::abs))
    println(Exam2_2.formatResult("factorial", 7, Exam2_2::factorial))
}

연습문제 2.1

피보나치 수를 지역적인 꼬리재귀함수를 사용하여 작성하라.

fun fib(i: Int): Int {

    tailrec fun go(beforeValue: Int, currentValue: Int, currentIndex: Int, maxIndex: Int): Int =
        if (currentIndex > maxIndex) beforeValue
        else go(currentValue, beforeValue + currentValue, currentIndex + 1, maxIndex)

    return go(0, 1, 1, i)
}

 

 

2.2 다형적 함수: 타입 추상화

fun formatResult(name: String, n: Int, f: (Int) -> Int): String

앞에서 이런 고차함수를 만들었었다. 

f는 Int값을 받고 Int값을 리턴한다. 오로지 Int 타입에 대해서만 작동하는 함수이다.
이런 함수를 단형적 함수라고 한다. 

특정 타입에 제한된 것이 아닌 어떤 타입에도 작동하는 함수를 다형적 함수라고 한다. 

여기서 얘기하는 다형(polymorphism)은 객체지향의 상속을 통한 다형성이 아닌 Generics(List<T>...)에 가깝다.

예제

단형적 함수를 다형적 함수로 바꾸는 예제를 살펴보자.

fun findFirst(ss: Array<String>, key: String): Int {
    tailrec fun loop(n: Int): Int =
        when {
            n >= ss.size -> -1
            ss[n] == key -> n
            else -> loop(n + 1)
        }
    return loop(0)
}

배열에서 특정 문자열의 index를 찾는 함수이다. 

함수를 보면 배열이 String, Int이던, 내가 정의한 클래스이던 같은 로직을 사용할 수 있을 것 처럼 보인다. 

다형적 함수로 변경해보자.

fun <A> findFirst(xs: Array<A>, p: (A) -> Boolean): Int {
    tailrec fun loop(n: Int): Int =
        when {
            n >= xs.size -> -1
            p(xs[n]) -> n
            else -> loop(n + 1)
        }
    return loop(0)
}

이렇게 타입 파라미터를 사용하여 정의할 수 있다.

findFirst(arrayOf(1,2,3,4,5,6)) {
    it == 5
}
findFirst(arrayOf("A", "B", "C", "D", "E")) {
    it == "A"
}

이런 식으로 사용하면 된다.

연습문제 2.2

isSorted함수를 구현하라. 확장 프로퍼티인 head와 tail을 사용하라.

fun main() {
    val list = listOf(1, 2, 3, 4, 5)
    val list2 = listOf(1, 2, 3, 5, 4)
    val isSorted = isSorted(list2) { a1, a2 ->
        a1 <= a2
    }
    println(isSorted)

}

val <T> List<T>.tail: List<T>
    get() = drop(1)

val <T> List<T>.head: T
    get() = first()

fun <A> isSorted(aa: List<A>, order: (A, A) -> Boolean): Boolean {
    val isOrdered = order(aa.head, aa.tail.head)
    return if (isOrdered.not()) {
        false
    } else if (aa.tail.size <= 1) {
        isOrdered
    } else {
        isSorted(aa.tail, order)
    }
}

 

 

2.3 타입에 맞춰 구현하기

위에서 타입으로 A를 받아서 다형적 함수를 구현하였다. 

다형적 합수 안에서 A 타입 객체에 사용할 수 있는 연산은 A 타입에 대해 작용하는 연산 뿐이다. 
예를 들어 A 타입으로 Int를 받아 나누기 연산을 할 수 있겠지만, String 타입에 연산자 오버라이딩을 하지 않고는 나누기 연산을 할 수 없다. 

그리고 주어진 타입에 따라 구현할 수 있는 코드가 하나로 정해지는 경우도 있다.

partial application 을 수행하는 고차함수를 보자. 

어떤 값과 함수를 인자로 받고, 인자를 하나만 적용해서 결과를 내놓는 함수이다.

fun <A, B, C> partial1(a: A, f: (A, B) -> C): (B) -> C

partial 함수 정의는 이렇게 한다. 

타입 파라미터 A, B, C 세가지를 받고 f는 A, B 타입 인자를 받아 C타입의 결과를 리턴한다. 
그리고 partial1 함수는 (B) -> C타입을 반환한다. 

이 함수는 한 가지 구현만 갖는다. 우선 리턴 타입인 (B) -> C를 리턴하는 함수를 정의하자.

fun <A, B, C> partial1(a: A, f: (A, B) -> C): (B) -> C = { b: B ->
	TODO()
}

이렇게 반환 함수를 만들 수 있다. 

이제 (B) -> C함수에서 C를 반환해야한다. C는 f를 이용해 도출할 수 있다. 

fun <A, B, C> partial1(a: A, f: (A, B) -> C): (B) -> C = { b: B ->
	f(a, b)
}

인자 두개를 받아 부분적으로 적용해 돌려주는 고차 함수를 정의했다. 

의문점

{ b -> C() }를 할 수는 없을까?

Generics 타입의 인스턴스 생성은 할 수 없다. 

이렇게 간단한 한 줄짜리 함수를 작성하였다. 이런 코드가 실제 세계의 큰 코드에서도 적용할 수 있을까?

답은 가능하다. 다형성 고차함수는 특정 도메인을 다루지 않고 다양한 문맥에서 발생할 수 있는 전형적인 패턴만 추상화한다.  

예제 2.3

currying 함수를 작성하라

fun <A, B, C> curry(f: (A, B) -> C): (A) -> (B) -> C = { a ->
    { b -> f(a, b) }
}

예제 2.4

curry 변환의 역변환인 uncurry함수를 작성하라

fun <A, B, C> unCurry(f: (A) -> (B) -> C): (A, B) -> C = { a, b ->
    f(a)(b)
}

예제 2.5

두 함수를 합성하는 고차함수를 작성하라.

fun <A, B, C> compose(f: (B) -> C, g: (A) -> B): (A) -> C = { a ->
    f(g(a))
}

파일

소프트웨어 상에서 동작하는 파일은 모두 그렇듯 파일 역시 0, 1로 기록된다. 

png 파일
pdf, apk 파일

UltraEdit을 통해 png, pdf, apk 파일을 열어봤다. 
2진수 비트보다 보기쉽게 16진수로 변환되어 보인다. 

모든 파일은 고유한 포맷을 가지고 있으며 파일 시그니처를 통해 포맷을 기록한다. 
파일 시그니처는 파일의 헤더에 기록된다. (png와 jpg는 footer 시그니처도 가지고 있다)

이렇게 PDF는 25 50 44 46, PNG는 89 50 4E 47 같이 파일 포맷에 맞는 고유한 시그니처가 존재한다. 

시그니처 외에도 파일 헤더에는 파일의 크기, 만든 시간, 접근 권한 등의 정보가 담겨 있다. 

파일 시스템

파일 시스템은 이런 파일과 디렉토리의 CRUD를 관리한다. 

그리고 파일에 대한 접근 방법을 제공하고, 접근 권한을 관리한다. 

또 파일 내용이 손상되지 않도록 무결성을 보장하고, 백업과 복구 작업을 한다.

파일을 보호하기 위한 암호화도 담당한다. 

 

파일 시스템은 어떻게 파일을 저장할까?

  • Continguous Allocation

처음에는 파일을 연속적인 공간에 저장했다. 연속적인 저장장치의 주소를 읽기 때문에 속도는 빠르지만, 파일은 수정을 거듭하며 사이즈가 달라지기 때문에 연속적으로 저장하기 어렵고 단편화 문제도 발생한다.

  • Linked Allocation

파일을 블록단위로 저장하고 각 블록에 다음 블록에 대한 주소를 갖고 있게해 LinkedList 형태로 파일을 읽을 수 있는 방식이다.

  • Indexed Allocation

인덱스를 기록하는 블럭을 하나 두고, 이 index 블록안에 포인터를 보고 파일에 접근하는 방식이다. 

이렇게 저장된 파일에 접근할 때는 파일 테이블을 통해서 접근한다. 

파일 테이블의 블록 번호를 보고 파일에 접근할 수 있다.

그리고 파일 테이블은 디스크 파티션 마다 존재한다 .

 

OS가 파일에 접근하는 법 - File Descriptor

유닉스 계열의 운영체제에서 모든 것은 파일이다. 파일, 디렉토리, 소켓, 등등 모두 파일로 관리된다. 

운영체제에서 파일에 접근할 때 File Descriptor를 사용한다. 

fd = open("test.txt", O_RDONLY);

C언어에서 open으로 파일을 열면 File Descriptor를 반환한다. File Descriptor는 0이 아닌 양의 정수이다. 

파일 디스크립터 값은 파일 디스크립터 테이블의 인덱스값이다. 

파일을 열 때마다 파일 디스크립터 테이블에 파일 테이블에 대한 참조값을 저장하고 인덱스를 반환해준다. 

우리는 fd를 통해 file table의 위치를 찾고 file table의 값을 통해 파일의 위치를 찾아 읽을 수 있다.  

리눅스 - 파일 디스크립터 :: Developer Ahn (tistory.com)

 

 

[운영체제] 파일과 파일 시스템 (velog.io)

[운영체제] File System Implementations (tistory.com)

리눅스 - 파일 디스크립터 :: Developer Ahn (tistory.com)

 

리눅스 - 파일 디스크립터

File Descriptor (파일 디스크립터) [출처: http://dev.plusblog.co.kr/22] 1. 파일 디스크립터 - 시스템으로부터 할당 받은 파일을 대표하는 0이 아닌 정수 값- 프로세스에서 열린 파일의 목록을 관리하는 테이

dev-ahn.tistory.com

 

[운영체제] File System Implementations

이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;) 테이프: 순차 접근만 가능. 건너뛰기 불가능 하드 디스크, 플래시 메모리: 건너뛰기 가능. 직접 접근 가능한 매체

movahws.tistory.com

 

[운영체제] 파일과 파일 시스템

쉽게 배우는 운영체제 2판 책을 통해 내용을 정리한 글입니다!파일 시스템은 파일과 파일의 집합체인 디렉터리(directory)를 관리한다.유닉스 -> 디렉터리윈도우 -> 폴더파일 시스템은 파일 및 디렉

velog.io

 

'CS > 운영체제' 카테고리의 다른 글

3장 프로세스(PCB, Context Switch, Scheduling, IPC)  (1) 2022.05.15

+ Recent posts