ScalaでHaskellのsequenceを実現する

  • 1
    いいね
  • 0
    コメント

はじめに

ScalaのEitherでエラーを引きずり回していたときに、Listの中にEitherが入り込んでしまって困ってました。
そういえばHaskellにはsequence関数があって、中に入ったモナドをリストの外に出せるなと思いついたのですが...

なんとScalaにはHaskellのsequence相当の関数がデフォルトで準備されていません。
Scalazにはありますが、一回しか使わないなど簡単に済ませたいときにはちょっと大げさです。
そこでモナドの理解もかねて、自作してみようという試みです。

なお前提となる諸々は端折っておりますので、ご了承ください。

Haskellのsequenceとは

Haskellのsequenceは、以下のように型が定義されています。

sequence :: (Monad m, Traversable t) => t (m a) -> m (t a)

Monad mはどんなモナドでもかまいませんが、Traversable tは、Traversable型クラスに所属した型でなければ動きません。
例えば、mをMaybe、tをListとして考えてみると、こんな感じ。

Prelude> sequence [Just 5, Just 6]
Just [5,6]

sequenceは、右たたみ込みを使って簡単に自作することができます。
左ではなく右たたみ込みを使うのは、リストを結合する際に先頭に結合されてしまうためです。

import Control.Monad

sequence' :: (Monad m, Traversable t) => t (m a) -> m [a]
sequence' = foldr (liftM2 (:)) (return [])

空リストをデフォルトの文脈に入れ(return [])、その文脈から値を取り出して引数として与えたリストの末尾にある値と結合していく(liftM2 (:))だけの簡単な関数です。動作の流れのイメージは以下のような感じ。
矢印の左が元の値で、右が返り値だと思ってください。

1. [Just 5, Just 6] -> Just []
2. [Just 5] -> Just (6 : [])
3. [] -> Just (5 : 6 : [])
4. [] -> Just [5, 6]

Scalaでsequence

さて、ここからが本題です。デフォルトのScalaにはsequenceが存在しないので、頑張って実装していきます。
ScalaにはTraversableトレイトはありますが、Monadトレイトはないので、今回は汎用的ではなく専用の関数を作ります。
MonadにOptionを、TraversableにはListを用います。

とりあえず型を決めていきます。

def sequence[A](List[Option[A]]): Option[List[A]] = ???

Haskellの例を参考にしながら、実装します。

def sequence[A](list: List[Option[A]]): Option[List[A]] = {
  list.foldRight (Some(Nil): Option[List[A]]) { (value, acc) => 
    for (
      v <- value;
      a <- acc
    ) yield v :: a
  }
}

こちらもデフォルトの文脈に入れてから、出してくっつけて入れて、という作業を繰り返しています。
2引数関数を取ることができるmap(HaskellではliftM2)が無いため、for~yieldを使って同様のプログラムを実現しています。
また、型推論がうまくいかないため、Some(Nil)に対して型を指定しています。

さて、Scala 2.12で改良されたEitherでも同様のことをやってみましょう。
デフォルトでRight値を取るようになってくれたおかげで、以下のようなコードで済むようになりました。

def sequence[A](list: List[Either[String, A]]): Either[String, List[A]] = {
  list.foldRight (Right(Nil): Either[String, List[A]]) { (value, acc) =>
    for (
      v <- value;
      a <- acc
    ) yield v :: a
  }
}

おわりに

Haskellでの記述にはちょっと目をつぶるとして(そもそもデフォルトで入ってる)、Scalaでも意外と簡単に実装できました。
少ししか使わないのであれば、このぐらいの関数を自前で実装してしまった方が手軽そうです。
もちろん、本格的な関数型プログラミングを楽しみたい方(型?)は、Scalazでバリバリやっても良いと思います。

Eitherが中に入ってしまったリストからEitherを追いやる当初の目的も達成できましたし、一件落着ということで。

参考