Groovy Applicatives

 02 July 2014    Mark Perry    

My last post discussed creating Functors in Groovy [5]. I demonstrated how to create a list functor. Before we start creating the applicative abstraction, let’s create a functor based on the rich FunctionalJava Option type to review functors and to later demonstrate applicatives.

@TypeChecked
class OptionFunctor implements Functor<Option> {
    @Override
    def <A, B> Option<B> map(Option<A> o, F<A, B> f) {
        o.map(f)
    }
}

Note that I swapped the traditional order of the parameters to map to match Groovy’s convention of putting the closure as the last parameter of a method.

To motivate the example, I will be converting some of the code from the excellent book for FP beginners, Learn You A Haskell [2]. When we map over functors, the function we are mapping with takes a single parameter. Consider the case where a function takes multiple parameters, e.g. multiplication of integers takes two parameters. To use this to map over a list of integers we curry the multiply function and map the curried function over the list. This creates a list of functions (list1) where each function takes a single integer parameter and returns an integer. We can then map over this list with another function that takes the function from the list and applies it to multiply by a number, say three.

    @Test
    void test1() {
        def listFunctor = new ListFunctor()
        def list1 = listFunctor.map([1, 2, 3], curry({ Integer a, Integer b -> a * b }))
        def list2 = listFunctor.map(list1, { F<Integer, Integer> f -> f.f(3) })
        println list1
        println list2
    }

This produces the output:

[fj.F2Functions$2$1@4e91d63f, fj.F2Functions$2$1@d4342c2, fj.F2Functions$2$1@2bbf180e]
[3, 6, 9]

With functors, we can’t combine two functors together. Consider having a functor of List<F<Integer, Integer>> and a functor of List<Integer> and taking the integer value from the second functor and applying it to the function in the first functor. However, functors only support mapping over functors with normal functions. We need to construct a new abstraction that allows us to combine these two abstractions. This abstraction, called an applicative (or applicative functor), was first described in [3]. It will take practice to learn the intuition of the abstraction, so focus on the definition and examples and build intuition through usage. The Applicative class has two abstract methods (with other concrete methods omitted here):

@TypeChecked
abstract class Applicative<App> implements Functor<App> {
    abstract <A> App<A> pure(A a)
    abstract <A, B> App<B> apply(App<F<A, B>> a1, App<A> a2)
}

This could be expressed as a Groovy trait, but the current implementation of Groovy (2.3.3) does not allow this [4].

We define a List applicative to allow us to try our example which we couldn’t do with functors, we need to define the pure and apply methods from Applicative and the map method from Functor.

@TypeChecked
class ListApplicative extends Applicative<List> {

    @Override
    def <A> List<A> pure(A a) {
        [a]
    }

    @Override
    def <A, B> List<B> apply(List<F<A, B>> fs, List<A> list) {
        fs.flatMap { F<A, B> f ->
            list.map { A a ->
                f.f(a)
            }
        }
    }

    @Override
    def <A, B> List<B> map(List<A> list, F<A, B> f) {
        list.collect(f)
    }
}

We use the Groovy trick (abuse?) of applying type parameters to the generic type to keep type information as documented in my post on functors [5]. Don’t concern yourself too much with the implementation here, the type signature is the important part of each method. We can now use the applicative to combine a List<F<Integer,Integer>> and List<Integer>, which we could not do with functors.

	@TypeChecked
	class ListApplicativeTest {

		@Test
		void test1() {
			def listFunctor = new ListFunctor()
			def app = new ListApplicative()

			// two examples of the apply method of list applicative
			def list1 = (1..3).toList().map { { Integer a -> 4 + a } as F }
			def list2 = app.apply(list1, [1, 2, 3])
			def list3 = listFunctor.map([1, 2, 3], F2Functions.curry({ Integer a, Integer b -> a * b }))
			def list4 = app.apply(list3, [1, 2, 3])

			println list1
			println list2
			println list3
			println list4
		}
	}

Which produces the output:

[com.github.mperry.fg.typeclass.ListApplicativeTest$_test1_closure1_closure3@21507a04, com.github.mperry.fg.typeclass.ListApplicativeTest$_test1_closure1_closure3@143640d5, com.github.mperry.fg.typeclass.ListApplicativeTest$_test1_closure1_closure3@6295d394]
[5, 6, 7, 5, 6, 7, 5, 6, 7]
[fj.F2Functions$2$1@475e586c, fj.F2Functions$2$1@657c8ad9, fj.F2Functions$2$1@436a4e4b]
[1, 2, 3, 2, 4, 6, 3, 6, 9]

