[함수형 프로그래밍] Chapter5.엄격성과 나태성

순수 함수적 자료구조

주어진 입력 목록 전체를 훑고 새로운 목록을 연산의 결과로 돌려준다.
여러 일괄 연산인 경우, 한번만 훑고 작업 동시 수행이 이상적

List(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3)

List의 프로그램 추적

List(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3)
List(11,12,13,14).filter(_ % 2 == 0).map(_ * 3)
List(12, 14).map(_ * 3)
List(36, 42)

획일적인 루프 작성보다 -> map과 filter 같은 고차 함수를 이용하는게 이상적 일련의 변화들을 하나의 패스로 융합( fusion)해서 임시 자료 생성을 피하는 것이 좋다.

비엄격성(non-strictness, 나태성[laziness])

자동적인 루프 융합이 가능

https://scastie.scala-lang.org/taA8fRlZT6O5v4pVYOq1vA

엄격한 함수와 엄격하지 않은 함수

비엄격한 함수

하나 이상의 인수들을 평가하지 않을 수도 있다.

엄격한 함수

자신의 인수들을 항상 평가한다.

def square(x: Double): Double = x * x

square(41.0 + 1.0)            // success
square(sys.error("failure"))  // failure

부울 함수 &&와 ||의 단축 평가는 엄격하지 않다.

false && { println("!!"); true }
// 아무것도 출력되지 않음
// 조건이 false가 되면 && 뒤의 조건이 평가되지 않는다.

true || { println("!!"); true }
// 역시 아무것도 출력되지 않음
// 앞의 조건이 true이면 || 뒤의 조건이 평가되지 않는다.

var result = if (input.isEmpty) sys.error("empty input") else input

비엄격 if함수

비엄격성을 명시적으로 지정
```
def if2[A](cond: Boolean, onTrue: () => A, onFalse: () => A): A = 
if (cond) onTrue() else onFalse()
```
- onTrue나 onFalse와 같이 조건에 따라 평가가 될 수도 있고 안될 수도 있다.
- if2와 같은 함수를 비엄격한 함수 라고함

if2(a < 22), () => println("a"), () => print("b"))

평가되지 않은채 전달되는 인수 -> 해당 형식 바로 앞에 () => 를 표기
() => A는 인수를 받지 않고 A를 돌려주는 함수 (Function[A] 형식의 구문적 별칭)
- 표현식의 평가되지 않은 형태를 성크(thunk) 라고 부름

() => A -> ()를 생략해서 표현할 수 있다.

def if2[A](cond: Boolean, onTrue: => A, onFalse: => A): A = 
    if (cond) onTrue else onFalse

보통의 함수 호출 구문을 이용하면 성크안의 표현식을 알아서 감싸준다.

if2(false, sys.error("fail"), 3)

def maybeTwice(b: Boolean, i: => Int) = if(b) i+i else 0

val x = maybeTwice(true, { println("hi"); 1+41 })

hi
hi
84

def maybeTwice2(b:Boolean, i: => Int) = {
  lazy val j = i
  if (b) j+j else 0
}

val 선언에 lazy 키워드를 추가 -> val 선언 우변의 평가를 우변이 처음 참조될 때까지 지연
평가 결과를 캐시에 담아두고, 이후 참조에서는 평가를 되풀이 하지 않음
비엄격 함수의 인수는 이름으로(by name) 전달

val y = maybeTwice2(true, { println("hi"); 1+41 })

hi
84

https://scastie.scala-lang.org/2poZA2paRsGU9ydr3ViNRg

확장 예제: 게으른 목록

Stream (Lazy List)

나태성 이용하여 개선(하나의 패스로 융합)하는 목록 자료형

Stream in package scala is deprecated (since 2.13.0): Use LazyList instead of Stream https://scastie.scala-lang.org/qcQnAyrFTAmVBAxWbnIOkA

Stream의 간단한 정의

sealed trait Stream[+A]
case object Empty extends Stream[Nothing]
case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]

object Stream {
    def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = {
        lazy val head = hd
        lazy val tail = tl
        Cons(() => head, () => tail)
    }
    def empty[A]: Stream[A] = Empty

    def apply[A](as: A*): Stream[A] = 
        if (as.isEmpty) empty
        else cons(as.head, apply(as.tail: _*))
}

