Composing functions that return an option

Question

Suppose I have a few functions of type Int => Option[Int]:

def foo(n: Int): Int => Option[Int] = {x => if (x == n) none else x.some}

val f0 = foo(0)
val f1 = foo(1)

I can compose them with >=> as follows:

val composed: Int => Option[Int] = Kleisli(f0) >=> Kleisli(f1)

Suppose now I need to compose all functions from a list:

val fs: List[Int => Option[Int]] = List(0, 1, 2).map(n => foo(n))

I can do it with map and reduce:

val composed: Int => Option[Int] = fs.map(f => Kleisli(f)).reduce(_ >=> _)

Can it (the composed above) be simplified ?

Answer 1

If you want the composition monoid (as opposed to the "run each and sum the results" monoid), you'll have to use the Endomorphic wrapper:

import scalaz._, Scalaz._

val composed = fs.foldMap(Endomorphic.endoKleisli[Option, Int])

And then:

scala> composed.run(10)
res11: Option[Int] = Some(10)

The monoid for kleisli arrows only requires a monoid instance for the output type, while the composition monoid requires the input and output types to be the same, so it makes sense that the latter is only available via a wrapper.

Answer 2

[A] Kleisli[Option, A, A] is a Semigroup via Compose, so we can use foldMap1:

val composed: Int => Option[Int] = fs.foldMap1(f => Kleisli(f))

Interestingly this doesn't work, though if we pass the correct instance explicitly then it does:

scala> val gs = NonEmptyList(fs.head, fs.tail: _*)
gs: scalaz.NonEmptyList[Int => Option[Int]] = NonEmptyList(<function1>, <function1>, <function1>)
scala> gs.foldMap1(f => Kleisli(f))(Kleisli.kleisliCompose[Option].semigroup[Int])
res20: scalaz.Kleisli[Option,Int,Int] = Kleisli(<function1>)
scala> gs.foldMap1(f => Kleisli(f))(Kleisli.kleisliCompose[Option].semigroup[Int]).apply(1)
res21: Option[Int] = None

I'm not sure where the instance that seems to take priority is coming from.