scala with cats 책 읽으면서 필기 Chapter 7 (Foldable and Traverse)

2020/02/21 - [Programmer Jinyo/Scala & AKKA] - scala with cats 책 읽으면서 필기 Chapter 6 (Semigroupal and Applicative)

위 글에서 이어지는 글입니다.

이 글 시리즈는 scala with cats 원문을 보고 쓴 글입니다.

 

*필기 위주로 합니다 ㅜ_ㅜ.. 공부하는데에 너무 시간이 오래걸려서..

 

 

---

Foldable and Traverse

이 챕터에서는 컬랙션에 대해서 순회를 캡쳐하는(?) 두 타입 클래스에 대해서 볼 것이다.

 

- Foldable 은 foldLeft와 foldRight과 비슷한 연산을 추상화한다.

- Traverse는 고-레벨의 추상화인데 folding보다 적게 고통받으며 순회하기 위해 Applicatives를 사용한다.

 

Foldable부터 살펴본다. 그리고 불편한걸 Traverse로 해결.

 

7.1 Foldable

Foldable 타입클래스는 우리가 Lists,Vectors,Streams와 같은 친구들을 시퀀스 하기 위해 썼던 foldLeft와 foldRight 메소드를 캡쳐(?)한다. Foldable을 사용하면 다양한 시퀀스 타입에 대한 일반적인 fold가 구현 가능하다. Foldable은 우리에게 Monoids와 Eval 모나드를 위한 훌륭한 유즈 케이스들을 제공한다.

 

7.1.1 Fold and Folding

빠르게 folding 복습. 우리는 초기 누적 값과 이진 함수(인자가 두개인 함수)를 시퀀스의 각 아이템들을 합치기 위해 제공해준다.

def show[A](list: List[A]): String =
  list.foldLeft("nil")((accum, item) => s"$item then $accum")

show(Nil)
// res0: String = nil

show(List(1, 2, 3))
// res1: String = 3 then 2 then 1 then nil

foldLeft 메소드는 시퀀스에 재귀적으로 동작한다. 우리의 이진 함수는 각 아이템에 대해 반복적으로 호출되고, 그 결과는 다음으로 축적된다. 마지막에 도달하면 전부 축적된 결과가 최종 결과가 된다. 

 

fold의 두가지 기본 변형이 있다.

- foldLeft는 왼쪽에서 오른쪽(시작->끝)으로 간다.

- foldRight는 오른쪽에서 왼쪽(끝->시작)으로 간다.

 

만약 foldLeft와 foldRight가 결합법칙을 만족한다면 같은 결과를 뱉는다.

List(1, 2, 3).foldLeft(0)(_ + _)
// res2: Int = 6

List(1, 2, 3).foldRight(0)(_ + _)
// res3: Int = 6

 

 

결합법칙을 만족하지 않으면 다른 결과를 뱉는다.

List(1, 2, 3).foldLeft(0)(_ - _)
// res4: Int = -6

List(1, 2, 3).foldRight(0)(_ - _)
// res5: Int = 2

7.1.2 Exercise: Reflecting on Folds

빈 리스트랑 :: 연산으로 이어붙여봐라?

별 의미없는 예제인듯? 다만 리스트는 항상 뒤에 있어야 하니까 순서가 바뀝니다 정도?

List(1, 2, 3).foldLeft(List.empty[Int])((a, i) => i :: a)
// res6: List[Int] = List(3, 2, 1)

List(1, 2, 3).foldRight(List.empty[Int])((i, a) => i :: a)
// res7: List[Int] = List(1, 2, 3)

List(1, 2, 3).foldRight(Nil)(_ :: _)
// <console>:13: error: type mismatch;
// found : List[Int]
// required: scala.collection.immutable.Nil.type
// List(1, 2, 3).foldRight(Nil)(_ :: _)
//                                 ^

7.1.3 Exercise: Scaf-fold-ing Other Methods

