Functional Programming Principles in Scala - Lists

5.1 More Functions on Lists

앞서 보았던 것과 추가로 List의 Method 몇가지를 더 보자.

Sublists and element access

  • xs.length - The number of elements of xs.
  • xs.last - The list's last element, exception if xs is empty.
  • xs.init - A List consisting of all elements of xs except the last one, exception if xs is empty.
  • xs take n - A List consisting of the first n elements of xs, or xs itselft if it is shorter than n.
  • xs drop n - The rest of the collection after taking n elements.
  • xs(n) - (or, written out, xs apply n). The element of xs at index n.

Creating new lists

  • xs ++ ys - The list consisting of all elements of xs followed by all elements of ys.
  • xs.reverse - The list containing the elements of xs in reversed order.
  • xs updated (n, x) - The list containing the same elements as xs, except at index n where it contains x.

Finding elements

  • xs indexOf x - The index of the first element in xs equal to x, or -1 if x does not appear in xs.
  • xs contains x - same as xs indexOf x >= 0

Implementation of last

head의 complexity는 constant time이다. 그럼 last의 경우는 어떨까? 일단 구현을 보자.

def last[T](xs: List[T]): T = xs match {  
    case List() => throw new Error("last of empty list")
    case List(x) => x
    case y :: ys => last(ys)
}

따라서 xs의 길이만큼 시간이 걸린다는 것을 알 수 있다.

그럼 이번에는 init을 구현해보자.

def init[T](xs: List[T]): List[T] = xs match {  
    case List() => throw new Error("init of empty list")
    case List(x) => List()
    case y :: ys => y :: init(ys)
}

Implementation of Concatenation

이번에는 concatenation을 어떻게 구현할지 보자.

기본적으로 두개의 list를 붙일 경우 아래와 같이 operation을 이용하여 구현할 수 있다.

xs ::: ys // ys.:::(xs)

동일하게 동작하는 concat 함수를 구현하면 아래와 같다.

def concat[T](xs: List[T], ys: List[T]) = xs match {  
    case List() => ys 
    case z :: zs => z :: concat(zs, ys)
}

complexity는 | xs | 이다. ( | | 는 길이를 의미한다.)

Implementation of reverse

이번에는 reverse를 구현해보자

def reverse[T](xs: List[T]): List[T] = xs match {  
    case List() => xs
    case y :: ys => reverse(ys) ++ List(y)
}

complexity는 | xs | * | xs | 로 다소 오래걸리게 된다. (xs 길이만큼 재귀가 돌고, 각 재귀마다 ++ operation에 대해 계산하게 되기 때문에) 나중에 더 나은 방법을 보도록 하자.

마지막으로 removeAt 함수를 구현해보자. removeAt은 아래와 같이 동작해야한다.

removeAt(1, List('a', 'b', 'c', 'd')) // List(a, c, d)  

def removeAt[T](n: Int, xs: List[T]): T = (xs take n) ::: (xs drop n + 1)

5.2 Pairs and Tuples

Sorting Lists Faster

이전에 보았던 insertion sort보다 향상된 merge sort를 보도록하자. merge sort에 대한 아이디어는 만약 list가 0 또는 1개의 element를 가질때 이미 정렬되어 있다는 것에서 기반한다. 그렇지 않은 경우

  • list를 두개의 sub-list로 나누는데 원래 list의 element를 반씩 가지고 있게 한다.
  • 두개의 sub-list를 정렬한다.
  • 그 두개의 sub-list를 하나의 list로 합친다(Merge).

이것을 Scala로 구현하면 아래와 같다.

def msort(xs: List[Int]): List[Int] = {  
    val n = xs.length / 2
    if (n == 0) xs
    else {
        def merge(xs: List[Int], ys: List[Int]) = 
        val (fst, snd) = xs splitAt n
        merge(msort(fst), msort(snd))
    }
}

여기서 merge를 구현하면 아래와 같다.

def meger(xs: List[Int], ys: List[Int]) =  
    xs match {
        case Nil => ys
        case x :: xs1 => ys match {
                case Nil => xs
                case y :: ys1 =>
                    if (x < y) x :: merge(xs1, ys)
                    else y :: merge(xs, ys1)
        }
    }
}

