Groovy Monad Combinators

  1. groovy
  2. monad
  3. combinator
  4. sequence
  5. traverse
  6. io

 10 September 2014    Mark Perry    

In the previous post I discussed how to define monads in Groovy and looked a little at how they differ from functors and applicatives.

The payoff for defining monads is not having the methods unit and flatMap defined for the monad, although this is useful. The key benefit is the many methods derived from these methods that come with the abstraction.

We start by defining the methods unit and flatMap where:

  • unit - lift a value into the monadic type

  • flatMap - compose two actions, passing any value from the first as the argument to the second

From this the following (selection of) useful methods are derived:

  • apply - sequence computations and combine their results.

  • compose - monad composition.

  • filterM - monadic filtering

  • foldM - monadic folding

  • join - remove one level of structure

  • liftM - lift function to a monad

  • liftM2 - lift a two argument function to a monad

  • map - apply function to each element

  • map2 - apply a two argument function over two monads

  • replicateM - perform the monad n times, gathering the results

  • sequence - evaluate action left to right, gathering the results

  • traverse - map each element to an action and evaluate left to right, gathering the results.

I am going to focus on just a couple of these, sequence and traverse and show their usefulness for a few concrete types. The type signatures of these two methods are:

@TypeChecked
abstract class Monad<M> extends Applicative<M> {

    /**
     * Evaluate each action in the sequence from left to right, and gather the results.
     */
    def <A> M<List<A>> sequence(List<M<A>> list)

    /**
     * Map each element of a structure to an action, evaluate these actions from
     * left to right and gather the results.
     */
    def <A, B> M<List<B>> traverse(List<A> list, F<A, M<B>> f)
}

For the Option monad we can test the use of sequence and traverse as follows:

  • sequence a list of optional integers to get an optional list of integers

  • traverse a list of integers to determine if they are all even

@TypeChecked
class OptionMonadTest {

    static OptionMonad monad = new OptionMonad()

    @Test
    void sequence() {
        assert(monad().sequence([some(3), some(2), some(5)]) == some([3, 2, 5]))
        assert(monad().sequence([some(3), none(), some(5)]) == none())
    }

    @Test
    void traverse() {
        def even = { Integer i -> i % 2 == 0 ? some(i) : none()} as F
        assert(monad().traverse([2, 4, 6], even) ==  some([2, 4, 6]))
        assert(monad().traverse([2, 3, 6], even) ==  none())
    }
}

We have used integers here, but with just a little imagination you could sequence an optional value from a map, value from property files, successful remote calls or any other abstraction with a sequence of success/fail methods. For traverse, we map each integer to an Option<Integer> and gather the results to a List<Option<Integer>>. These two methods are quite similar, they both have the same return type. I believe they can be implemented in terms of each other. Perhaps you could try to do this yourself.

Now consider a little more exotic example of an input/output type (IO). We define an interface, which when the run method is called, returns a type A. We ignore any exception value in the following examples for simplicity.

public interface IO<A> {
    public A run() throws IOException;
}

We define an IO monad by implementing unit and flatMap:

@TypeChecked
class IOMonad extends Monad<IO> {

    @Override
    def <A> IO<A> unit(A a) {
        { -> a } as IO<A>
    }

    @Override
    def <A, B> IO<B> flatMap(IO<A> io, F<A, IO<B>> f) {
        { -> f.f(io.run()).run() } as IO<B>
    }
}

We define some referentially transparent IO functions which we will use:

    static IO<List<File>> listFiles(File f) {
        { ->
            def files = new ArrayList<File>()
            files.addAll(f.listFiles())
            files
        } as IO<List<File>>
    }

    static IO<List<File>> listFiles() {
        listFiles(new File("."))
    }

    static IO<Long> size(File f) {
        { -> f.length() } as IO
    }

    static IO<String> info(File f) {
        { -> "${f.name}:${f.length()}" } as IO
    }

Now we can use sequence and traverse to list the files in the current directory and their sizes. We use the sequence method first (whose type signature for IO is IO<List<A>> sequence(List<IO<A>>)).

    static IOMonad monad = new IOMonad()

    @Test
    void sequence() {
        def io = monad.flatMap(listFiles(), { List<File> list ->
            monad.sequence(list.map{ File f -> info(f) }) as IO<List<String>>
        })
        println(io.run().join("\n"))
    }

This produces the following output snippet for the FunctionalGroovy base directory:

.git:4096
.gitattributes:518
.gitignore:72
.gradle:0
.idea:4096
.travis.yml:453
build:0
build.gradle:3458
consume:4096
...

We can remove a map call in the example above by using the traverse method (whose type for IO is IO<List<B>> traverse(List<A>, F<A, IO<B>>)):

    static IOMonad monad = new IOMonad()

    @Test
    void traverse() {
        def io = monad.flatMap(listFiles(), { List<File> list ->
            monad.traverse(list, { File f -> info(f) }) as IO<List<String>>
        })
        println(io.run().join("\n"))
    }

Summary

Remember that sequence and traverse are just two methods derived from the definition of a monad. To view the full definition of monad combinators, go to the Github FunctionalGroovy Monad class.

Bibliography

comments powered by Disqus