Traverse

Traverse

今日はなんだか複雑な型クラスTraverse。
Functorを継承しています。

traverseという関数をもちます。

	case class ScalaChan[A](value: A)
	implicit def ScalaChanEqual[A]: Equal[ScalaChan[A]] = equalA
	implicit def ScalaChanShow[A]: Show[ScalaChan[A]] = showA
	implicit lazy val ScalaChanTraverse: Traverse[ScalaChan] = new Traverse[ScalaChan] {
	def traverse[F[_] : Applicative, A, B](f: A => F[B], t: ScalaChan[A]): F[ScalaChan[B]] = f(t.value).map(ScalaChan[B])
	}
	nel(1, 2, 3).traverse(_ +>: 1.some) assert_=== Some(NonEmptyList(2, 3, 4))
	ScalaChan(10).traverse(_ +>: 1.wrapNel) assert_=== NonEmptyList(ScalaChan(10), ScalaChan(1))
	1.some.traverse(_ +>: nel(1, 2, 3)) assert_=== NonEmptyList(Some(1), Some(1), Some(2), Some(3))

view raw traverse1.scala hosted with ❤ by GitHub

たぶんこれを見ても内部でどういったことをしているかわからないと思います。

sequence

Haskellのsequence関数を知っていますか？

	sequence :: Monad m => [m a] -> m [a]
	sequence ms = foldr k (return []) ms
	where
	k m m' = do { x <- m; xs <- m'; return (x:xs) }

view raw traverse2.hs hosted with ❤ by GitHub

Haskellのコードを見てもわからないのでScalaで書き直してみます。

	def sequence[M[_]: Monad, A](xs: List[M[A]]): M[List[A]] = {
	def k(m: M[A], n: => M[List[A]]): M[List[A]] = for {
	x <- m
	xs <- n
	} yield x :: xs
	xs.foldr(nil[A].pure[M])(k)
	}
	sequence(List(1.some, 2.some, 3.some)) assert_=== Some(List(1, 2, 3))

view raw traverse3.scala hosted with ❤ by GitHub

というかこれMonadである必要はなくね！？
と気付いた方、さすがです。
Applicativeで十分なので書き直してみます。

	def sequence[M[_]: Applicative, A](xs: List[M[A]]): M[List[A]] = {
	def k(m: M[A], n: => M[List[A]]): M[List[A]] = (m <**> n)(_ :: _)
	xs.foldr(nil[A].pure[M])(k)
	}
	sequence(List(1.some, 2.some, 3.some)) assert_=== Some(List(1, 2, 3))

view raw traverse4.scala hosted with ❤ by GitHub

実はこのsequence関数はScalazでも定義されています。
これはより汎用的なものでListのみではなく、Traverseのインスタンスを持つものならば利用可能です。
そしてこの関数は、traverse関数に恒等関数を渡すことで実装できます。

	sequence(List(1.some, 2.some, 3.some)) assert_=== List(1.some, 2.some, 3.some).sequence
	List(1, 2, 3).some.sequence assert_=== List(1.some, 2.some, 3.some)
	List(1, 2, 3).some.traverse(identity) assert_=== List(1, 2, 3).some.sequence

view raw traverse5.scala hosted with ❤ by GitHub

これらのことからtraverseはコンテナT[A]の要素Aを関数A => F[B]に適用してT[F[B]]になったものを畳み込み関数とApplicativeのapplyメソッドでF[T[B]]に変換する関数ということが・・・・・わかりにくいですよね、説明力なくてすみません・・・・・

実際には、畳み込み関数が使われているかどうかはTraverseのインスタンスの実装によって変わってきます。

Traverseの本質などは偉い人に聞いてもらうとして、ここではTraverseを使った関数を紹介します。

foldMapDefault

foldMapのTraverse実装。

	nel(1, 2, 3).foldMapDefault(_.shows) assert_=== "123"
	none[Int].foldMapDefault(_ |+| 100) assert_=== 0

view raw traverse6.scala hosted with ❤ by GitHub

collapse

sumのTraverse実装。

	List(1, 2, 3).collapse assert_=== 6
	none[String].collapse assert_=== ""

view raw traverse7.scala hosted with ❤ by GitHub

zipWithA

２つの値をコンテナにまとめてsequence。

	nel(1, 2).zipWithA(nel("Hello", "World"))(_.shows |+| _ |> Option.apply) assert_=== Some(NonEmptyList(1Hello, 1World, 2Hello, 2World))
	"a".some.zipWithA(1.some)((s, i) => s.parseInt.map(_ |+| i).toOption) assert_=== None

view raw traverse8.scala hosted with ❤ by GitHub

今回も説明がわかりにくくてごめんなさい。
ここで出てきたfoldr, foldMap, sumは近々書くので今日のところはこれでひとまずおわりです。