Java monad implementation

Question

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

Answer 1

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.