21
\$\begingroup\$

I'm learning functional programming and their concept of Monads. I've found nothing more effective in learning than writing an implementation in a programming language I have experience with.

I came up with the following implementation in Java. Could someone please suggest improvements?

So, I have an interface, Bindable:

public interface Bindable<T> {

    <E> Bindable<E> bind(Function<T, Bindable<E>> function);

}

And I have the Maybe implementation:

public class Maybe<T> implements Bindable<T> {
    private final State<T> state;

    public static <T> Maybe<T> just(T value) {
        return new Maybe<T>(new Just<T>(value));
    }

    public static <T> Maybe<T> nothing() {
        return new Maybe<T>((State<T>) Nothing.INSTANCE);
    }

    private Maybe(State<T> state) {
        this.state = state;
    }


    @Override
    public <E> Bindable<E> bind(final Function<T, Bindable<E>> function) {
        return state.accept(new StateVisitor<T, Bindable<E>>() {
            @Override
            public Bindable<E> visitJust(T value) {
                return function.apply(value);
            }

            @Override
            public Bindable<E> visitNothing() {
                return nothing();
            }
        });
    }

    @Override
    public String toString() {
        return Objects.toStringHelper(this)
                .add("state", state)
                .toString();

    }

    private static interface State<T> {

        <E> E accept(StateVisitor<T, E> visitor);

    }

    private static interface StateVisitor<T, E> {
        E visitJust(T value);

        E visitNothing();
    }

    private static class Just<T> implements State<T> {
        private final T value;

        private Just(T value) {
            this.value = value;
        }

        @Override
        public <E> E accept(StateVisitor<T, E> visitor) {
            return visitor.visitJust(value);
        }

        @Override
        public String toString() {
            return Objects.toStringHelper(this)
                    .add("value", value)
                    .toString();
        }
    }

    private static enum Nothing implements State<Object> {
        INSTANCE;

        @Override
        public <E> E accept(StateVisitor<Object, E> visitor) {
            return visitor.visitNothing();
        }


        @Override
        public String toString() {
            return "Nothing";
        }
    }
}

My Identity implementation:

public class Identity<T> implements Bindable<T> {
    private final T value;

    public static <T> Identity<T> create(T value) {
        return new Identity<T>(value);
    }

    private Identity(T value) {
        this.value = value;
    }

    @Override
    public <E> Bindable<E> bind(Function<T, Bindable<E>> function) {
        return function.apply(value);
    }

    @Override
    public String toString() {
        return Objects.toStringHelper(this)
                .add("value", value)
                .toString();
    }
}

And of BindableSequence:

public class BindableSequence<T> implements Bindable<T> {
    private final Iterable<Bindable<T>> sequence;

    public static <T> BindableSequence<T> create(Iterable<T> sequence) {
        ImmutableList.Builder<Bindable<T>> builder = ImmutableList.builder();
        for (T item : sequence) {
            builder.add(Identity.create(item));
        }

        return new BindableSequence<T>(builder.build());
    }

    public static <T> BindableSequence<T> create(T... sequence) {
        return BindableSequence.create(Lists.newArrayList(sequence));
    }


    private BindableSequence(Iterable<Bindable<T>> sequence) {
        this.sequence = sequence;
    }


    @Override
    public <E> Bindable<E> bind(Function<T, Bindable<E>> function) {
        List<Bindable<E>> result = Lists.newArrayList();

        for (Bindable<T> t : sequence) {
            Bindable<E> bind = t.bind(function);
            result.add(bind);
        }

        return new BindableSequence<E>(result);
    }

    @Override
    public String toString() {
        return Objects.toStringHelper(this)
                .add("sequence", sequence)
                .toString();
    }
}

And Sample class of how they can be used

public class Sample {

