Functors, Applicatives and Monads in Java

Ismail S

September 2018

Intro

Abstraction of common design patterns
Underlying ideas are very general, but lots of practical applications

Warning

This stuff is hard to learn, especially for the first time. If it doesn’t make sense, ask.

Functors

Motivating examples

Optional

Sequencing operations and treating all failures in the same way

requestAFilenameFromUser().map(this::openFile);

Streams

Lazy lists

getAListOfFilesAsAStream()
    .map(this::filenameToFile)
    .map(this::readFileAsString)
    .collect(toList());

CompletableFuture

Representation of a value or error that will be available at some future time

performAnApiCall()
    .thenApply(this::transformResponse);

Function

Representation of a value that will be available once this function is called (it’s weird)

((Function<T, U>)this::someFunction)
    .andThen(aFunctionThatTransformsResultOfFirstOne)

Generic implementation

abstract class Functor<A> {
    public abstract <B> Functor<B> map(Function<A, B> func);
}

Haskell

class Functor f where
    fmap :: (a -> b) -> f a -> f b

Elevate a function (with one input) to operate on Functor objects

Rules

fmap id == id
fmap (f . g) == fmap f . fmap g

someFunctor.map(identity).equals(someFunctor);
someFunctor.map(g.andThen(f)).equals(someFunctor.map(g).map(f));

An example helper function

-- | Replace all locations in the input with the same value.
(<$) :: a -> f b -> f a
(<$) =  fmap . const

<$ is equivalent to:

public Functor<A> replaceWithConstant(A a, Functor<B> functor) {
    return functor.map(unused -> a);
}

Applicatives

Motivating examples

Optional

No library support. If there was, could look like:

Optional.applyTo(
    Optional.applyTo(Optional.pure(function),
    requestFirstNameFromUser()),
    requestSecondNameFromUser());

Or:

Optional.map2(function,
    requestFirstNameFromUser(),
    requestLastNameFromUser());

Streams

No library support. If there was, could look like:

Stream.applyTo(
    Stream.applyTo(Stream.of(function),
    stream1),
    stream2);

Or:

Stream.map2(function, stream1, stream2);

This can work in one of 2 ways:

For all combinations of elements of both streams, apply function and return a Stream with all results. With this definition, we can make Stream be an instance of Monad.
Apply the function to the first 2 elements of both streams, then the 2nd elements, etc, until the shortest length Stream is consumed. With this definition, Stream can’t be an instance of Monad.

CompletableFuture

Very limited library support (Only 2 arguments)

performAnApiCall()
    .thenCombine(
        performAnotherApiCall(),
        this::doSomethingWithTheTwoResponses);

Function

No library support. If there was, could look like:

Function.applyTo(
    Function.applyTo(unused -> function),
    func1),
    func2);

Or:

Function.map2(function, func1, func2);

where we have:

public A func1(T t);
public B func2(T t);
public C function(A a, B b);

Essentially, Function.map2 would have a type signature:

public Function<T, C> map2(
    BiFunction<A, B, C> func,
    Function<T, A> func1,
    Function<T, B> func2);

Generic implementation

abstract class Applicative<A> extends Functor<A> {
  public static <C> Applicative<C> pure(C a) {
      return null; // TODO-subclasses need to implement this
    }
  public abstract <B> Applicative<B> ap(Applicative<Function<A, B>> func);
}

Haskell

class Functor f => Applicative f where
    pure :: a -> f a

    -- | Sequential application.
    (<*>) :: f (a -> b) -> f a -> f b

Elevate a function (with many inputs) to operate on objects
Only invented/discovered in 2007.

Sequential application means we can do things like:

pure function <*> arg1 <*> arg2 <*> arg3

where all the arguments are Applicative objects thingies

Rules

pure id <*> v = v -- identity
pure (.) <*> u <*> v <*> w = u <*> (v <*> w) -- composition
pure f <*> pure x = pure (f x) -- homomorphism
u <*> pure y = pure ($ y) <*> u -- interchange

Some helper functions

-- | Lift a binary function to actions.
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
liftA2 f x = (<*>) (fmap f x)

-- | Sequence actions, discarding the value of the first argument.
(*>) :: f a -> f b -> f b
a1 *> a2 = (id <$ a1) <*> a2

-- | Sequence actions, discarding the value of the second argument.
(<*) :: f a -> f b -> f a
(<*) = liftA2 const

public Applicative<C> map2(BiFunction<A, B, C> func, Applicative<A> a, Applicative<B> b) {
    return a.ap(Applicative.pure(func)).ap(b);
    // note that this relies on being able to curry BiFunction
}

public Applicative<B> andThen(Applicative<A> a, Applicative<B> b) {
    return replaceWithConstant(Function.identity, a).ap(b);
}

public Applicative<A> thenAnd(Applicative<A> a, Applicative<B> b) {
    return andThen(b, a);
}

