Hi all :wave:, I'm currently wading through the tr...

# arrow

[marc0der]

Hi all 👋, I'm currently wading through the treacherous waters of Applicative and Traversable functors in the FP in Kotlin book 😅. I'm having some issues expressing some of the more advanced concepts like product, fusion and composition of types like Applicative and Traverse. An example of product would be when translating the following function from Scala:

def compose[G[_]](G: Applicative[G]): Applicative[({type f[x] = F[G[x]]})#f] = {
  val self = this
  new Applicative[({type f[x] = F[G[x]]})#f] {
   def unit[A](a: => A) = self.unit(G.unit(a))
   override def map2[A,B,C](fga: F[G[A]], fgb: F[G[B]])(f: (A,B) => C) =
    self.map2(fga, fgb)(G.map2(_,_)(f))
  }
 }

The problem here being how to express that type lambda ({type f[x] = F[G[x]]})#f. The unit and map2 functions should return types like (F[A], G[A]), translated to Kotlin that would be Tuple2<Kind<F, A>, Kind<G, A>>. From what I can tell, this simply isn't possible in Kotlin, but maybe someone else can see a way of achieving this that I just can't see.

[Jannis]

I think you may have the types mixed up here: A composed Applicative will look more like this:

fun just(a: A): Kind<F, Kind<G, A>>
fun Kind<F, Kind<G, A>>.map2(fgb: Kind<F, Kind<G, B>>, f: (A, B) -> C): Kind<F, Kind<G, A>>

This allows us to write an instance like this:

class Composed<F, G, A>(val v: Kind<F, Kind<G, A>>): Kind<ForComposed, Kind<F, Kind<G, A>>>

instance ComposedApplicative<F, G> : Applicative<Kind<ForComposed, Kind<F, G>>> {
  fun AF(): Applicative<F> // require F to be applicative
  fun AG(): Applicative<G> // require G to be applicative
  override fun <A> just(a: A): Composed<F, G> = Composed(AF().just(AG().just(a)))
  override fun <A, B, C> Composed<F, G, B>.map2(fgb: Composed<F, G, B>, f: (A, B) -> C): Composed<F, G, C> = AF().run {
    AG().run {
      v.map2(fgb.v) { ga, gb -> ga.map2(gb, f) }
    }
  }
}

Now admittedly this is not as nice as the scala version, and we don't even have this exact code in arrow atm. We are currently using a different type called Nested to create a Kind<Kind<F, G>, A> instead of using something like Composed<F, G, A> and make that higherkinded.
This makes stuff a bit uglier, but avoids wrapping and unwrapping.

For now this is all in this file: https://github.com/arrow-kt/arrow-incubator/blob/master/arrow-mtl-data/src/main/kotlin/arrow/mtl/typeclasses/Composed.kt

I will at some point add the code that I have written here to arrow, but probably not before we have actual newtypes so that the Composed wrapper gets removed at runtime.

[Jannis]

If you are just interested in the composed applicative and not all the rest, you can see it here: https://github.com/arrow-kt/arrow-incubator/blob/master/arrow-mtl-data/src/main/kotlin/arrow/mtl/typeclasses/Composed.kt#L307

[marc0der]

@Jannis apologies, my bad I got my wires crossed! I pasted the wrong snippet. I actually intended to paste the product function that has the return types I mentioned:

def product[G[_]](G: Applicative[G]): Applicative[({type f[x] = (F[x], G[x])})#f] = {
    val self = this
    new Applicative[({type f[x] = (F[x], G[x])})#f] {
      def unit[A](a: => A): (F[A], G[A]) = (self.unit(a), G.unit(a))
      override def apply[A,B](fs: (F[A => B], G[A => B]))(p: (F[A], G[A])): (F[B], G[B]) =
        (self.apply(fs._1)(p._1), G.apply(fs._2)(p._2))
    }
  }

This has a return type of (F[x], G[x]) as I mentioned. The type lambda here being ({type f[x] = (F[x], G[x])})#f

[marc0der]

I'll certainly look at your composition example too, as that is next up in the chapter.

[Jannis]

Ah well a literal translation won't work because of the higher kind emulation we have to do.
But this can be solved by newtyping again:

@higherkind
class Product<F, G, A>(val v: Tuple2<Kind<F, A>, Kind<G, A>>)
// now we can define
interface ProductApplicative<F, G> : Applicative<Kind<ForProduct, Kind<F, G>>> {
  // the implementation is easy now because we can go back and forth between Product and Tuple2 easily
}

Tbh I don't really like the scala encoding here, newtyping for instance resolution seems much better to me and there is lots of examples of this in the haskell world

[marc0der]

Ha! That is exactly what I was looking for. I totally agree with you about the Scala encoding, the type lambdas seem extremely obscure and difficult to comprehend. I'll give your approach a try and let you know how it goes.

[marc0der]

@Jannis I've had a good play and a lot of fun with your suggestion and arrived at something that I think could work. Would you be able to validate that my assumption is correct here?
Assuming a Product higher kind as shim:

@higherkind
class Product<F, G, A>(val value: Pair<Kind<F, A>, Kind<G, A>>) : ProductOf<F, G, A>

I have the following function for the product of two applicatives:

fun <F, G> product(
    af: Applicative<F>,
    ag: Applicative<G>
): Applicative<ProductPartialOf<F, G>> =
    object : Applicative<ProductPartialOf<F, G>> {
        
        override fun <A, B> apply(
            fgab: ProductOf<F, G, (A) -> B>,
            fga: ProductOf<F, G, A>
        ): ProductOf<F, G, B> {
            val (fab: Kind<F, (A) -> B>, gab: Kind<G, (A) -> B>) = fgab.fix().value
            val (fa: Kind<F, A>, ga: Kind<G, A>) = fga.fix().value
            return Product(Pair(af.apply(fab, fa), ag.apply(gab, ga)))
        }

        override fun <A> unit(a: A): ProductOf<F, G, A> = 
        	Product(Pair(af.unit(a), ag.unit(a)))
    }

This does deviate a little from your approach, but I wanted something that didn't require the fabrication of a ProductApplicative interface for the sake of simplicity of the exercise. Do you think that this will fly?

[Jannis]

Sure, this is perfectly fine. We do the extra interface everywhere in arrow because it allows us to reuse it when defining classes that extend others. For example IdMonad<A> : Monad<ForId>, IdApplicative<A>, but for composed instances like this it does not really matter 🙂