The SplitAt Function

여기서 splitAt 함수를 보면 주어진 n을 기점으로 두개의 sublist를 돌려준다. 여기서 list들은 한 pair에 담아 돌려받게 된다.

pair는 아래와 같은 예처럼 사용이 가능하다.

val pair = ("answer", 42)  > pair : (String, Int) = (answer, 42)  
val (label, value) = pair  > label : String = answer  
                           | value : Int = 42

이 동작은 두개 이상의 element에 대한 tuple과 동일하다.

이전에 보았던 Function n과 동일하게 tuple도 각각에 대한 정의가 되어있다.

case class Tuple2[T1, T2](_1: +T1, _2: +T2) {  
    override def toString = "(" + _1 + "," + _2 + ")"
}

따라서, 앞서 봤던 pattern matching 형태가 더 선호되지만 아래와 같이 사용할 수도 있다.

val label = pair._1  
val value = pair._2

이러한 pair을 이용하여 앞서 구현했던 merge 함수를 아래와 같이 수정할 수 있다.

def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, ys) match {  
    case (Nil, ys) => ys
    case (xs, Nil) => xs
    case (x :: xs1, y :: ys1) => 
        if (x < y) x :: match(xs1, ys)
        else y :: match(xs, ys1)
}

5.3 Implicit Parameters

여기서 Merge sort를 일반화해보자. 지금 현재는 Int에 대해서만 동작한다. 그럼 Double 및 Boolean 등 여러가지 자료구조를 포함하여 아래와 같이 구현이 가능할까?

def msort[T](xs: List[T]): List[T] = ...

지금 현재 구현된 내용으로는 불가하다. 이유는 비교 연산자인 <가 모든 type에 대해 동작 가능한 것이 아니기 때문이다. 그럼 어떻게 해결할까? 이를 위해 비교 연산 함수를 parameter로 받으면 된다.

Parameterization of Sort

따라서 추가적인 parameter를 받도록 설계해보자.

def msort[T](xs: List[T])(lt: (T, T) => Boolean) = {  
    ...
    merge(msort(fst)(lt), msort(snd)(lt))
}

def merge(xs: List[T], ys: List[T]) = (xs, ys) match {  
    ...
    case (x :: xs1, y :: ys1) =>
        if (lt(x, y)) ...
        else ...
}

따라서, String에 대해서 처리할 경우 아래와 같이 적용할 수 있다.

val fruits = List("apple", "pineapple", "orange", "banana")

msort(fruits)((x: String, y: String) => x.compareTo(y) < 0)

Parametrization with Ordered

위와 같이 비교연산자를 구현하여 추가할 수도 있지만, scala에서 standard library로 order를 제공하는 api를 사용할 수도 있다.

scala.math.Ordering[T]

따라서 이걸 이용하여 구현하면 아래와 같이 할 수 있는데,

def msort[T](xs: List[T])(ord: Ordering) =

    def meger(xs: List[T], ys: List[T]) =
        ... if (ord.lt(x, y)) ...

... merge(msort(fst)(ord), msort(snd)(ord)) ...

이렇듯 다른 함수를 추가 구현하여 넘겨주지 않아도 된다. 따라서 msort를 호출 할때는 아래와 같이 호출하면 된다.

import math.Ordering

...
msort(nums)(Ordering.Int)  
msort(fruits)(Ordering.String)

Implicit Parameter

하지만, 일일이 ord 값을 넘겨주는 일도 귀찮을 수 있다. 이럴 경우 Implicit Parameter를 통해 해결할 수 있다.

def msort[T](xs: List[T])(implicit ord: Ordering) =

    def merge(xs: List[T], ys: List[T]) =
        ... if (ord.lt(x, y)) ...

... merge(msort(fst), msort(snd)) ...

또한, complier에 의해 자동으로 type이 넘어가게 되어 호출할 때도 아래처럼 할 수 있다.

msort(nums)  
msort(fruits)

Rules for Implicit Parameters