List 목록과 거의 비슷 (List 함수적 자료구조 참고)
Cons 자료 생성자가 명시적인 성크(() => A와 () => Stream[A])를 받는다.
Stream을 조사하거나 순회 -> 성크들의 평가를 강제해야 함

def headOption: Option[A] = this match {
        case Empty => None
        case Cons(h, t) => Some(h())
}

// expensive(x)가 두 번 계산
val x = Cons(() => expensive(x), tl)
val h1 = x.headOption
val h2 = x.headOption

똑똑한(smart) 생성자

패턴 부합에 쓰이는 '실제' 생성자와는 조금 다른 서명을 제공하는 자료 형식을 생성하는 함수
생성자의 이름으로 해당 자료 생성자의 첫글자를 소문자로 바꾼것을 사용하는 것이 관례

메모화(memoization)

성크는 한번만 평가되고 이후 강제에서는 캐싱된 lazy val이 반환

def cons[A](hd: => A, tl: Stream[A]): Stream[A] = {
    lazy val head = hd
    lazy val tail = tl
    Cons(() => head, () => tail)
}

    def apply[A](as: A*): Stream[A] = 
        if (as.isEmpty) empty
        else cons(as.head, apply(as.tail: _*))

cons 인수들을 성크로 감쌈 -> Steam을 강제할 때까지는 as.head, apply(as.tail: _*) 표현식은 평가되지 않는다.

https://scastie.scala-lang.org/iX6c2lpPQxGsQYAbn9htpw

스트림 조사를 위한 보조 함수들

Stream을 List로 변환

def toList: List[A] =  {
      def go(s: Stream[A], acc:List[A]): List[A] = s match {
        case Cons(h, t) => go(t(), h() :: acc)
        case _ => acc
      }
      go(this, List()).reverse
    }

Stream의 처음 n개의 요소를 돌려주는 함수 take(n)

def take(n: Int): Stream[A] = this match {
      case Cons(h, t) if n > 1 => cons(h(), t().take(n - 1))
      case Cons(h, _) if n == 1 => cons(h(), empty)
      case _ => empty
    }

Stream의 처음 n개의 요소를 건너뛴 스트림을 돌려주는 drop(n)

def drop(n: Int): Stream[A] = this match {
      case Empty => empty
      case Cons(h, t) if n > 1 => t().drop(n-1)
      case Cons(h, t) if n == 1 => t()
    }

Stream에서 주어진 술어를 만족하는 선행 요소들을 모두 돌려주는 함수 takeWhile

def takeWhile(p: A => Boolean): Stream[A] = this match {
      case Empty => empty
      case Cons(h, t) => if (p(h())) cons(h(), t().takeWhile(p)) else t().takeWhile(p)
    }

https://scalafiddle.io/sf/lNfmSu5/0

프로그램 서술과 평가의 분리

관심사의 분리(separation of concerns)
- 나태성을 통해 표현식의 서술을 표현시의 평가와 분리
- Stream을 이용하면 요쇼들의 순차열을 생성하는 계산을 구축하되 계산 단계들의 실행은 실제 요소가 필요할 때까지 미룰 수 있다.

def exists(p: A => Boolean): Boolean = this match {
  case Cons(h, t) => p(h()) || t().exists(p)
  case _ => false
}

재귀를 foldRight의 형태로 구현

def foldRight[B](z: => B)(f: (A, => B) => B) : B = 
  this match {
    case Cons(h, t) => f(h(), t().foldRight(z)(f))
    case _ => z
  }

def exists(p: A => Boolean): Boolean =
  foldRight(false)((a,b)=> p(a) || b)

점진적(incremental)

결과 Stream의 요소들을 다른 어떤 계산이 참조되는 시점이 되어서야 계산이 실제로 진행
중간 결과를 완전히 인스턴스화 하지 않고도 함수들을 연이어 호출할 수 있음

Stream의 모든 요소가 주어진 술어를 만족하는지 점검하는 forAll 함수

만족하지 않는 값을 만나면 즉시 순회를 마쳐야 한다.

def forAll(p: A => Boolean): Boolean = this match {
  case Cons(h, t) => if(p(h())) t().forAll(p) else false
  case _ => true
}

def forAll(f: A => Boolean): Boolean =
    foldRight(true)((a,b) => f(a) && b)

Stream에 대한 프로그램 추적

Stream(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).toList