foldLeft와 foldRight는 굉장히 일반적인 method이다. 우리는 많은 high-level 시퀀스 연산을 구현하는데에 쓸 수 있다. List의 map, flatMap, filter, sum method를 fildRight를 통해 구현할 수 있음을 보여라.

  def func(a:Int):Int = {
    a+1
  }
  println(List(1, 2, 3).foldRight(List.empty[Int])((a, i) => func(a) :: i))
  //이게 map이지?
  
  def func(a:Int):List[Int] = {
    List(a+1)
  }
  println(List(1, 2, 3).foldRight(List.empty[Int])((a, i) => func(a) ::: i))
  //flatMap
  
  def func(a:Int):List[Int] = {
    if(a>2) Nil
    else List(a)
  }
  println(List(1, 2, 3).foldRight(List.empty[Int])((a, i) => func(a) ::: i))
  //filter
  
  println(List(1, 2, 3).foldRight(0)((a, i) => a+i))
  //sum

귀찮아서 이렇게 했더니만 모범답안은 예뻤다.

  def map[A, B](list: List[A])(func: A => B): List[B] =
    list.foldRight(List.empty[B]) { (item, accum) =>
      func(item) :: accum
    }
  map(List(1, 2, 3))(_ * 2)
  // res9: List[Int] = List(2, 4, 6)
  def flatMap[A, B](list: List[A])(func: A => List[B]): List[B] =
    list.foldRight(List.empty[B]) { (item, accum) =>
      func(item) ::: accum
    }
  flatMap(List(1, 2, 3))(a => List(a, a * 10, a * 100))
  // res10: List[Int] = List(1, 10, 100, 2, 20, 200, 3, 30, 300)
  def filter[A](list: List[A])(func: A => Boolean): List[A] =
    list.foldRight(List.empty[A]) { (item, accum) =>
      if(func(item)) item :: accum else accum
    }
  filter(List(1, 2, 3))(_ % 2 == 1)
  // res11: List[Int] = List(1, 3)

그리고 아래같은 함수 활용도 가능이다고 한다.

import scala.math.Numeric

def sumWithNumeric[A](list: List[A])(implicit numeric: Numeric[A]): A =
  list.foldRight(numeric.zero)(numeric.plus)

sumWithNumeric(List(1, 2, 3))
// res13: Int = 6

 

7.1.4 Foldable in Cats

Cats의 Foldable은 foldLeft와 foldRight를 타입클래스로 추상화 시킨다. Foldable의 인스턴스는 이 두 메소드를 정의하고 파생된 메소드를 상속한다. Cats는 List, Vector, Stram 및 Option과 같은 소수의 스칼라 데이터 유형에 대해 유용한 Foldable 인스턴스를 제공한다.

 

Foldable.apply를 통해서 인스턴스를 불러올 수 있고, 그 foldLeft 구현체를 바로 불러올 수 있다. 예시를 보자.

import cats.Foldable
import cats.instances.list._ // for Foldable

val ints = List(1, 2, 3)

Foldable[List].foldLeft(ints, 0)(_ + _)
// res1: Int = 6

 

7.1.4.1 Folding Right

Foldable은 foldRight를 foldLeft와 다르게 정의하는데, Eval monad를 통해 그렇게 한다.

def foldRight[A, B](fa: F[A], lb: Eval[B])(f: (A, Eval[B]) => Eval[B]): Eval[B]