만약 함수가 type T 의 implicit parameter를 받는 다면 아래와 같은 rule에 따라 implicit definition을 찾게 된다.

  • implicit로 마크되어 있는 경우
  • T와 type이 호환(compatible)되는 경우
  • 함수하는 시점이 보여야하거나 T와 관련된 companion object안에 정의가 되어 있는 경우

5.4 Higher-Order List Functions

이전까지 본 함수들을 보면 list에 대해 동일한 구조를 가진 것을 볼 수 있다. 예를 들어,

  • 각각 element에 대해 동일한 방법을 적용하여 변경하거나,
  • 특정한 기준을 만족하는 list의 element를 돌려주거나,
  • operator를 이용하여 list를 합치거나,

이러한 pattern을 구현한 일반 함수를 higher-order function을 사용하여 해결할 수 있 다.

Applying a Function to Elements of a List

흔한 operation은 list의 각각 element를 변경하여 그 결과를 돌려주는 것이다. 예를 들어, factor를 모든 element에 적용하는 함수를 구현하고자 할때,

def scaleList(xs: List[Double], factor: Double): List[Double] = xs match {  
    case Nil     => xs
    case y :: ys => y * factor :: scaleList(ys, factor)
}

위와 같이 구현할 수 있다.

Map

List class에 map이라는 method가 있는데 아래와 같이 정의를 보자.

