6
\$\begingroup\$

After asking a similar question on Stack Overflow, I'm picking up on the answer there to improve my monad. I'm not trying to solve the general case, just come up with one to see how it works. If I'm right, then I really like this pattern. I've already used it to rework some code I'm working on. So I hope it's right.

I was pretty strict about the signatures and not taking shortcuts that OO allows.

The (contrived) example is to provide semantics to represent a Friend relationship between two users. If there's an error, or the friendship is blocked, then processing stops. I have sample code that "lifts" Boolean, String and a custom Friend class into the monadic space, so I think that' a sign I'm on the right track. I've included the sample code lifting String into the monadic space.

My question is, did I get the monad implementation right? Please call out the places where I jumped the rails!

public class FriendSpace<A> {

    public boolean rejected = false;
    public String errors = "";
    public A original;

    public interface Function<B, MA> {
        MA apply(B b, MA a);
    }

    public FriendSpace<A> unit(A a) {
        FriendSpace<A> that = new FriendSpace<A>();
        that.original = a;
        return that;
    }

    public <B> FriendSpace<A> bind(B b, Function<B, FriendSpace<A>> f) {
        if (! errors.isEmpty()) {
            // we have errors; skip the rest
            return this;
        }

        if (rejected) {
            // No means no
            return this;
        }

        FriendSpace<A> next = f.apply(b, this);

        return next;
    }

    @SuppressWarnings("unchecked")
    public <B> FriendSpace<A> pipeline(B value,
           FriendSpace.Function<B, FriendSpace<A>>... functions) {
        FriendSpace<A> space = this;
        for (FriendSpace.Function<B, FriendSpace<A>> f : functions) {
            space = space.bind(value, f);
        }
        return space;
    }

    // toString omitted to save space
}

And here's an example where the (arbitrary) input is a People class, and the (arbitrary) class representing the friendship state is String.

public class People {

    public People(String from, String to) {
        this.from = from;
        this.to = to;
    }

    public String from;
    public String to;
}

@SuppressWarnings("unchecked")
public static void main(String[] args) {
    FriendSpace<String> proto = new FriendSpace<String>();

    People people0 = new People("Bob", "Fred");
    FriendSpace<String> space0 = proto.unit("");
    FriendSpace<String> friends0 = space0.pipeline(people0, VERIFY, INVITE, ACCEPT);
    System.err.println(friends0);

    People people1 = new People("Bob", "Jenny");
    FriendSpace<String> space1 = proto.unit("");
    FriendSpace<String> friends1 = space1.pipeline(people1, VERIFY, INVITE, ACCEPT);
    System.err.println(friends1);

    People people2 = new People("Fred", "Jenny");
    FriendSpace<String> space2 = proto.unit("");
    FriendSpace<String> friends2 = space2.pipeline(people2, VERIFY, INVITE, BLOCK);
    System.err.println(friends2);

    People people3 = new People("Bob", "Tom");
    FriendSpace<String> space3 = proto.unit("");
    FriendSpace<String> friends3 = space3.pipeline(people3, VERIFY, INVITE, ACCEPT);
    System.err.println(friends3);
}

public interface StringFunction extends FriendSpace.Function<People, FriendSpace<String>> {
}

static StringFunction VERIFY = new StringFunction() {
    public FriendSpace<String> apply(People from, FriendSpace<String> to) {
        String KNOWN_USERS = "Bob Fred Jenny";

        if (! KNOWN_USERS.contains(from.from)) {
            to.errors += "Unknown from: " + from.from;
        }

        if (! KNOWN_USERS.contains(from.to)) {
            to.errors += "Unknown to: " + from.to;
        }

        return to;
    }
};

static StringFunction INVITE = new StringFunction() {
    public FriendSpace<String> apply(People from, FriendSpace<String> to) {
        // Jenny has blocked Bob
        if ("Jenny".equals(from.to) && "Bob".equals(from.from)) {
            to.errors = "Jenny blocked Bob";
        }
        return to;
    }
};

static StringFunction ACCEPT = new StringFunction() {
    public FriendSpace<String> apply(People from, FriendSpace<String> to) {
        // Good to go!
        to.original = "YES";
        return to;
    }
};

static StringFunction BLOCK = new StringFunction() {
    public FriendSpace<String> apply(People from, FriendSpace<String> to) {
        to.original = "BLOCK";
        to.rejected = true;
        return to;
    }
};
\$\endgroup\$
8
\$\begingroup\$

