Scala Stream(Scala関数型デザインより)
Scala Lazy!(Scala関数型デザインより) - shutdown -r nowからの続きで、Streamを扱う。
package example.laziness.stream import Stream._ trait Stream[+A] { def toList: List[A] = { @annotation.tailrec 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 } 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 } def takeWhile(f: A => Boolean): Stream[A] = foldRight(empty[A])((h, t) => if (f(h)) cons(h,t) else empty) @annotation.tailrec final def drop(n: Int): Stream[A] = this match { case Cons(_, t) if n > 0 => t().drop(n - 1) case _ => this } // (A, => B) は、(A,B)と同じようではあるが、遅延実行させるため // 第2引数を名前渡しで受け取る // def foldRight[B](z: => B)(f: (A, B) => B): B = this match { 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 forAll(f: A => Boolean): Boolean = foldRight(true)((a, b) => f(a) && b) def map[B](f: A => B): Stream[B] = foldRight(empty[B])((h,t) => cons(f(h), t)) def filter(f: A => Boolean): Stream[A] = foldRight(empty[A])((h,t) => if (f(h)) cons(h, t) else t) def append[B>:A](s: => Stream[B]): Stream[B] = foldRight(s)((h,t) => cons(h,t)) def flatMap[B](f: A => Stream[B]): Stream[B] = foldRight(empty[B])((h,t) => f(h) append t) def mapViaUnfold[B](f: A => B): Stream[B] = unfold(this) { case Cons(h,t) => Some((f(h()), t())) case _ => None } def takeViaUnfold(n: Int): Stream[A] = unfold((this,n)) { case (Cons(h,_), 1) => Some((h(), (empty, 0))) case (Cons(h,t), n) if n > 1 => Some((h(), (t(), n-1))) case _ => None } def takeWhileViaUnfold(f: A => Boolean): Stream[A] = unfold(this) { case Cons(h,t) if f(h()) => Some((h(), t())) case _ => None } def zipWith[B,C](s2: Stream[B])(f: (A,B) => C): Stream[C] = unfold((this, s2)) { case (Cons(h1,t1), Cons(h2,t2)) => Some((f(h1(), h2()), (t1(), t2()))) case _ => None } def zip[B](s2: Stream[B]): Stream[(A,B)] = zipWith(s2)((_,_)) def zipAll[B](s2: Stream[B]): Stream[(Option[A],Option[B])] = zipWithAll(s2)((_,_)) def zipWithAll[B, C](s2: Stream[B])(f: (Option[A], Option[B]) => C): Stream[C] = unfold((this, s2)) { case (Empty, Empty) => None case (Cons(h, t), Empty) => Some(f(Some(h()), Option.empty[B]) -> (t(), empty[B])) case (Empty, Cons(h, t)) => Some(f(Option.empty[A], Some(h())) -> (empty[A] -> t())) case (Cons(h1, t1), Cons(h2, t2)) => Some(f(Some(h1()), Some(h2())) -> (t1() -> t2())) } def startsWith[A](s: Stream[A]): Boolean = zipAll(s).takeWhile(!_._2.isEmpty) forAll { case (h,h2) => h == h2 } def tails: Stream[Stream[A]] = unfold(this) { case Empty => None case s => Some((s, s drop 1)) } append Stream(empty) def scanRight[B](z: B)(f: (A, => B) => B): Stream[B] = foldRight((z, Stream(z)))((a, p0) => { lazy val p1 = p0 val b2 = f(a, p1._1) (b2, cons(b2, p1._2)) })._2 } 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: _*)) val ones: Stream[Int] = cons(1, ones) def constant[A](a: A): Stream[A] = { lazy val tail: Stream[A] = Cons(() => a, () => tail) tail } 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 } def map2[A,B,C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] = a flatMap(aa => b map (bb => f(aa, bb))) def main(args: Array[String]): Unit = { val sl = Stream(1,2,3,4) val sl2 = Stream("a","b","c","d") val ass2 = constant("a").takeViaUnfold(5) println(s"ass2:${ass2}") println(s"ass2.toList:${ass2.toList}") val slstr = sl.mapViaUnfold((a) => a.toString() + "!") println(s"slstr:${slstr.toList}") val zips = sl.zip(sl2) println(s"zips:${zips.toList}") val zipws = sl.zipWith(sl2)((a,b) => a + "!!" + b) println(s"zipws:${zipws.toList}") val zipalls = sl.zipAll(sl2) println(s"zipalls:${zipalls.toList}") val zipwalls = sl.zipWithAll(sl2)((a,b) => map2(a,b)((aa,bb) => aa + "!!" + bb)) println(s"zipwalls:${zipwalls.toList}") val b = sl.startsWith(sl2) println(s"b:${b}") println("tails") sl.tails.toList.foreach(x => println(x.toList)) println("scanRight") println(sl.scanRight(0)(_ + _).toList) } }
constant
def constant[A](a: A): Stream[A] = { lazy val tail: Stream[A] = Cons(() => a, () => tail) tail }
無限ストリーム。Consで、tail側を余再帰呼び出しする。
val ass2 = constant("a").takeViaUnfold(5) println(s"ass2:${ass2}") println(s"ass2.toList:${ass2.toList}") > ass2.toList:List(a, a, a, a, a)
constantで、aの無限ストリームを作り、そこから、takeViaUnfold(5)で、5個取り出す。
map
trait Stream[+A] { def map[B](f: A => B): Stream[B] = foldRight(empty[B])((h,t) => cons(f(h), t)) def mapViaUnfold[B](f: A => B): Stream[B] = unfold(this) { case Cons(h,t) => Some((f(h()), t())) case _ => None } } object Stream { 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 } }
ストリームに対するmap。mapは、トレイトに実装し、その中で使われるunfoldは、Streamオブジェクトに実装。
unfoldは、引数で渡した関数がSomeを返す限り、無限ストリームになる。
mapは、自分のストリームに対して、関数fを適用するための関数。
自分をもと(this)に値があれば、hに関数を適用して、unfoldに渡すために、Someでつつむ。
val slstr = sl.mapViaUnfold((a) => a.toString() + "!") println(s"slstr:${slstr.toList}")
ストリームの各値のおしりに、"!"をつける。
zip
def zipWith[B,C](s2: Stream[B])(f: (A,B) => C): Stream[C] = unfold((this, s2)) { case (Cons(h1,t1), Cons(h2,t2)) => Some((f(h1(), h2()), (t1(), t2()))) case _ => None } def zip[B](s2: Stream[B]): Stream[(A,B)] = zipWith(s2)((_,_))
実行結果
> zips:List((1,a), (2,b), (3,c), (4,d)) > zipws:List(1!!a, 2!!b, 3!!c, 4!!d)
以下は、リストの場合のzipWith
def zipWith[A,B,C](a: List[A], b: List[B])(f: (A,B) => C): List[C] = (a,b) match { case (Nil, _) => Nil case (_, Nil) => Nil case (Cons(h1,t1), Cons(h2,t2)) => Cons(f(h1,h2), zipWith(t1,t2)(f)) }
ストリームの場合は、タプルで、(自分と結合するストリーム)を見て、
Consでつなげ、unfoldにわたすため、Someでつつむ
def zipWith[B,C](s2: Stream[B])(f: (A,B) => C): Stream[C] = unfold((this, s2)) { case (Cons(h1,t1), Cons(h2,t2)) => Some((f(h1(), h2()), (t1(), t2()))) case _ => None }
zipAll
def zipAll[B](s2: Stream[B]): Stream[(Option[A],Option[B])] = zipWithAll(s2)((_,_)) def zipWithAll[B, C](s2: Stream[B])(f: (Option[A], Option[B]) => C): Stream[C] = unfold((this, s2)) { case (Empty, Empty) => None case (Cons(h, t), Empty) => Some(f(Some(h()), Option.empty[B]) -> (t(), empty[B])) case (Empty, Cons(h, t)) => Some(f(Option.empty[A], Some(h())) -> (empty[A] -> t())) case (Cons(h1, t1), Cons(h2, t2)) => Some(f(Some(h1()), Some(h2())) -> (t1() -> t2())) }
実行結果
> zipalls:List((Some(1),Some(a)), (Some(2),Some(b)), (Some(3),Some(c)), (Some(4),Some(d))) > zipwalls:List(Some(1!!a), Some(2!!b), Some(3!!c), Some(4!!d))
zipWithAllは、パターンマッチングで、4パターンに分かれる。タプルのうち、両方がEmptyの場合のみ、Noneをunfoldにわたす。
Some(f(Some(h()), Option.empty[B]) -> (t(), empty[B]))
で、 「->」があるが、これは、タプルを表す。
scala> 1 -> 2 res0: (Int, Int) = (1,2) scala> List().->(2) res1: (List[Nothing], Int) = (List(),2) scala> (1 -> 2) == ((1, 2)) res2: Boolean = true
カッコが多いから、「->」を使っているようだが、逆にわかりづらい気もする。。
unfoldにわたすために、タプルのタプルをSomeでくるんでいる。
startsWith
def startsWith[A](s: Stream[A]): Boolean = zipAll(s).takeWhile(!_._2.isEmpty) forAll { case (h,h2) => h == h2 }
先頭比較のために、zipAllして、タプルのセットを作る。
takeWhileでタプルの2番目が空でない所まで取り出す。
forAllで、それぞれ取り出した値に対して、比較を行う。
map(_._ 2)はmap(x =>(x._2))の省略形 x._2はタプルの2番目の要素
tails
def tails: Stream[Stream[A]] = unfold(this) { case Empty => None case s => Some((s, s drop 1)) } append Stream(empty)
tailsは、実行例を見た方がイメージがつきやすい。
sl.tails.toList.foreach(x => println(x.toList)) List(1, 2, 3, 4) List(2, 3, 4) List(3, 4) List(4) List()
畳込みしないfoldRightのイメージで、途中式をStream[Stream[A]]にして返す。
scanRight
def scanRight[B](z: B)(f: (A, => B) => B): Stream[B] = foldRight((z, Stream(z)))((a, p0) => { lazy val p1 = p0 val b2 = f(a, p1._1) (b2, cons(b2, p1._2)) })._2
実行例
println(sl.scanRight(0)(_ + _).toList) List(10, 9, 7, 4, 0)
各tailsの結果を畳み込んだイメージ
Scala Lazy!(Scala関数型デザインより)
「Scala関数型デザイン&プログラミング」の「第 5 章 正格 と 遅延」
ストリームによる、Lazy処理を行う。
コード
package example.laziness import Stream._ trait Stream[+A] { def toListRecursive: List[A] = this match { case Cons(h,t) => h() :: t().toListRecursive case _ => List() } def toList: List[A] = { @annotation.tailrec 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 } 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 } @annotation.tailrec final def drop(n: Int): Stream[A] = this match { case Cons(_, t) if n > 0 => t().drop(n - 1) case _ => this } // (A, => B) は、(A,B)と同じようではあるが、遅延実行させるため // 第2引数を名前渡しで受け取る // def foldRight[B](z: => B)(f: (A, B) => B): B = this match { 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) def forAll(f: A => Boolean): Boolean = foldRight(true)((a, b) => f(a) && b) def takeWhile(f: A => Boolean): Stream[A] = foldRight(empty[A])((h, t) => { println(s"h:${h}") if (f(h)) cons(h,t) else empty } ) def headOption: Option[A] = foldRight(None: Option[A])((h,_) => { println(s"h:${h}") Some(h) }) } 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: _*)) def main(args: Array[String]): Unit = { val sl = Stream(1,2,3,4) println(s"sl:${sl}") println(s"sl:${sl.toList}") val r = sl.foldRight(0)((a,b) => a + b) println(s"r:${r}") val tw = sl.takeWhile((a) => a < 4) // この段階では、先頭だけfetchされる println(s"tw:${tw}") // toListを呼び出すと全部fetchされる println(s"tw:${tw.toList}") } }
Stream 定義
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) }
Streamは、サンク「() => A」で、渡して、すぐに評価させないようにする。
lazyキーワードをつけて、head遅延評価しつつ、キャッシュさせるようにする。
foldRight
// (A, => B) は、(A,B)と同じようではあるが、遅延実行させるため // 第2引数を名前渡しで受け取る // def foldRight[B](z: => B)(f: (A, B) => B): B = this match { def foldRight[B](z: => B)(f: (A, => B) => B): B = this match { case Cons(h,t) => f(h(), t().foldRight(z)(f)) case _ => z }
foldRightのfの定義次第で、遅延実行されるようになる。
val sl = Stream(1,2,3,4) val tw = sl.takeWhile((a) => a < 4) // この段階では、先頭だけfetchされる println(s"tw:${tw}") // toListを呼び出すと全部fetchされる println(s"tw:${tw.toList}")
即実行の場合の結果
def foldRightB(f: (A, B) => B): B = this match {
h:4 h:3 h:2 h:1 tw:Cons(example.laziness.Stream$$$Lambda$7/226170135@3b6eb2ec,example.laziness.Stream$$$Lambda$8/381707837@1e643faf) tw:List(1, 2, 3)
takeWhileが呼ばれた段階で、全データが取られてしまう。
遅延実行の場合の結果
def foldRightB(f: (A, => B) => B): B = this match {
h:1 tw:Cons(example.laziness.Stream$$$Lambda$7/226170135@43a25848,example.laziness.Stream$$$Lambda$8/381707837@3ac3fd8b) h:2 h:3 h:4 tw:List(1, 2, 3)
必要になった時(toListが呼ばれた時等)に、データを取る。
ORMフレームワークのlazy loadのようだ。
one more thing
@annotation.tailrec final def drop(n: Int): Stream[A] = this match { case Cons(_, t) if n > 0 => t().drop(n - 1) case _ => this }
末尾再帰させるために、finalをつける。 scalaが末尾再帰を最適化するためには、 再帰関数が、オーバーライドされる可能性のないメソッドであること。 つまり、メソッドを定義するクラスが final かメソッド自体がfinal、あるいは private であることなためである。
ScalaのEither(Scala関数型デザインより)
「Scala関数型デザイン&プログラミング」の「第 4 章 例外 を 使わ ない エラー 処理」のEither編。
package example sealed trait Either[+E,+A] { def map[B](f: A => B): Either[E, B] = this match { case Right(a) => Right(f(a)) case Left(e) => Left(e) } def flatMap[EE >: E, B](f: A => Either[EE, B]): Either[EE, B] = this match { case Right(a) => f(a) case Left(e) => Left(e) } def orElse[EE >: E, AA >: A](b: => Either[EE, AA]): Either[EE, AA] = this match { case Right(a) => Right(a) case Left(_) => b } def map2[EE >: E, B, C](b: Either[EE, B])(f: (A, B) => C): Either[EE, C] = for { a <- this; b1 <- b } yield f(a,b1) def traverse[E,A,B](es: List[A])(f: A => Either[E, B]): Either[E, List[B]] = es match { case Nil => Right(Nil) case Cons(h,t) => (f(h) map2 traverse(t)(f))(Cons(_,_)) } def sequence[E,A](es: List[Either[E,A]]): Either[E,List[A]] = traverse(es)(x => x) } case class Left[+E](get: E) extends Either[E,Nothing] case class Right[+A](get: A) extends Either[Nothing,A] case class Person(name: Name, age: Age) sealed class Name(val value: String) sealed class Age(val value: Int) object Either { def mean(xs: IndexedSeq[Double]): Either[String, Double] = if (xs.isEmpty) Left("mean of empty list!") else Right(xs.sum / xs.length) def mkName(name: String): Either[String, Name] = if (name == "" || name == null) Left("Name is empty.") else Right( new Name( name)) def mkAge(age: Int): Either[String, Age] = if (age < 0) Left("Age is out of range.") else Right(new Age(age)) def mkPerson(name: String, age: Int): Either[ String, Person] = mkName(name).map2(mkAge(age))(Person(_, _)) def main(args: Array[String]): Unit = { val ds = IndexedSeq(1.1, 2.2, 3.3) val result: Either[String, Double] = mean(ds) println(s"result:${result}") result match { case Right(a) => println(s"a:${a}") case Left(e) => println(s"e:${e}") } val ei = Right(1.0) val res = ei.map((a) => a + 2.0) //(1.0) println(s"res:${res}") val eiErr = Left("Error!!") val errRes = eiErr.map((a: Double) => a + 2.0) //(1.0) println(s"errRes:${errRes}") println(s"errRes OrElse:${errRes.orElse(Left("the other side."))}") val misia = Right(1.0) val r2 = Right(2.0) val resultMap = misia.map2(r2)((a,b) => a + b) println(s"resultMap:${resultMap}") val p = mkPerson("Totti", 18) println(s"p:${p}") p match { case Right(pp) => { println(s"name:${pp.name.value}") println(s"age:${pp.age.value}") } case Left(e) => println("Error!") } } }
こちらもOption同様、トレイトで実装。
map flatMap orElse
def map[B](f: A => B): Either[E, B] = this match { case Right(a) => Right(f(a)) case Left(e) => Left(e) } def flatMap[EE >: E, B](f: A => Either[EE, B]): Either[EE, B] = this match { case Right(a) => f(a) case Left(e) => Left(e) } def orElse[EE >: E, AA >: A](b: => Either[EE, AA]): Either[EE, AA] = this match { case Right(a) => Right(a) case Left(_) => b }
このパターンマッチングは簡単。
map2 traverse sequence
def map2[EE >: E, B, C](b: Either[EE, B])(f: (A, B) => C): Either[EE, C] = for { a <- this; b1 <- b } yield f(a,b1) def traverse[E,A,B](es: List[A])(f: A => Either[E, B]): Either[E, List[B]] = es match { case Nil => Right(Nil) case Cons(h,t) => (f(h) map2 traverse(t)(f))(Cons(_,_)) } def sequence[E,A](es: List[Either[E,A]]): Either[E,List[A]] = traverse(es)(x => x)
map2は、for内包表記を使う。
「<- 」で、ほどいて、fを適用する。
「<- 」は、Haskellだと、束縛というらしい。
「<- 」は、flatMap & mapに展開される。
case class Person(name: Name, age: Age) sealed class Name(val value: String) sealed class Age(val value: Int) (略) val p = mkPerson("Totti", 18) println(s"p:${p}") p match { case Right(pp) => { println(s"name:${pp.name.value}") println(s"age:${pp.age.value}") } case Left(e) => println("Error!") }
NameとAgeをclassにしているため、valueを参照する必要があるため、使い勝手がいまいち。。 typeの方がよい?
ScalaのOption(Scala関数型デザインより)
「Scala関数型デザイン&プログラミング」の「第 4 章 例外 を 使わ ない エラー 処理」をやる。
package example sealed trait Option[+A] { def map[B](f: A => B): Option[B] = this match { case None => None case Some(x) => Some(f(x)) } def flatMap[B](f: A => Option[B]): Option[B] = this match { case None => None case Some(x) => f(x) } def flatMap2[B](f: A => Option[B]): Option[B] = this map(f) getOrElse None def getOrElse[B>:A](default: => B): B = this match { case None => default case Some(a) => a } def orElse[B>:A](ob: => Option[B]): Option[B] = this match { case None => ob case _ => this } def orElse2[B>:A](ob: => Option[B]): Option[B] = this map(Some(_)) getOrElse ob def filter(f: A => Boolean): Option[A] = this match { case Some(a) if (f(a)) => this case _ => None } def filter_1(f: A => Boolean): Option[A] = flatMap(a => if (f(a)) Some(a) else None) // Option対応されていない関数(f: A => B)をOptionでくるまれた引数を取れるようにする def lift[A, B](f: A => B): Option[A] => Option[B] = _ map f def map2[A,B,C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] = a flatMap(aa => b map (bb => f(aa, bb))) def sequence[A](a: List[Option[A]]): Option[List[A]] = a match { case Nil => Some(Nil) //case h :: t => h flatMap (hh => sequence(t) map (hh :: _)) case Cons(h,t) => h flatMap (hh => sequence(t) map (Cons(hh, _))) //(h flatMap)は、OptionのflatMapを読んでいる } def traverse[A, B](a: List[A])(f: A => Option[B]): Option[List[B]] = a match { case Nil => Some(Nil) case Cons(h,t) => map2(f(h), traverse(t)(f))(Cons(_,_)) } def sequenceViaTraverse[A](a: List[Option[A]]): Option[List[A]] = traverse(a)(x => x) } case class Some[+A](get: A) extends Option[A] case object None extends Option[Nothing] object Option { def calcSlayer(n: Int): Option[Int] = if (n > 5) Some(n) else None def main(args: Array[String]): Unit = { val n = calcSlayer(99) println(s"n:${n}") println(s"n:${n.getOrElse(0)}") println(s"none:${None.getOrElse(0)}") //val m = n flatMap(aa => Some(aa)) val m = n.flatMap(calcSlayer) println(s"m:${m}") println(s"m:${m.getOrElse(0)}") val fnZ = n.lift((a: Int) => a + 100) println(s"fnZ:${fnZ(Some(7))}") val absO = misia.lift(math.abs) println(s"absO:${absO(Some(-11))}") val absb = (Some(-11)).map(math.abs) println(s"absb:${absb}") val misia = None val s1 = Some(1) val s2 = Some(2) val result = misia.map2(s1,s2)((a,b) => a + b) println(s"result:${result}") val lstSome = List(s1,s2) val optLst = misia.sequence(lstSome) println(s"lstSome:${lstSome}") println(s"optLst:${optLst}") val lstNone = List(s1,None,s2) val optNoneLst = misia.sequence(lstNone) println(s"lstNone:${lstNone}") println(s"optNoneLst:${optNoneLst}") } }
Optionのメソッドは、traitに登録する。 なので、Optionのメソッド達を使うためには、インスタンスが必要。
val misia = None val s1 = Some(1) val s2 = Some(2) val result = misia.map2(s1,s2)((a,b) => a + b) println(s"result:${result}")
mapとflatMap
def map[B](f: A => B): Option[B] = this match { case None => None case Some(x) => Some(f(x)) } def flatMap[B](f: A => Option[B]): Option[B] = this match { case None => None case Some(x) => f(x) } def flatMap2[B](f: A => Option[B]): Option[B] = this map(f) getOrElse None
- mapとflatMapは普通にパターンマッチで、NoneとSomeを見てやればよい。
- flatMapの場合は、fがOptionでくるんで返すので、Someの場合、そのままfを呼ぶだけで良い。
getOrElse
def getOrElse[B>:A](default: => B): B = this match { case None => default case Some(a) => a } def orElse[B>:A](ob: => Option[B]): Option[B] = this match { case None => ob case _ => this } def orElse2[B>:A](ob: => Option[B]): Option[B] = this map(Some(_)) getOrElse ob
こちらもパターンマッチでやる。 以下のような形で使う。
println(s"${None.getOrElse(0)}")
filter
def filter(f: A => Boolean): Option[A] = this match { case Some(a) if (f(a)) => this case _ => None } def filter_1(f: A => Boolean): Option[A] = flatMap(a => if (f(a)) Some(a) else None)
- こちらもパターンマッチングで。caseの条件にifを入れるのがミソ。
lift
// Option対応されていない関数(f: A => B)をOptionでくるまれた引数を取れるようにする def lift[A, B](f: A => B): Option[A] => Option[B] = _ map f
lift: Option対応されていない関数(f: A => B)をOptionでくるまれた引数を取れるようにする 「通常の関数をリフトして、Option対応にする。」という
val absO = misia.lift(math.abs) println(s"absO:${absO(Some(-11))}") val absb = (Some(-11)).map(math.abs) println(s"absb:${absb}")
絶対値返す関数(math.abs)をOption対応すると、
実行には、Optionを渡してあげる
mapをそのまま使う場合には、Option値に対して、直接実行する形となる
def lift[A, B](f: A => B): Option[A] => Option[B] = _ map f
liftの式の(_ map f)の「_」を「this」に変えると、その場で実行してしまう形となる。mapを実行した結果のOption[B]の値を返してしまうため、型があわずコンパイルエラーとなる。 「_」であれば、値を返すのではなく、fを「Option[A] => Option[B]」に変換した関数を返す。
map2
def map2[A,B,C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] =
a flatMap(aa => b map (bb => f(aa, bb)))
2項関数をOption対応にする。
flatMapとmapの内と外を間違えやすいが、flatMapに渡す関すは、(f: A => Option[B])だから、mapが内。
flatMapとmapで、つつまれたものを、ほどいた後、fに適用する。
sequenceとtraverse
def sequence[A](a: List[Option[A]]): Option[List[A]] = a match { case Nil => Some(Nil) //case h :: t => h flatMap (hh => sequence(t) map (hh :: _)) case Cons(h,t) => h flatMap (hh => sequence(t) map (Cons(hh, _))) //(h flatMap)は、OptionのflatMapを読んでいる } def traverse[A, B](a: List[A])(f: A => Option[B]): Option[List[B]] = a match { case Nil => Some(Nil) case Cons(h,t) => map2(f(h), traverse(t)(f))(Cons(_,_)) } def sequenceViaTraverse[A](a: List[Option[A]]): Option[List[A]] = traverse(a)(x => x)
sequenceは、Optionでくるまれた、リストを入れ替えて、リストをOptionにくるんで返す。
traverseは、リストにする際に関数を適用して、Optionにくるんで返す。
なので、sequenceは、何もしない関数をtraverseに渡せばよい。
case Cons(h,t) => map2(f(h), traverse(t)(f))(Cons(_,_))
traverseの、「map2(f(h), traverse(t)(f))(Cons(,))」は、map2でほどいて、Consするが、リストのtailをtraverse(t)(f)で、再帰して取り出している。
Scalaツリー遊び(Scala関数型デザインより)
リスト秋田県。 ツリーで遊ぶ。 2分木ツリーだよ。
package example sealed trait Tree[+A] case class Leaf[A](value: A) extends Tree[A] case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A] object Tree { def size[A](t: Tree[A]): Int = t match { case Leaf(_) => 1 case Branch(l,r) => 1 + size(l) + size(r) } def maximum(t: Tree[Int]): Int = t match { case Leaf(i) => i case Branch(l,r) => maximum(l) max maximum(r) } def map[A,B](t: Tree[A])(f: A => B): Tree[B] = t match { case Leaf(a) => Leaf(f(a)) case Branch(l,r) => Branch(map(l)(f), map(r)(f)) } def main(args: Array[String]): Unit = { val tree = Branch(Leaf(1), Branch(Leaf(2), Leaf(3))) val n = size(tree) println(s"n:${n}") } }
Scalaリスト遊び3(Scala関数型デザインより)
まだまだリストで遊ぶぞ。
def concat[A](l: List[List[A]]): List[A] =
foldRight(l)(Nil:List[A])(append)
- リストのリストを平らにする。やはりfoldRightで、右から、リストをappendしていく
def map[A, B](as: List[A])(f: A => B): List[B] = foldRight(as)(Nil:List[B])((h,t) => Cons(f(h),t)) def filter[A](as: List[A])(f: A => Boolean): List[A] = foldRight(as)(Nil:List[A])((h,t) => if (f(h)) Cons(h,t) else t) def flatMap[A, B](as: List[A])(f: A => List[B]): List[B] = concat(map(as)(f)) def filter2[A](as: List[A])(f: A => Boolean): List[A] = flatMap(as)(a => if (f(a)) List(a) else Nil)
- map関数。foldRightで、Nil:List[B]に対して、fを適用したあとに、Consでつなげる
- filter。Consの前のif (f(h))がミソ。else tも。
- flatMap。mapして、concatするだけ。mapの結果がList[List[A]]になるため。
- filter2。filterのflatMap実装。さっきは、Consでつなげていたが、List(a)かNilで返して、flatにする。
def addPairwise(a: List[Int], b: List[Int]): List[Int] = (a,b) match { case (Nil, _) => Nil case (_, Nil) => Nil case (Cons(h1,t1), Cons(h2,t2)) => Cons(h1+h2, addPairwise(t1,t2)) } def zipWith[A,B,C](a: List[A], b: List[B])(f: (A,B) => C): List[C] = (a,b) match { case (Nil, _) => Nil case (_, Nil) => Nil case (Cons(h1,t1), Cons(h2,t2)) => Cons(f(h1,h2), zipWith(t1,t2)(f)) }
- addPairwise zipWithのInt型版。match文がイディオム。
- addPairwiseを抽象化して、zipWithにすると、「+」メソッドの抽象化が必要になり、関数パラメータとしてもらう必要がある。
Scalaリスト遊び2(Scala関数型デザインより)
Scalaのリスト遊びの続き。
def reverse[A](l: List[A]): List[A] =
foldLeft(l)(List[A]())((acc:List[A],h:A) => Cons(h,acc))
引数で指定されたリストを逆にする。
def reverse[A](l: List[A]): List[A] =
foldLeft(l)(List[A]())((acc:List[A],h:A) => Cons(h,acc))
引数で指定されたリストを逆にする。
def foldRight2[A,B](l: List[A])(z: B)(f: (A, B) => B): B =
foldLeft(reverse(l))(z)((b,a) => f(a,b))
foldRightをfoldLeftを使って、実装する。 * reverseを使って、リストを逆にして、畳込み関数の引数も逆にして、実行する。
def append2[A](l: List[A], r: List[A]): List[A] = foldRight(l)(r)(Cons(_,_)) def append3[A](a1: List[A], a2: List[A]): List[A] = foldLeft(reverse(a1))(a2)((acc,h) => Cons(h,acc))
foldRightとfoldLeftを使ったappendの再実装。 * foldRightを使った方が素直。アキュムレータの初期値のrリストに対して、lのリストを右から読んでいって、Consでつなげていけばよい。 * Consの定義がCons+Aのため、このような形になる。
def foldRightViaFoldLeft_1[A,B](l: List[A])(z: B)(f: (A,B) => B): B =
foldLeft(l)((b:B) => b)((g,a) => b => g(f(a,b)))(z)
foldRightをfoldLeftを使って、実装する。 の別解。難しい。 * アキュムレータの初期値((b:B) => b)を関数にして、畳込み計算中には、実行させない。のと関数合成((g,a) => b => g(f(a,b)))を作って、初期値(z)を適用させているらしい。 codeday.me
以下は、appendの実行例。
val l = List(1,2,3,4,5) println(s"l:${l}") val l2 = List(6,7,8) println(s"l2:${l2}") val result = append2(l,l2) println(s"result:${result}") val result2 = append3(l,l2) println(s"result2:${result2}")