abstract class List[T] {  
    def map[U](f: T => U): List[U] = this match {
        case Nil     => this
        case x :: xs => f(x) :: xs.map(f)
    }

(실제로는 tail-recursive로 구현되기 때문에 훨씬 복잡하다.)

이러한 map을 scaleList에 적용하면 아래와 같이 된다.

def scaleList(xs: List[Double], factor: Double) =  
    xs map (x => x * factor)

그럼 이번에는 다른 예로 squareList 함수를 구현해보자. 모든 element에 대해 제곱을 적용하면된다. 위와 같이 두가지 방법을 모두 사용해보자.

def squareList(xs: List[Int]): List[Int] =  
  xs match {
    case Nil     => xs // Nil
    case y :: ys => y * y :: squareList(ys)
  }

def squareList(xs: List[Int]): List[Int] =  
  xs map (x => x * x)

Filter

이번에는 비슷하지만 다른 operation을 보자. 주어진 조건(condition)을 통과하는 element만 돌려주는 함수이다.

def posElems(xs: List[Int]): List[Int] = xs match {  
    case Nil     => xs
    case y :: ys => if (y > 0) y :: posElems(ys) else posElems(ys)

구현을 보면 (y > 0)(condition)을 통과하는 element에 대해서만 추가(::)되는 것을 볼 수 있다.

이와 동일하게 행동하는 List의 method로 filter가 있다.

abstract class List[T] {  
    ...
    def filter(p: T => Boolean): List[T] = this match {
        case Nil     => this
        case x :: xs => if (p(x)) x :: xs.filter(p) else xs.filter(p)
    }
}

이를 이용하면 위의 구현이 아래와 같이 요약된다.

def posElems(xs: List[Int]): List[Int] =  
    xs filter (x => x > 0)

추가적으로 아래와 같은 함수들도 있다.

nums filter (x => x > 0)     // List[Int] = List(2, 5, 7, 1)  
nums filterNot (x => x > 0)  // List[Int] = List(-4)  
nums partition (x => x > 0)  // (List[Int], List[Int]) = (List(2, 5, 7, 1), List(-4))

nums takeWhile (x => x > 0)  // List[Int] = List(2)  
nums dropWhile (x => x > 0)  // List[Int] = List(-4, 5, 7, 1)  
nums span (x => x > 0)       // (List[Int], List[Int]) = (List(2), List(-4, 5, 7, 1))

5.5 Reduction of Lists

주어진 operation을 이용하여 list의 모든 element를 합치는(combine)하는 경우를 보자. 아래의 예를 보면,

sum(List(x1, ..., xn))         = 0 + x1 + ... + xn  
product(List(x1, ..., xn))     = 1 * x1 * ... * xn

이러한 경우 아래와 같이 recursive schema를 이용하여 구현할 수 있다.

def sum(xs: List[Int]): Int = xs match {  
    case Nil     => 0
    case y :: ys => y + sum(ys)
}

ReduceLeft

이러한 pattern은 generic method은 reduceLeft를 이용하여 추상화할 수 있다.

reduceLeft는 list 안에 근접한 element 간 operator 적용되도록 한다. 

List(x1, ..., xn) reduceLeft op = (...(x1 op x2) op ...) op xn

따라서 아래와 같이 정리가 가능하다.

def sum(xs: List[Int])     = (0 :: xs) reduceLeft ((x, y) => x + y)  
def product(xs: List[Int]) = (1 :: xs) reduceLeft ((x, y) => x * y)

A Shorter Way to Write Functions

((x, y) => x * y))대신에 아래와 같이 더 짧게 표현할 수 있다.

(_ * _)

여기서 _는 새로운 parameter를 의미하고, 왼쪽에서 오른쪽으로 인식한다.

따라서, 이를 적용하여 아래와 같이 간단하게 표현할 수 있다.

def sum(xs: List[Int])     = (0 :: xs) reduceLeft (_ + _)  
def product(xs: List[Int]) = (1 :: xs) reduceLeft (_ * _)

FoldLeft

reduceLeft 보다 조금 더 일반화된 함수로 foldLeft가 있다.

foldLeft는 reduceLeft와 동작방식이 유사하나 accumulator parameter를 추가로 받는 다는 점이 다르다. 따라서 아래와 같이 동작하게 되는데,

(List(x1, ..., xn) foldLeft z)(op) = (...(z op x1) op ...) op xn

아래와 같이 이를 이용하여 정의를 변경할 수 있다.

def sum(xs: List[Int])     = (xs foldLeft 0)(_ + _)  
def product(xs: List[Int]) = (xs foldLeft 1)(_ * _)

이러한 두 method를 List class에 구현해보자.

abstract class List[T] {  
    def reduceLeft(op: (T, T) => T): T = this match {
        case Nil     => throw new Error("Nil.reduceLeft")
        case x :: xs => (xs foldLeft x)(op)
    }
    def foldLeft[U](z: U)(op: (U, T) => U): U = this match {
        case Nil     => z
        case x :: xs => (xs foldleft op(z, x))(op)
    }
}

FoldRight and ReduceRight

foldLeft와 reduceLeft를 트리에 풀면 왼쪽으로 기울어져있는 것을 볼 수 있다. 이거와 쌍을 이루는 함수로 foldRight와 reduceRight가 있는데, 이 둘은 트리에 풀면 오른쪽으로 치우쳐있다.

List(x1, ..., x{n-1}, xn) reduceRight op = x1 op ( ... (x{n-1} op xn) ... )  
(List(x1, ..., xn) foldRight acc)(op)    = x1 op ( ... (xn op acc) ... )

이를 구현하면 아래와 같다.

def reduceRight(op: (T, T) => T): T = this match {  
    case Nil => throw new Error("Nil.reduceRight")
    case x :: Nil => x
    case x :: xs => op(x, xs.reduceRight(op))
}
def foldRight[U](z: U)(op: (T, U) => U): U = this match {  
    case Nil => 2
    case x :: xs => op(x, (xs foldRight z)(op))
}

Difference between FoldLeft and FoldRight

효율성에서 차이가 있을 수 있어도 결합법칙(associative)나 교환법칙(commutative)이 적용되는 operator에 대해 foldLeft나 foldRight는 동일한 결과를 돌려준다.

하지만, 때에 따라 둘 중 하나의 경우만 적절할 수 있다. 아래 예를 보자.

def concat[T](xs: List[T], ys: List[T]): List[T] =  
    (xs foldRight ys) (_ :: _)

물론 이걸 이해하기 위해서는 그림으로 보는 것이 가장 도움이 되지만, 여건에 따라 상상하기로 하자. ys가 accumulator로 가장 오른쪽 하단에 붙고 나머지가 차례로 붙는다. 따라서 최종적으로 xs의 맨 마지막인 xs{n}과 ys가 결합하여 결과적으로 xs, ys순으로 List가 구성된다. 이 경우 만약 foldRight대신 foldLeft를 쓰면 어떻게 될까? 답은 type이 제대로 동작하지 않는다. 결과적으로 ys List에 xs element를 ::를 통해 붙여나가려하기 때문이다.

5.6 Reasoning About Concat

Laws of Concat

연결(concatenation) operation 인 ++를 보자. 만약 이 operation에 대해 결합법칙(associative)가 성립되고, 빈 list Nil에 대해서도 연결이 성립하는지 보고 싶다고 할 경우 어떻게 증명할 수 있을까?

(xs ++ ys) ++ za = xs ++ (ys ++ zs)
       xs ++ Nil = xs
       Nil ++ xs = xs

structural induction 을 통해 가능하다.

Reminder: Natural Induction

여기서 잠시 natural induction을 회상해보자. 모든 정수 n >= b에 대해 P(n)이 성립하는 것을 증명하기 위해,

