I have the following functions:
f: a -> m[b]
g: (b,c) -> m[d]
h: (a,c) -> m[d]
How can h
be expressed as a composition of f
and g
?
Using do/for
notation we can implement h
easily like so:
h: (a,c) => {
for {
b <- f(a)
d <- g(b,c)
} yield (d)
}
However, I'm curious if we can express it like so: h = f andThen g
where andThen
is used like a monadic composition operator. For example:
f: a -> m[b]
g: b -> m[c]
h: a -> m[c] = f andThen g
I'm assuming that creating such an andThen
function is possible in languages like Haskell (e.g., Kliesli >=>
). In Scala we can write one like so: (example in Scala naming andThenE
since andThen
is already defined on instance of Function1
).
implicit class AndThenEither[A,B](val e: Function1[A,Either[_,B]]) {
def andThenE[C](f:Function1[B, Either[_,C]]): Function1[A, Either[_,C]] = {
(v1: A) => e.apply(v1).flatMap(b => f.apply(b))
}
}
Given this, it seems if we curry the functions we may be able to achieve such a composition (or at least it looks possible):
f: a -> m[b]
g: b -> c -> m[d]
h: a -> c -> m[d] = f andThen g
In theory this could work but I have no idea if this is possible or how to go about implementing something like this in Scala (or Haskell, although I'm more fluent with the former).
Let's say we had the following functions:
case class Error(e:String)
case class Output(i: Int, f: Float, s: String)
case class IntermediateOutput(i:Int, f:Float)
def f(i:Int): Either[Error, IntermediateOutput] = Right(IntermediateOutput(i+1, i*0.33)
def g(io: IntermediateOutput, s: String): Either[Error, Output] = Right(Output(io.i, io.f, "hello "+s))
val h: (Int, String) => Either[Error, Output] = f andThen g
val result = h(1, "world!") //Right(Output(2, 0.33, "hello world!")
Is this even possible/achievable? If not Scala, how could we go about curry composing monadic functions in Haskell or in general?
Is this a known thing or do we explicitly distinguish between currying being applicable to non-monadic functions and reserving the andThen
like operator for monadic ones, but avoid mixing the two? If so, I can see a strong case for the do/for
notation. However, I'm not entirely convinced that it's impossible and would like to understand this further. Perhaps the code would just be cluttered and that's okay - I'm simply curious. I stumbled on such a situation as a result of working on an existing problem and I couldn't cast it like so.
In functional programming, a monad is a software design pattern with a structure that combines program fragments (functions) and wraps their return values in a type with additional computation.
A monad is a way of composing functions that require context in addition to the return value, such as computation, branching, or I/O. Monads type lift, flatten and map so that the types line up for lifting functions a => M(b) , making them composable.
Map is not one of the defining properties of monads, however, because it's technically just a special case of FlatMap. A lifting function like Unit will wrap its object in a container, even if that object is itself the same type of container.
In Haskell there are some standard (i.e. in the base
lib) operators for that.
First, your andThen
function is the well known Kleisli composition:
>=> :: (a -> m b) -> (b -> m c) -> a -> m c
a -> m b
b -> m c
-----------------
a -> m c
This operator doesn't match exactly with your types due to g
operating in tuples and f
not returning a a tuple. This can be easily overcome with do/for
notation
h :: Monad m => (a -> m b) -> ( (b,c) -> m d ) -> (a,c) -> m d
h f g (a, c) = do
b <- f a
g (b, c)
I'd go for the solution above, but for the sake of curiosity, this problem has been faced already and the Haskell's base
library introduces a category-theory-oriented module called Control.Arrow
. Here you can find a pletora of operators to achive your goal:
import Control.Arrow
hKleisli :: Monad m => (a -> m b) -> ( (b,c) -> m d ) -> (a,c) -> m d
hKleisli f g = runKleisli $
first (Kleisli f) >>> Kleisli g
--| | |- this is just boilerplate
--| |- This composes Categories
--|- this converts f into a function operating in tuples
{--
Kleisli f :: Kleisli m a b -- a -> m b
---------------------------------------------
first (Kleisli f) :: Kleisli m (a,c) (b,c) -- (a,c) -> m (b,c)
Kleisli g :: Kleisli m (b,c) d -- (b,c) -> m d
---------------------------------------------
first (Kleisli f)
>>> Kleisli g :: Kleisli m (a,c) d -- (a,c) -> m d
--}
With regard to your comment: The original question is: how can we compose f
and g
after currying g
? and my solution looks more like let's uncurry f
to work with g
so I agree it isn't a complete solution. Ok let's solve your question, but first, some notes:
h :: a -> c -> m d
It should be clear that we want some monad that behaves like m
but takes c
into acount.f :: a -> m b
we know that f
has no access to c
and somehow It should be brought into scope. Otherwise, f
and h
could never be the same monad.const . f :: a -> c -> m b
So far we have
{--
The name of the type variables are chosen to match the ones used in this post, but are different in ghci
f :: a -> m b
g :: (b,c) -> m d
const . f :: a -> c -> m b
curry g :: b -> c -> m d
--}
Now It seems obvious that we need to use some monadic operator with const . f
and curry g
but the problem is that we need to preserve the monad m
and that can't be achive unless we wrap the result into some new data type, otherwise, the monad we would be refering is the function monad (->)
(Is this haskell specific? I think no). The obvious choice is to use the Kleisli
monad (ghc >= 8.10
). So now we have:
{--
The name of the type variables are chosen to match the ones used in this post, but are different in ghci
f :: a -> m b
g :: (b,c) -> m d
const . f :: a -> c -> m b
curry g :: b -> c -> m d
|- This result lives in the -> monad
Kleisli . const . f :: a -> Kleisli m c b
Kleisli . curry g :: b -> Kleisli m c b
--}
import Control.Monad
import Control.Arrow
f :: Monad m => a -> m b
f = undefined
g :: Monad m => (b, c) -> m d
g = undefined
-- And now, We have curryed and composed g
h :: Monad m => a -> c -> m b
h = runKleisli . (f' >=> g')
where
f' :: Monad m => a -> Kleisli m c b
f' = Kleisli . const . f
g' :: Monad m => b -> Kleisli m c d
g' = Kleisli . curry g
Notice, that this can be done using different monads than Kleisli
. Probably all solutions are isomorphic up to curry / uncurry. As long as you can bring c
to the scope of f
and find a monad that preserves the behaviour of m
you can apply this.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With