(How) Can you curry compose monadic functions?

user_609074 0
Viewed 283

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.

function-composition currying scala monads haskell
1 Answers

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

EDIT

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:

  • from the type h :: a -> c -> m d It should be clear that we want some monad that behaves like m but takes c into acount.
  • from the type of 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.
  • Tankfully we can add an extra argument to f using 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.

user_92712660
Related