    public static void main(String[] args) {

        Bindable<Integer> result = Identity.create(5)
                .bind(new Function<Integer, Bindable<Integer>>() {
                    @Override
                    public Maybe<Integer> apply(Integer integer) {
                        return Maybe.just(integer * 10);
                    }
                })
                .bind(new Function<Integer, Bindable<Integer>>() {
                    @Override
                    public Bindable<Integer> apply(Integer integer) {
                        return BindableSequence.create(integer, integer + 10);
                    }
                })
                .bind(new Function<Integer, Bindable<Integer>>() {
                    @Override
                    public Maybe<Integer> apply(Integer integer) {
                        return Maybe.just(integer + 10);
                    }
                });

        System.out.println(result);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Note that without having return in your interface (which you can't in Java because interfaces can only specify instance methods), you can't do half the things with your Bindable interface that you can do with monads in Haskell (e.g. you won't be able to implement most of the functions from Control.Monad) including sequence, mapM etc. This makes Bindable much less useful then monads. \$\endgroup\$ – sepp2k Jan 21 '12 at 14:00
  • \$\begingroup\$ It seems odd to have a "monad implementation" that doesn't define anything named "Monad". Maybe this reflects the problem cited by @sepp2k ? Is "Bindable" that models the "bind" part of Monad behavior as close as you can get (without perhaps a radically different approach)? I'm trying to decide how much damage the "lack of return" argument does -- can you give a small example of what your Bindable definition can do in its current form? Perhaps show some generic code that operates abstractly on Bindable to do something useful/different for each of Maybe, Identity, and BindableSequence. \$\endgroup\$ – Paul Martel Jan 21 '12 at 16:10
  • \$\begingroup\$ @PaulMartel I added sample code of how Bindable can be used \$\endgroup\$ – Mairbek Khadikov Jan 22 '12 at 11:16
  • \$\begingroup\$ @Mairbek: Note that what you wrote would actually be illegal in Haskell. The function given to bind should return the same kind of monad that you're calling bind on. I.e. you're not allowed to return an Identity from a function that's given as an argument to bind on a Maybe. This works in this case, but if you consider for example the list monad, you'll see why this is problematic. \$\endgroup\$ – sepp2k Jan 22 '12 at 11:30
  • \$\begingroup\$ Also note that it's impossible to write methods that work with arbitrary monads in Java since already the type <M extends Bindable, T, U> M<U> bla(M<T>, Function<T,U>, M<U>) would be illegal. This makes the interface next to useless. \$\endgroup\$ – sepp2k Jan 22 '12 at 11:34
7
\$\begingroup\$

As mentioned in the comments, the problem with implementing monads in Java is that in an OO language class methods always work on a single instance. Type classes in Haskell are very different, there you can create values "out of nowhere" like in

class Monad m where
    return :: a -> m a
    -- ...

or

class Monoid a where
    mempty :: a
    -- ...

There is a functional library for Scala called Scalaz, which solves the problem in the following way: Instead of having an object implement an interface such as Bindable, it creates a separate object that carries all the functions of a "type class". Unfortunately this requires generic type parameters that take parameters themselves, so called higher-order kinds, which Java doesn't support. If Java had them, we'd write something like

public interface Monad<M<?>> {
    public <A> M<A> pure(A value); // return is a keyword
    public <A,B> M<B> bind(M<A> v, Function<A,M<B>> f);
}

and then for each monad type you'd define a singleton that implements this interface, such as Monad<Maybe>. However, Java doesn't allow this. And another problem is that you have to pass this singleton around in every computation, which is very inconvenient.

If you want to explore such functional concepts in a Java-like language, probably the best bet is to start learning Scala. Scala has implicit parameters which solve the problem with passing singletons around, and also has higher-order type parameters. In Scala you'd do something like

trait Monad[M[_]] {
    def pure[A](value: A): M[A];
    def bind[A,B](v: M[A], f: A => M[B]): M[B];
}

implicit object OptionMonad extends Monad[Option] {
    override def pure[A](value: A): Option[A]
        = Some(value);
    // in most cases Scala's flatMap corresponds to bind
    override def bind[A,B](v: Option[A], f: A => Option[B]): Option[B]
        = v.flatMap(f);
}

// Generic monadic computations use implicit parameters:
def liftM2[M[_],A,B,C](f: (A,B) => C, x: M[A], y: M[B])
                      (implicit m: Monad[M]): M[C] =
  m.bind(x, (x1: A) => m.bind(y, (y1: B) => m.pure(f(x1, y1))))

def sequence[M[_],A](xs: List[M[A]])(implicit m: Monad[M]): M[List[A]] =
  xs match {
    case Nil      => m.pure(Nil)
    case x :: xs  => liftM2[M,A,List[A],List[A]](_ :: _, x, sequence(xs))
  }

System.out.println(sequence(List[Option[Int]](Some(1), Some(2))))
System.out.println(sequence(List[Option[Int]](Some(1), None)))

Note that Scala has it's own concept for dealing with monadic computations using for-comprehensions, but that's out of the scope of this question.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.