Well, lets find out by checking the monad laws.

  1. (unit x) >>= f ≡ f x, which translates to the Java

    new FriendSpace<...>().unit(x).bind(..., f) ≡ f.apply(..., ...)
    

    wait, why do bind and Function.apply take two arguments in your case?Note that the instance which you call a method on is an implicit argument. And why is the type of apply :: (B, MA) → MA incompatible with the proper usage A → M<C>? It should look like

    new Friendspace<A>(x).bind(f) ≡  f.apply(x)
    
  2. m >>= unit ≡ m, which translates to the Java

    m.bind(..., new Function<..., ...>{
        public ... apply(..., ...){
            return new Friendspace<...>().unit(argumentToApplyFunction);
        }
    })
    ≡
    m
    

    Again, the arity of your methods is completely off. All the parts which don't make any sense have been marked with an ellipsis. Note that an equivalence relation is in no way required for monads, this notation is only chosen to emphasize that the two expressions should be equivalent for all purposes.

    It should look like:

    Friendspace<A> m = ...;
    
    m.bind(new Function<A, Friendspace<A>>() {
        public Friendspace<A> apply(A x){
            return new Friendspace<A>(x);
        }
    })
    ≡
    m
    
  3. (m >>= f) >>= g ≡ m >>= ( \x -> (f x >>= g) ), which should translate to

    Friendspace<A> m = ...;
    Function<A, Friendspace<B>> f = ...;
    Function<B, Friendspace<C>> g = ...;
    
    m.bind(f).bind(g)
    ≡
    m.bind(new Function<A, Friendspace<C>>() {
        public Friendspace<C> apply(A x) {
            return f.apply(x).bind(g);
        }
    }) 
    

    This is basically a requirement that bind composes the result of each function application in a sensible way.

Your class does not seem to be implementing the Monad pattern. A few pointers:

  • unit is basically just a constructor. It should either be a static method, or an actual constructor.

  • The bind operation takes a monad m :: M[A] and a function f :: A → M[B], and applies the function to each element contained in the monad. Each application returns a new monad, these are combined into a single one which then is the output of bind.

  • It is often more useful and simple to implement fmap :: (M[A], A → B) → M[B], as the transforming function doesn't need to know anything about the monad. If other languages like Haskell put a lot of emphasis on the bind, that's because bind is really important in its imperative “do-notation”, and because fmap can be easily derived from bind: fmap f m = m >>= (f . return), our in our Java notation:

    public <B> Monad<B> fmap(Function<A, B> f) {
        return this.bind(new Function<A, Monad<B>>() {
            public Monad<B> apply(A x) {
                return new Monad<B>(f.apply(x));
            }
        });
    }
    
  • Mixing monads with mutability can make for very confusing results. Monads are a clever way to compose operations, so using mutable data structures really isn't necessary when using monads.

  • The Scala language has a well-designed immutable collection library. The classes are written in a way so that they can be used as monads. I suggest you play a bit with those to get a better feeling of monads.

I created an example of a List monad for you to look at. The List is slightly different from a normal monad, as it's additive, i.e. [a, b] + [c, d] = [a, b, c, d]. This makes implementing bind properly quite easy. I used a List for the example, because it's something you are probably familiar with, and the implementation of the linked list shouldn't detract too much from the monad implementation itself.

\$\endgroup\$
  • \$\begingroup\$ Also, you make excellent points. I was trying to squint and ignore the implicit self argument ;) but I see how my arguments are wrong otherwise. Still, as "also ran" as it is, it gave me the kind of operation chaining I was looking for (!) So I think as I correct it, and understand the pattern better, it will get even stronger. Your insight is invalable -- thank you again. \$\endgroup\$ – Rob Feb 16 '14 at 15:39
  • \$\begingroup\$ By flatMap, do you mean fmap? flatMap is usually defined more like Haskell's bind. \$\endgroup\$ – fgb Feb 16 '14 at 17:50
  • \$\begingroup\$ @fgb I don't know Haskell that much, aren't fmap and flatMap basically the same thing? It may very well be that I screwed up in that paragraph, feel free to edit until it's correct \$\endgroup\$ – amon Feb 16 '14 at 18:36
  • 1
    \$\begingroup\$ No, fmap is just map defined on a functor. flatMap is map followed by flatten. \$\endgroup\$ – fgb Feb 16 '14 at 20:30
  • \$\begingroup\$ @amon a funny side note... I am playing with 2 monadic classes to get the signatures right, and more or less copied your monadic rule tests in. I got them working with the first class, copied them to the second class, did a global search/replace on the class name & magic! They worked without any other modification. I'm taking that as a good sign. But I want to stare at it some more. \$\endgroup\$ – Rob Feb 17 '14 at 8:58