Let’s define an option applicative to further investigate the applicative abstraction.

@TypeChecked
class OptionApplicative extends Applicative<Option> {

    @Override
    def <A> Option<A> pure(A a) {
        Option.some(a)
    }

    @Override
    def <A, B> Option<B> apply(Option<F<A, B>> optF, Option<A> o) {
        o.flatMap { A a ->
            optF.map { F<A, B> f ->
                f.f(a)
            }
        }
    }

    @Override
    def <A, B> Option<B> map(Option<A> o, F<A, B> f) {
        o.map(f)
    }
}

In the code below we play with simple, one argument functions with the option applicative. I then include a more complicated example, where I curry a 3 argument function to produce a single function F<A, F<B, F<C, D>>> and gradually apply options until the final result is obtained. Note that this can be written more neatly using infix operators.

    @Test
    void test1() {
        def app = new OptionApplicative()
        F<Integer, Integer> f = { Integer a -> 3 + a } as F
        def o1 = app.apply(some(f), some(10)) // Some(13)
        def o2 = app.apply(some({ Integer a -> 3 + a } as F), some(10)) // Some(13)
        def o3 = app.apply(some(f), none()) // None

        // use the discriminate for quadratic equations: b^2 - 4ac
        F3<Integer, Integer, Integer, Integer> f3 = { Integer a, Integer b, Integer c -> b * b - 4 * a * c } as F3
        def o4 = app.apply(app.apply(app.apply(app.pure(Function.curry(f3)), some(4)), some(5)), some(3)) // Some(-23)
        // note, with infix methods we could have written this more elegantly as:
        // app.pure(Function.curry(f3)) app.apply some(4) app.apply some(5) app.apply some(3)

        println o1
        println o2
        println o3
        println o4
    }
Some(13)
Some(13)
None
Some(-23)

Instead of gradually applying applicatives, we can lift the function through the applicative using the method liftA3, defined on Applicative with the type signature

def <A, B, C, D> App<D> liftA3(F3<A, B, C, D> f, App<A> apa, App<B> apb, App<C> apc)

We could add a line to the code above to use this method:

    def o5 = app.liftA3(f3, some(4), some(5), some(3)) // some(-23)

We can also combine an arbitrary number of applicatives into a single applicative of a list of results of those applicatives. The method is called sequenceA (sequence applicative). It’s type signature is:

	def <A> App<List<A>> sequenceA(List<App<A>> list) { ... }

We can then combine various applicatives:

	def app1 = new OptionApplicative()
	def o1 = app1.sequenceA([some(3), some(2), some(1)]) // some([3, 2, 1])
	def o2 = app1.sequenceA([some(3), none(), some(1)]) // none()

	def app2 = new ListApplicative()
	def list1 = app.sequenceA([[1, 2, 3], [4, 5, 6]]) // [[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
	def list2 = app.sequenceA([[1,2,3],[4,5,6],[3,4,4],[]]) // []

	[[1, 2, 3], [4, 5, 6]].combinations() // [[1, 4], [2, 4], [3, 4], [1, 5], [2, 5], [3, 5], [1, 6], [2, 6], [3, 6]]

For lists, sequenceA creates lists of all possible combinations. This gives the same result (ignoring ordering) that the Groovy default method combinations on the Collection class.

It is expected that all applicatives satisfy the following properties (warning: Haskell code ahead):

  • identity: pure id <*> u == u

  • composition: pure (.) <*> u <*> v <*> w == u <*> (v <*> w)

  • homomorphism: pure f <*> pure x == pure (f x)

  • interchange: u <*> pure x == pure (\f → f x) <*> u where <*> is the apply method and (.) is function composition.

Once you grok applicatives you start seeing them everywhere. If you are familiar with monads, it turns out all monads are also applicatives, so all the monad classes you might be familiar with are also applicatives including:

  • IO

  • Set

  • Tree

  • List

  • Option

  • Software transactional memory (STM)

  • Arrows

  • Either (right biased)

Bibliography

comments powered by Disqus