scala - Analog of Haskell's sequence

Question

What is the scala analog of Haskell's sequence function? http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:sequence

sequence is defined in Haskell as follows:

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) }

Here are some uses:

ghci> sequence [Just 1, Just 2, Nothing, Just 3]
Nothing
ghci> sequence [[1,2],[3,4],[5,6]]
[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]

Thanks in advance!

See also [this question](http://stackoverflow.com/q/12268351/334519) and [my answer](http://stackoverflow.com/a/12269252/334519) there. — Travis Brown, Apr 25 '13 at 01:35
Note also that you only need an applicative functor for `sequence`, so Scalaz's version is more general than Haskell's. — Travis Brown, Apr 25 '13 at 01:37
@TravisBrown: Your version is not more general than Haskell's version. Quite the opposite. See `sequenceA` from `Data.Traversable`. — ertes, Apr 25 '13 at 02:08
@ertes: More general in the sense that Scalaz's will work on an applicative functor that's not a monad (e.g. `Validation`), and the Prelude's won't. And yes, there's `sequenceA`, but the question mentions `sequence`. — Travis Brown, Apr 25 '13 at 02:36
@TravisBrown: I only gave the Prelude sequence as a point of reference - I'm new to scala, does scalaz' `sequence` work over Traversable and Foldable functors like the implementations of `sequenceA` in Haskell? — Matt W-D, Apr 25 '13 at 11:47

4lex1v · Accepted Answer · 2013-04-26T05:30:06.127

If you don't want to use scalaz, then you can implement it by yourself

def map2[A,B,C](a: Option[A], b: Option[B])(f: (A,B) => C): Option[C] =
  a.flatMap { x => b.map { y => f(x, y) } }

def sequence[A](a: List[Option[A]]): Option[List[A]] =
  a.foldRight[Option[List[A]]](Some(Nil))((x,y) => map2(x,y)(_ :: _))

Or an alternative implementation with traverse

def traverse[A, B](a: List[A])(f: A => Option[B]): Option[List[B]] =
  a.foldRight[Option[List[B]]](Some(Nil))((h,t) => map2(f(h),t)(_ :: _))

def sequence[A](seq: List[Option[A]]): Option[List[A]] = traverse(seq)(identity)

scala - Analog of Haskell's sequence

1 Answers1