Eval을 사용한다는 의미는, collection의 기본 정의인 foldRight가 그렇지 않을 지라도, 항상 stack safe하다는 의미이다. stream이 길면 길수록 stack은 더욱 fold해야한다. (eval에 대한 설명은 https://wingnim.tistory.com/114 챕터 4.6에 나온다)

import cats.Eval
import cats.Foldable

def bigData = (1 to 100000).toStream

bigData.foldRight(0L)(_ + _)
// java.lang.StackOverflowError ...

참고할만한 링크
Tail recursion / Trampoline / Stream에 대한 정리
https://partnerjun.tistory.com/5?category=673084
Stream은 lazy하게 evalution을 통해 무한한 값을 표현할 수 있게 해 주며 head쪽의 계산만을 필요한 만큼만 진행 해 준다.

import cats.instances.stream._ // for Foldable

val eval: Eval[Long] = Foldable[Stream].
  foldRight(bigData, Eval.now(0L)) { (num, eval) =>
    eval.map(_ + num)
  }

eval.value
// res7: Long = 5000050000

Foldable 은 stack safe operation을 할 수 있게 해 준다. 개꿀ㅋ

 

* foldLeft는 왜? 라고 물어볼 수 있는데, foldLeft는 애초에 최적화가 되어 있다. 왼쪽부터 차례로 오른쪽으로 계산해나가는게 Stream이자너~ 근데 맨 오른쪽부터 접으려고 하니까 다 계산한 후에 접어야 해서 문제가 생겼던 것.

 

Stack Safety in the Standard Library

List나 Vector같은 친구들은 그냥 stack safe를 제공해놨다.

(1 to 100000).toList.foldRight(0L)(_ + _)
// res8: Long = 5000050000

(1 to 100000).toVector.foldRight(0L)(_ + _)
// res9: Long = 5000050000

Stream에서는 안되니까 안하는것. 그치만 뭘 쓰든 Eval은 든든하다~

 

7.1.4.2 Folding with Monoids

Foldable은 foldLeft로부터 정의된 여러 유용한 메소드를 제공한다. 스텐다드 라이브러리의 복제판 친구들이 많다. find, exists, forall, toList, isEmpty, nonEmpty, 등등 말이다.

Foldable[Option].nonEmpty(Option(42))
// res10: Boolean = true

Foldable[List].find(List(1, 2, 3))(_ % 2 == 0)
// res11: Option[Int] = Some(2)

이 친숙한 메소드들에 더해서, Monoid를 통해 만든 두가지 더 메소드 제공함.

- combineAll(and its alias fold) 는 Monoid를 사용해서 시퀀스의 원소들을 다 합친다.

- foldMap은 유저가 제공한 함수를 모노이드를 통해 시퀀스를 합성해서 결과를 제공한다

 

예를 들어, combineAll 을 List[Int]를 다 더하려고 쓴다면?

import cats.instances.int._ // for Monoid

Foldable[List].combineAll(List(1, 2, 3))
// res12: Int = 6

대체제로, 우리는 foldMap을 각 Int를 String으로 하며 이어붙이는데에 쓸 수 있다.

import cats.instances.string._ // for Monoid

Foldable[List].foldMap(List(1, 2, 3))(_.toString)
// res13: String = 123

마지막으로, 우리는 Foldables를 깊은 중첩된 시퀀스의 순회를 위해 쓸 수 있다.

import cats.instances.vector._ // for Monoid

val ints = List(Vector(1, 2, 3), Vector(4, 5, 6))

(Foldable[List] compose Foldable[Vector]).combineAll(ints)
// res15: Int = 21

7.1.4.3 Syntax for Foldable

Foldable의 모든 메소드는 cats.syntax.foldable을 통해서 사용할 수 있다. 

import cats.syntax.foldable._ // for combineAll and foldMap

List(1, 2, 3).combineAll
// res16: Int = 6

List(1, 2, 3).foldMap(_.toString)
// res17: String = 123

 

Explicits over Implicits

스칼라는 메소드가 receiver 입장에서 명쾌하게 사용가능하지 않다면 Foldable의 인스턴스만 사용할 것이라는걸 기억하자. 예를 들어, 아래의 코드는 List에서 정의된 foldLeft을 사용할 것이다.

List(1, 2, 3).foldLeft(0)(_ + _)
// res18: Int = 6

아래의 제네릭 코드는 Foldable을 사용할 것이다.

import scala.language.higherKinds

def sum[F[_]: Foldable](values: F[Int]): Int =
  values.foldLeft(0)(_ + _)
  
// sum: [F[_]](values: F[Int])(implicit evidence$1: cats.Foldable[F])Int

컴파일러가 알아서 잘 써주니까 일반적인 상황에서는 사실 걱정 안해도 된다.

 

7.2 Traverse

foldLeft와 foldRight는 아주 유연한 순회 메소드이지만 우리로 하여금 누산기(누적 될 값)와 합성함수를 정의하는에에 애를 먹인다. Traverse 타입 클래스는 Applicatives를 조율하는 더 높은 레벨의 도구이다.

 

7.2.1 Traversing with Futures

Scala standard library에 있는 Future.traverse와 Future.sequence메소드를 사용해서 Traverse를 보여줄 수 있다. 이 메소드들은 traverse 패턴이 Future에서 특별히 정의되어있다.  예를 들어, 우리가 서버 호스트 이름이 개많고 이 호스트들의 가동시간을 알기 위해 poll해야 한다고 해 보자.

import scala.concurrent._
import scala.concurrent.duration._
import scala.concurrent.ExecutionContext.Implicits.global
val hostnames = List(
  "alpha.example.com",
  "beta.example.com",
  "gamma.demo.com"
)
def getUptime(hostname: String): Future[Int] =
  Future(hostname.length * 60) // just for demonstration

이제, 우리가 모든 host를 poll해서 그들의 가동시간을 알기 원한다고 해보자. 우리는 단순하게 hostname들에 map연산을 적용 할 수 없다. 왜냐하면 결과가 List[Future[Int]]형이기 때문에 한개 이상의Future을 가지고 있기 때문이다. 우리는 결과를 우리가 블록으로 감쌀 수 있는 하나의 Future로 줄여야 한다. 우선 그냥 fold를 사용해서 이걸 하나하나 해 보자.

val allUptimes: Future[List[Int]] =
  hostnames.foldLeft(Future(List.empty[Int])) {
    (accum, host) =>
      val uptime = getUptime(host)
      for {
        accum <- accum
        uptime <- uptime
      } yield accum :+ uptime
  }

Await.result(allUptimes, 1.second)
// res2: List[Int] = List(1020, 960, 840)

우리는 이걸 해결하기 위해서 합성 함수를 매번 만들어 주어야 했고, empty list도 타입을 맞추어서 넣어 주어야 했다. 꽤나 복잡했다. 우리는이 패턴에 안성맞춤인 Future.traverse를 통해 이것을 해결할 수 있다.

val allUptimes: Future[List[Int]] = Future.traverse(hostnames)(getUptime)

Await.result(allUptimes, 1.second)
// res3: List[Int] = List(1020, 960, 840)

이게 훨씬 편하고 명확하다. 어떻게 동작하는지 보자. 만약 우리가 CanBuildFrom 나 ExecutionContext같은 번잡한 것들을 무시하면, Future.traverse는 아래와 같이 생겼다.

  def traverse[A, B](values: List[A])
                    (func: A => Future[B]): Future[List[B]] =
    values.foldLeft(Future(List.empty[B])) { (accum, host) =>
      val item = func(host)
      for {
        accum <- accum
        item <- item
      } yield accum :+ item
    }

높은 차원에서 간추려서 설명하자면 traverse는

- List[A]로 시작한다.

- function A => Future[B]로 가는 함수를 제공한다.

- Future[List[B]]로 끝난다.

 

* 더 직관적인 이해를 위해서 설명하자면, List[A]이고 A=>Future[B]함수를 통해 그냥 map하면 List[Future[B]]가 되는데 context순서를 서로 바꿔주는게 traverse이다 !!!!!!!!!!!!!!!!!!

 

 

standard 라이브러리는 Future.sequence라는 List[Future[B]]로 시작해서 identity function을 제공할 필요가 없는 메소드 또한 제공한다.

  object Future {
    def sequence[B](futures: List[Future[B]]): Future[List[B]] =
      traverse(futures)(identity)
    // etc...
  }

sequence 경우엔 직관적인 이해가 더 쉽다.

- List[Future[A]]로 시작.

- Future[List[A]]로 끝.

 

Future.traverse와 Future.sequence는 굉장히 특별한 문제를 푼다. 그들은 Future인 sequence를 돌고 결과를 누적한다. 위 예시는 List에서 동작했지만 standard Scala collection안에서면 다 동작한다.

또 Future, Option, Validated 등등에 대한 일반화된 타입클래스 패턴을 제공한다.

 

7.2.2 Traversing with Applicatives

자세히 살펴보면, 우리는 traverse를 Applicative로 재 작성이 가능한 것을 볼 수 있을 것이다. 우리의 위의 accumulator예시에서,

Future(List.empty[Int])

이것은 Applicative.pure와 동일하다. 

import cats.Applicative
import cats.instances.future._ // for Applicative
import cats.syntax.applicative._ // for pure

List.empty[Int].pure[Future]

(그러니까, applicative는 pure을 정의하는 친구니까 재작성이 가능하다고 한듯?)

 

우리의 combinator은 아래와 같이 생겼었다.

  def oldCombine( accum : Future[List[Int]], host : String ): Future[List[Int]] = {
    val uptime = getUptime(host)
    for {
      accum <- accum
      uptime <- uptime
    } yield accum :+ uptime
  }

이것은 이제 Semigroupal.combine과 일치한다.

import cats.syntax.apply._ // for mapN

// Combining accumulator and hostname using an Applicative:
def newCombine(accum: Future[List[Int]],host: String): Future[List[Int]] =
  (accum, getUptime(host)).mapN(_ :+ _)

semigroupal에서 product 함수같은거 보면 묶어줬으니까~ 그거랑 비슷하다고 한거.

 

이 스니펫을 traverse의 정의 안으로 대체하면, 우리는 어떠한 Applicative와도 일반화하여 사용할 수 있게 된다.

import scala.language.higherKinds

def listTraverse[F[_]: Applicative, A, B](list: List[A])(func: A => F[B]): F[List[B]] =
  list.foldLeft(List.empty[B].pure[F]) { (accum, item) =>
    (accum, func(item)).mapN(_ :+ _)
  }

def listSequence[F[_]: Applicative, B](list: List[F[B]]): F[List[B]] =
  listTraverse(list)(identity)

우리는 listTraverse를 사용해서 uptime 예시를 재 작성해볼 수 있다.

val totalUptime = listTraverse(hostnames)(getUptime)

Await.result(totalUptime, 1.second)
// res11: List[Int] = List(1020, 960, 840)

아래 예제에 있는 Applicative data type과 함께 사용 가능하다.

 

7.2.2.1 Exercise: Traversing with Vectors

 

다음 결과가 뭘까요?

import cats.instances.vector._ // for Applicative
listSequence(List(Vector(1, 2), Vector(3, 4)))

스포방지

미친 ㅋㅋㅋㅋㅋㅋㅋㅋ

Vector(List(1, 3), List(1, 4), List(2, 3), List(2, 4)) 이거네 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

Vector List 바뀌는거 깜빡함 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

이건 어떨까?

listSequence(List(Vector(1, 2), Vector(3, 4), Vector(5, 6)))

이건 안속지 ㅋㅋ

Vector(List(1, 3, 5), List(1, 3, 6), List(1, 4, 5), List(1, 4, 6), List(2, 3, 5), List(2, 3, 6), List(2, 4, 5), List(2, 4, 6))

이거다.

7.2.2.2 Exercise: Traversing with Options

 

여기에 Option을 사용하는 예시가 있다.

import cats.instances.option._ // for Applicative

def process(inputs: List[Int]) =
  listTraverse(inputs)(n => if(n % 2 == 0) Some(n) else None)

이 메소드의 리턴 타입은 뭘까? 아래의 인풋을 넣으면 어케 될까?

process(List(2, 4, 6))
process(List(1, 2, 3))

답은

일단 리턴 타입은 Option[List[Int]]

리턴 결과는

Some(List(2,4,6))

Some(List(2)) 이지 않을까? 했으나..

Some(List(2))가 아닌 None  이었다..;;;;;;

 

Some(List(2, 4, 6))
None

이게 답.

flatMap은 fail-first error handling이므로 하나가 실패하면 그냥 None을 리턴 해 준다.

 

7.2.2.3 Exercise: Traversing with Validated

 

마지막으로, Validated를 이용하는 예시이다.

  import cats.data.Validated
  import cats.instances.list._ // for Monoid
  type ErrorsOr[A] = Validated[List[String], A]
  def process(inputs: List[Int]): ErrorsOr[List[Int]] =
    listTraverse(inputs) { n =>
      if(n % 2 == 0) {
        Validated.valid(n)
      } else {
        Validated.invalid(List(s"$n is not even"))
      }
    }

 

다음 인풋을 넣으면 무엇이 튀어 나올까?

process(List(2, 4, 6))
process(List(1, 2, 3))

정답은 아마

Validation(List(2,4,6))

Validation(List("1 is not even", "3 is not even")) 일듯 ㅎㅎ

이라고 생각했는데

Valid(List(2,4,6))

Invalid(List("1 is not even", "3 is not even")) 이었다..

 

7.2.3 Traverse in Cats

우리의 listTraverse와 listSequence는 Applicative와 전부  동작하지만 sequence 타입 List와만 동작한다. (List안의 데이터를 임의의 Applicative안에 넣어주는 과정만 가능하다는 뜻.) 이것도 타입클래스를 통해 일반화 가능하다.

package cats

trait Traverse[F[_]] {
  def traverse[G[_]: Applicative, A, B](inputs: F[A])(func: A => G[B]): G[F[B]]
  def sequence[G[_]: Applicative, B](inputs: F[G[B]]): G[F[B]] = traverse(inputs)(identity)
}

 

Cats는 List, Vector, Stream, Option, Either 등 다양한 타입에 대한 Traverse 인스턴스를 제공한다. Traverse.apply를 통해 불러올 수 있고 이전에 설명한 대로 그냥 사용이 가능하다.

import cats.Traverse
import cats.instances.future._ // for Applicative
import cats.instances.list._ // for Traverse

val totalUptime: Future[List[Int]] =
  Traverse[List].traverse(hostnames)(getUptime)

Await.result(totalUptime, 1.second)
// res1: List[Int] = List(1020, 960, 840)

val numbers = List(Future(1), Future(2), Future(3))

val numbers2: Future[List[Int]] =
  Traverse[List].sequence(numbers)

Await.result(numbers2, 1.second)
// res3: List[Int] = List(1, 2, 3)

cats.syntax.traverse를 통해 import되는 syntax버전도 있다.

import cats.syntax.traverse._ // for sequence and traverse

Await.result(hostnames.traverse(getUptime), 1.second)
// res4: List[Int] = List(1020, 960, 840)

Await.result(numbers.sequence, 1.second)
// res5: List[Int] = List(1, 2, 3)

확인할 수 있듯, 훨씬 깔끔하게 순회가 가능해요~~~~ 짱짱

 

7.3 Summary

 

안읽었음.

 

 

…and with that, we’ve finished all of the theory in this book. There’s plenty more to come, though, as we put everything we’ve learned into practice in a series of in-depth case studies in Part II!

 

파트투는 저는 안 읽을것입니다 여기까지 같이 공부하신 여러분 고생 하셨습니다 ^_^7

 

 

 

 

오역/오개념 정정 제보 환영입니다~