// Stream(1,2,3,4)는 Stream.apply 메소드에 의해 cons 메소드를 통해 다음과 같이 변환된다.
cons(1, Stream(2,3,4)).map(_ + 10).filter(_ % 2 == 0).toList
(1 :: Stream(2,3,4)).map(_ + 10).filter(_ % 2 == 0).toList
(11 :: Stream(2,3,4).map(_ + 10)).filter(_ % 2 == 0).toList
cons(11, Stream(2,3,4).map(_ + 10)).filter(_ % 2 == 0).toList

//그 다음 cons의 head와 tail에 filter를 적용하게 된다.
cons(11, Stream(2,3,4).map(_ + 10)).filter(_ % 2 == 0).toList
(11 :: Stream(2,3,4).map(_ + 10)).filter(_ % 2 == 0)).toList
Stream(2,3,4).map(_ + 10).filter(_ % 2 == 0).toList

//마찬가지로 Stream(2,3,4)에 대해서도 cons와 map과 filter를 차례로 수행한다.
cons(12, Stream(3,4).map(_ + 10)).filter(_ % 2 == 0).toList()
(12 :: Stream(3,4).map(_ + 10)).filter(_ % 2 == 0).toList()
12 :: Stream(3,4).map(_ + 10).filter(_ % 2 == 0).toList()
12 :: cons(3, Stream(4)).map(_ + 10).filter(_ % 2 == 0).toList()
12 :: cons(13, Stream(4).map(_ + 10)).filter(_ % 2 == 0).toList()
12 :: Stream(4).map(_ + 10).filter(_ % 2 == 0).toList()
12 :: Stream(14).filter(_ % 2 == 0).toList()
12 :: 14 :: Stream().map(_ + 10).filter(_ % 2 == 0).toList()
12 :: 14 :: List()

https://scastie.scala-lang.org/qcQnAyrFTAmVBAxWbnIOkA

무한 스트림과 공재귀

작성한 함수들은 점진적 무한 스트림(infinite stream)에도 사용할 수 있습니다.

1이 무한히 나열되는 stream


val ones: Stream[Int] = Stream.cons(1, ones)

ones.take(5).toList ones.exists(_ % 2 != 0)

ones는 무한,
작성한 함수들은 요구된 출력을 산출하는데 필요한 만큼만 스트림을 조사

```scala
ones.map(_ + 1).exists(_ % 2 == 0)
ones.taskWhile(_ == 1)
ones.forAll(_ != 1)

세 경우 모두 결과가 즉시 나온다. 단 결코 종료되지 않거나 스택에 안전하지 않은 표현식이 만들어지기 쉬우니 조심해야 한다.

ones.forAll(_ == 1)

주어진 값의 무한 Stream을 돌려주는 함수 constant

def constant[A](a: A): Stream[A] = {
      cons(a, constant(a))
    }

n에서 시작해서 n +1, n+2 등으로 이어지는 무한 정수 스트림

def from(n: Int): Stream[Int] = {
    cons(n, from(n+1))
  }

주어진 값의 무한 Stream을 돌려주는 함수 constant

def constant[A](a: A): Stream[A] = {
      cons(a, constant(a))
    }

n에서 시작해서 n +1, n+2 등으로 이어지는 무한 정수 스트림

def from(n: Int): Stream[Int] = {
    cons(n, from(n+1))
  }

좀 더 일반화된 스트림 구축 함수 unfold

이 함수는 초기상태 하나와 다음 상태 및 다음 값(생성된 스트림 안의)을 산출하는 함수 하나를 받아야 한다.
```
def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] =
f(z) match {
  case Some((h,s)) => cons(h, unfold(s)(f))
  case None => empty
}
```
Option은 Steam이 종료되는 시점(있는경우)을 지정
값이 있거나 또는 없거나 한 상태를 나타낼 수 있는 타입이다.
값이 담겨져 있는 Option 의 하위 타입은 Some[T] 이며, 값이 없으면 None 이다.

unFold 함수는 일반적인 Stream 구축 함수, 소위 공재귀(corecursive)함수의 예 재귀 함수는 자료를 소비하지만 공재귀 함수는 자료를 생산

재귀는 점점 더 작은 입력으로 재귀하다가 종료
공재귀 함수는 생산성(procdutivity)을 유지하는 한 종료될 필요가 없다. 함수 f를 한 번 더 실행해서 Stream의 다음 요소를 생성하기만 하면 됨

https://scalafiddle.io/sf/7bjR93Y/9

NMP-Study / FunctionalProgrammingInScala