0
\$\begingroup\$

amon still gets credit for the win, but I thought I'd post this as a follow up.

I have a fancier example here that's for handling downcasts and type conversions: Monadic Downcast

but I thought it would be fun to create an Any mondad that basically just wraps an object reference. Useful? Well, it permits late binding in Java, which is kind of a win. And I suppose it could be used as a initial code or a base class for something useful (haven't tried the latter).

EDIT: I suppose all the arguments for using monads as interpreters apply here, too. For example, while the code sample below uses "train wreck" syntax to chain the operations: .bind().bind().bind()... you could put your functions into a Map and then build your operation chains in configuration text. And it allows aspect-style insertion of new concerns without recompiling the old functions... So this is more of a starting point than anything else. /EDIT

The idea is that it's a Java monad that wraps a single object & provides a bind, so you can plug in new operations at runtime. Like I say, that's not revolutionary except for Java. ;)

Next up -- javascript!!!

public class Any<A> {

    public final A get;

    /** generic function interface -- note no monadic restrictions here */
    public interface Function<A, B> {
        B apply(A a);
    }

    /** internal constuctor */
    Any(A get) {
        this.get = get;
    }

    /** of === unit ... lift a value into monadic space */
    public static <A> Any<A> unit(A a) {
        return new Any<A>(a);
    }

    /** bind :: m a -> (a -> m b) -> m b */
    public <B> Any<B> bind(Function<A, Any<B>> f) {
        return f.apply(get);
    }

    /** a nice to string */
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("{Any ");
        if (get != null) {
        builder.append(get.getClass().getSimpleName());
        }
        builder.append(": ");
        builder.append(get);
        builder.append(" }");
        return builder.toString();
    }
}

Demonstration of the monadic rules:

public class Rules {

    /** int to string */
    static final Function<Integer, Any<String>> f = new Function<Integer, Any<String>>() {
        public Any<String> apply(Integer b) {
            return Any.unit("" + b);
        }
    };

    /** string to int */
    static final Function<String, Any<Integer>> g = new Function<String, Any<Integer>>() {
        public Any<Integer> apply(String b) {
            return Any.unit(Integer.parseInt(b));
        }
    };

    /** unit int */
    static final Function<Integer, Any<Integer>> u = new Function<Integer, Any<Integer>>() { 
        public Any<Integer> apply(Integer b) {
            return Any.unit(b);
        }
    };

    /** associative */
    static final Function<Integer, Any<Integer>> r = new Function<Integer, Any<Integer>>() { 
        public Any<Integer> apply(Integer b) {
            return f.apply(b).bind(g);
        }
    };

    /** test the monadic rules */
    public static void main(String[] args) {

        Any<Integer> m = Any.unit(1);

        leftIdentity(m);
        rightIdentity(m);
        associativity(m);
    }

    /** Left identity: return a >>= f ≡ f a */
    private static void leftIdentity(Any<Integer> m) {
        Any<String> left = m.bind(f);
        Any<String> right = f.apply(1);
        System.err.println(left + " " + right);
        assert left.toString().equals(right.toString());
    }

    /** Right identity: m >>= return ≡ m */
    private static void rightIdentity(Any<Integer> m) {
        Any<Integer> left = m.bind(u);
        Any<Integer> right = m;
        System.err.println(left + " " + right);
        assert left.toString().equals(right.toString());
    }

    /** associativity: (m >>= f) >>= g ≡ m >>= (\x -> f x >>= g) */
    private static void associativity(Any<Integer> m) {
        Any<Integer> left = m.bind(f).bind(g);
        Any<Integer> right = m.bind(r);
        System.err.println(left + " " + right);
        assert left.toString().equals(right.toString());
    }
}

And a sample usage. A boiled-down version of the solution amon provided:

public class Sample {

    public static final Function<Integer, Any<Integer>> SQUARE = new Function<Integer, Any<Integer>>() {
        public Any<Integer> apply(Integer a) {
            return Any.unit(a * a);
        }
    };

    public static final Function<Integer, Any<String>> STRINGIFY = new Function<Integer, Any<String>>() {
        public Any<String> apply(Integer a) {
            return Any.unit("" + a);
        }
    };

    public static void main(String[] args) {
        Any<Integer> i = Any.unit(5);
        Any<String> s = i.bind(SQUARE).bind(STRINGIFY);
        assert s.get.equals("25");
        System.err.println(s);
    }
}

lol that's a lot more typing than Haskell requires. But still a lot less work than getting my team to adopt Haskell ;)

\$\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.