  • P(b) (base case) 에 대해 성립할 경우,
  • 모든 정수 n >= b에 대해 아래의 induction step을 보이면 된다.

    만약 P(n)이 된다면, P(n+1) 또한 가능하다.

예를 들어, 
def factorial(n: Int): Int =  
    if (n == 0) 1            // 1st clause
    else n * factorial(n-1)  // 2nd clause
위와 같이 `factorial`이 있을 때, 
factorial(n) >= power(2, n)
을 증명하려 한다고 생각해보자. 여기서 **Base case**는 4 이다. 즉, 4에 대해서는 아래와 같이 명제가 성립한다. 
factorial(4) = 24 >= 16 = power(2, 4)

Induction Step

그럼 이번엔, n >= 4에 대해서는 성립한다고 가정하고 **Induction step**으로 n+1에 대해 성립하는지 확인해보자. 
factorial(n + 1)  
>= (n + 1) * factorial(n)   // by 2nd clause in factorial
>  2 * factorial(n)         // by calculating
>= 2 * power(2, n)          // by induction hypothesis
=  power(2, n+1)            // by definition of power

Referential Transparency

위와 같은 reduction step이 가능한 것이 중요한데, pure functional program은 side effects가 없기때문에 가능하다. 이러한 원리를 참조 투명성(*referential transparency*)라고 한다.

Structural Induction

structural induction의 원리는 natural induction과 동일하다. 만약, list `xs`에 대해 `P(xs)`를 증명할 경우,
  • P(Nil)에 대해서 증명을 한다. (base case)
  • list xs와 x element에 대해 induction step을 증명한다. 만약 P(xs)가 가능하면, P(x :: xs)에 대해서도 가능하다.

예를 들어보면, 아래와 같이 결합법칙에 대해 증명해보자.

(xs ++ ys) ++ zs = xs ++ (ys ++ zs)

xs에 대해서 structural induction을 사용해보자. 이전에 봤던 concat을 보면,

def concat[T](xs: List[T], ys: List[T]) = xs match {  
    case List() => ys
    case x :: xs1 => x :: concat(xs1, ys)
}

또한 아래의 두가지는 ++ 에 대한 부분이다.

       Nil ++ ys = ys               // 1st clause
(x :: xs1) ++ ys = x :: (xs1 ++ ys) // 2nd clause

Base case

여기서 base case로 Nil을 보자.

// left-hand side
(Nil ++ ys) ++ zs
= ys ++ zs         // by 1st clause of ++

// right-hand side
Nil ++ (ys ++ zs)  
= ys ++ zs

위와 같이 성립하는 것을 볼 수 있다.

Induction Step: LHS

그럼 induction step중 left-hand side부터 보자.

((x :: xs) ++ ys) ++ zs
= (x :: (xs ++ ys)) ++ zs     // by 2nd clause of ++
= x :: ((xs ++ ys) ++ zs)     // by 2nd clause of ++
= x :: (xs ++ (ys ++ zs))     // by induction hypothesis

Induction Step: RHS

다음으로 right-hand side를 보자.

(x :: xs) ++ (ys ++ zs)
= x :: (xs ++ (ys ++ zs))     // by 2nd clause of ++

따라서 위 두가지 경우를 조합하여 P(x :: xs)의 경우에 증명이 가능하다고 판단할 수 있다.

Reference

comments powered by Disqus