Monads

Some examples

Optional

requestAFilenameFromUser()
    .flatMap(this::openFile)
    .flatMap(this::parseFile)
    .flatMap(this::processFile);

Another example:

getFirstVal()
    .flatMap(a -> getSecondVal()
        .flatMap(b -> Optional.of(a + b)));

Streams

No library support. If there was, could look like:

multiplesOf3.monadMap(t ->
    multiplesOf5.monadMap(f ->
        if (t == f) {
            return Stream.of(t);
        } else {
            return emptyStream();
})).forEach(System.out::println);

CompletableFuture

performAnAPICall().thenCompose(a ->
    performAnotherAPICall().thenCompose(b -> {
        if (a.equals(b)) {
            return performALastAPICall();
        }
        return completedFuture("blah");
}));

Function

No library support. If there was, could look like:

this::getInputfileParam.flatMap(in ->
    this::getOutputfileParam.flatMap(out ->
        // TODO-do some computation
)).apply(getEnvironment());

Generic implementation

abstract class Monad<A> extends Applicative<A> {
    public static <C> Monad<C> retturn(C a) {
      return pure(a);
    }
    public abstract <B> Monad<B> flatMap(Function<A, Monad<B>> func);
}

Haskell

class Applicative m => Monad m where
    -- | Sequentially compose two actions, passing any value produced
    -- by the first as an argument to the second.
    (>>=) :: forall a b. m a -> (a -> m b) -> m b

    return :: a -> m a
    return = pure

Rules

return a >>= k  =  k a
m >>= return  =  m
m >>= (\x -> k x >>= h)  =  (m >>= k) >>= h

Example implementations

Optional

class Maybe<T> extends Monad<T> {
  public T t;
  public Maybe(T t) {
    this.t = t;
  }
  @Override
  public <U> Maybe<U> map(Function<T, U> func) {
    if (t != null) {
      return new Maybe<U>(func.apply(t));
    }
    return new Maybe<U>(null);
  }

  public static <U> Maybe<U> pure(U u) {
    return new Maybe<>(u);
  }

  public static <U> Maybe<U> retturn(U u) {
    return pure(u);
  }

  @Override
  public <U> Maybe<U> ap(Applicative<Function<T, U>> func1) {
    Maybe<Function<T, U>> func = (Maybe<Function<T, U>>) func1;
    if (func.t != null && t != null) {
      return new Maybe<>(func.t.apply(t));
    }
    return new Maybe<>(null);
  }

  @Override
  public <U> Maybe<U> flatMap(Function<T, Monad<U>> func) {
    if (t != null) {
      return (Maybe<U>)func.apply(t);
    }
    return new Maybe<>(null);
  }
}

List

class MonadList<T> extends Monad<T> {
  public List<T> list;
  public MonadList(List<T> list) {
    this.list = list;
  }
  @Override
  public <U> MonadList<U> map(Function<T, U> func) {
    return new MonadList<>(
      list.stream().map(func).collect(toList()));
  }

  public static <U> MonadList<U> pure(U u) {
    List<U> list = new ArrayList<>();
    list.add(u);
    return new MonadList<>(list);
  }

  public static <U> MonadList<U> retturn(U u) {
    return pure(u);
  }

  @Override
  public <U> MonadList<U> ap(Applicative<Function<T, U>> func1) {
    MonadList<Function<T, U>> func = (MonadList<Function<T, U>>) func1;
    List<U> result = new ArrayList<>();
    func.list.forEach(f -> {
      list.forEach(l -> {
        result.add(f.apply(l));
      });
    });
    return new MonadList<>(result);
  }

  @Override
  public <U> MonadList<U> flatMap(Function<T, Monad<U>> func) {
    List<U> result = new ArrayList<>();
    list.forEach(l -> {
      result.addAll(((MonadList<U>)func.apply(l)).list);
    });
    return new MonadList<>(result);
  }
}

ZipList

class ApplicativeList<T> extends Applicative<T> {
  public Stream<T> list;
  public ApplicativeList(Stream<T> list) {
    this.list = list;
  }
  @Override
  public <U> ApplicativeList<U> map(Function<T, U> func) {
    return new ApplicativeList<>(
      list.map(func);
  }

  public static <U> ApplicativeList<U> pure(U u) {
    // To satisfy rules for Applicative, we must create an infinite stream
    return new ApplicativeList<>(Stream.iterate(u, Function.identity));
  }

  @Override
  public <U> ApplicativeList<U> ap(Applicative<Function<T, U>> func1) {
    ApplicativeList<Function<T, U>> func = (ApplicativeList<Function<T, U>>) func1;
    return new ApplicativeList(zipStreams(list, func.list, a, b -> a.apply(b))); // TODO-zipStreams example implementations at https://stackoverflow.com/q/17640754
  }
}