Category Archives: design patterns

Simple Explaination of Monad

Here’s my shot at a simple explanation of what a monad is in the computer world. First, I have to explain what a monoid is.

A monoid is (roughly)  a group of functions who take a parameter of a certain type and return a result of that type.

That’s useful because it allows easy “chaining” or “composition” of functions. Any fluent interface in java is a monoid:

MyThing result = myThing.spin()
                        .treadle()
                        .flip()
                        .invert()
                        .aggregate();

Note that the input to each function is a MyThing, and the result is a MyThing.

A caution; strictly speaking, a monoid needs a few extra things. It needs an “identity” function that just returns the parameter, it needs a binary function that takes two items of the type and returns a new instance of the type, and those binary functions must be associative, so you can change the order of evaluation:

a.do(b).do(c) == a.do(b.do(c))

A monad takes the idea of monoid one step further; instead of mapping a class onto itself, it takes a container type which accepts any underlying type, and lifts that into a monoid space. So it’s a monoid using a container type:

A monad is (roughly) a group of functions who take a container type as an argument and return a result of the container type.

But note that the underlying type of the container may change. So you could map Container<String> to Container<Integer>. But the functions would still line up.

MyContainer<Int> myContainer = new MyContainer(1);
MyContainer<String> result = myContainer.<Int>rehash()
                                        .fondue()
                                        .serializeToString()
                                        .prefix()
                                        .onomatapeize();

So that you are able to “chain” or “compose” the functions and get a result of any arbitrary type! That’s a pretty strong claim for a statically-typed language like Java.

(Note that in Haskell, the signatures of the functions would be a little different. They would be functions of (Int, MyContainer) or (String, MyContainer), and it would be the job of the container to appropriately apply the function to it’s contents. But it’s hard to make a direct comparison from Java to Haskell, because Haskell works much more directly with function composition. In Haskell, the monad is actually composing the type constructors, rather than with instances of the type.)

But the core idea behind the monad is to create a monoid on a container type, in order to get the benefits of chaining and composition across different underlying types.

Advertisements

Leave a comment

Filed under computer architecture, computer OOD, design patterns

Using Double Underscores in Python, and the Black Death

OK maybe that title is sensationalistic.

A lot of people erroneously use double underscores to simulate “private” members, because double underscores invokes code mangling and makes those members harder to reference outside the class. However, it does not actually make them inaccessible.

Most of the time, it mainly adds a road bump to unit testing.

Really the double underscore mangling mechanism is to hide those members from subclasses that you don’t want clobbering the values inadvertently. Name mangling isn’t intended to hide the member from other programmers. The mangling scheme is simple, and referencing the variables anyway is easy.

Single underscore is the common convention for internal members. That’s saying, we’re all adults here, and although you can see it, this variable is intended for internal use. If you reference it, there’s no guarantee it will still be there in future versions.

The Pep8 doc talks about that, and says use of the double underscores for variables and functions should really be rare.

Leave a comment

Filed under design patterns, opinionizing, python

Wherefore Monads?

I’ve been looking at and playing with monads in the last week or so, and I think I’m getting pretty close to understanding them. From what I’ve seen, here’s why it’s a valuable design pattern.

If you’re familiar with the GoF patterns, monads are like the Decorator pattern and Builder pattern put together, on steroids, bitten by a radioactive badger.

  • monads decorate some core type with additional properties without changing the core type. For example, a monad might “lift” String and add values like “isWellFormed”, “isProfanity” or “isPalindrome” etc.
  • similarly, monads allow conglomerating a simple type into a collection type
  • monads allow late binding of functions into this higher-order space
  • monads allow mixing arbitrary functions and arguments with an arbitrary data type, in the higher-order space
  • monads allow blending pure, stateless functions with an impure, stateful base, so you can keep track of where the trouble is

A familiar example of a monad in Java is List. It takes some core class, like String, and “lifts” it into the monad space of List, adding information about the list. Then it binds new functions into that space like get(), getFirst(), add(), empty(), etc.

On a small scale, suppose there’s a code snippet you apply all over the place, like checking to see if a value is null. You can incorporate the null check into a little monad like Maybe — or better yet, return a Maybe that knows it’s null, avoiding null altogether. Then you can build or “lift” a value into the monad, and eliminate the repetitive code.

On a large scale, imagine that instead of writing a program, you just wrote a big Builder (as the GoF pattern), and the build() method at the end spat out whatever answer the program was supposed to produce. And that you could add new methods to your ProgramBuilder without recompiling the original code. That’s why monads are a powerful design model.

Leave a comment

Filed under design patterns, opinionizing, utility

Monadic Downcast

lol that’s kind of a cool title.

Downcasts are always a pain in the butt in an OO language. If you’ve designed your code correcly, you should never need to do a downcast. But sometimes you get stuck where you have to.

An upcast is the good kind of object cast, for example casting an ArrayList up to a List so you can handle it more generically. That’s a good practice in OO, something you should aim for.

A downcast goes the other way, for example saying, “I know this Object is really a BigInteger, so I’m going to cast it down the class hierarchy to a more specific type.” The problem is, the compiler can’t guarantee that an Object is a BigInteger, so you’re taking a chance that an Integer or String or whatever slipped in at runtime. You’re risking a Class Cast Exception.

The classic downcast situation is parsing a JSON structure into a nested Map heirarchy, and then pulling values out of it. Each Object in the map could be a String, List, or another Map. Sometimes, rather than encapsulating the JSON structure as a class structure, you encapsulate the data operation as an operation on a nested Map structure as a convenience.

Anyway…

C# has a nice “as” operator that will perform a cast, and return null if the cast isn’t valid. I always really liked that operator. So, inspired by that and my latest investigation of Monads, I came up with this utility.

It’s a monadic downcast utility class. The idea is that you instantiate one with the class that you want to cast to, and then invoke that instance to perform the down-cast.

It’s monadic because:

  • It “lifts” any arbitrary class into a monadic casting space.
  • It also provides a bind operation that allows you to perform arbitrary functions on the data, without recompiling the original code.

I’ve taken shortcuts with convention to make the code shorter. Also, note the @SuppressWarnings that suppresses the compiler warning you about the downcast you’re making.

The usage is to instantiate an As object, and then use the of to perform the cast. The result has an “isA” property (here it’s just an attribute, for brevity) if the cast is possible, and a “present” property if the object is not null. The “get” property returns the object as the type that you want.

Example:

// use a prototype for a custom class
    As<Thing> asThing = As.proto(Thing.class);
    As<Thing> t = asThing.of(o);
    if (t.isA) {
        t.get.doSomething();
    }
// or use the one of the convenience classes:
    As<Map<String, Object>> a = As.MAP.of(source);
    if (a.isA) {
        a.get.put("zoom", "pop");
    }
// or do a type conversion
    As<String> s = As.STRING.of("123");
    assert s.isA;

    As<Integer> i = s.bind(TO_INTEGER);
    assert i.isA;
    assert i.get == 123;

    // parse int
    static final Function<String, As<Integer>> TO_INTEGER = new Function<String, As<Integer>>() {
        public As<Integer> apply(String b) {
            try {
                return As.INTEGER.of(Integer.parseInt(b));
            }
            catch (NumberFormatException e) {
                return As.no();
            }
        }
    };

And here’s the implementation.

public class As<A> {

    // info we're tracking
    public final A get;
    public final boolean isA;
    public final Class<?> clazz;

    // some utility prototypes
    public static final As<Map<String, Object>> MAP = As.proto(Map.class);
    public static final As<List<Object>> LIST = As.proto(List.class);
    public static final As<String> STRING = As.proto(String.class);
    public static final As<Integer> INTEGER = As.proto(Integer.class);

    /** create a prototype */
    public static <A> As<A> proto(Class<?> clazz) {
        return new As<A>(clazz, null, false);
    }

    /** no of a certain type */
    public static final <X> As<X> no() {
        return new As<X>(null, null, false);
    };

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

    /** internal constuctor */
    As(Class<?> clazz, A get, boolean isA) {
        this.get = get;
        this.isA = isA;
        this.clazz = clazz;
    }

    /** of === unit ... lift a value into monadic space */
    @SuppressWarnings("unchecked")
    public As<A> of(Object a) {
        if (clazz == null) {
            return no();
        }

        boolean is = clazz.isInstance(a);
        As<A> that = new As<A>(clazz, is ? (A)a : null, is);
        return that;
    }

    /** bind :: m a -> (a -> m b) -> m b */
    public <B> As<B> bind(Function<A, As<B>> f) {
        if (! isA) {
            // I'd like to return a prototype, but can't because of type erasure
            return As.no();
        }

        return f.apply(get);
    }

    /** a nice to string */
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("{As");

        builder.append(" " + get);
        builder.append(" isA=");
        builder.append(isA);

        builder.append(" }");
        return builder.toString();
    }
}

And here’s a sample, using the classic case of traversing a generic map hierarchy to pull out data.

public class Sample0 {

    public static void main(String[] args) {
        Map<String, Object> source = sample();

        assert !As.MAP.of(null).isA;

        assert !As.MAP.of("booya").isA;

        As<Map<String, Object>> c = As.MAP.of(source.get("ma"));
        if (c.isA) {
            c.get.put("po", "op");
            System.err.println(c);

            As<String> d = As.STRING.of(c.get.get("li"));
            assert !d.isA;

            As<String> e = As.STRING.of(c.get.get("str"));
            if (e.isA) {
                System.err.println("String: " + e.get.substring(0, 1));
            }

            As<List<Object>> f = As.LIST.of(c.get.get("li"));
            if (f.isA) {
                System.err.println("List: " + f.get.get(0));
            }
        }
    }

    private static Map<String, Object> sample() {
        Map<String, Object> source = new HashMap<String, Object>();
        Map<String, Object> hoppop = new HashMap<String, Object>();
        List<String> zing = Arrays.asList("1", "2", "3");
        String booya = "booya";
        String zoopup = "zoopup";

        source.put("str", booya);
        source.put("li", zing);
        source.put("ma", hoppop);
        hoppop.put("str", zoopup);
        hoppop.put("li", zing);
        return source;
    }
}

BTW here is a demonstration that the implementation meets the Monadic Rules. Maybe I’ll post more about that later.

public class Rules {

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

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

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

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

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

        As<Integer> m = As.INTEGER.of(1);

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

    /** Left identity: return a >>= f ≡ f a */
    private static void leftIdentity(As<Integer> m) {
        As<String> left = m.bind(f);
        As<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(As<Integer> m) {
        As<Integer> left = m.bind(u);
        As<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(As<Integer> m) {
        As<Integer> left = m.bind(f).bind(g);
        As<Integer> right = m.bind(r);
        System.err.println(left + " " + right);
        assert left.toString().equals(right.toString());
    }

}

Leave a comment

Filed under computer algorithms, computer OOD, design patterns, utility

RESTful MONAD!

I was going through my old posts, and saw an old one about writing a RESTful Functional interface. One where functions are the resources.

I’ve moved past that, now. I’m considering a RESTful interface where the resources are MONADS! How cool would that be? I guess it would kind of be a superset of the Functional REST interface.

Maybe I should bite the bullet and write a RESTful interface for Categories. Then I’d be done forever.

Leave a comment

Filed under design patterns, opinionizing

You can Make a Monad in Java!

Monads are a hot topic in functional programming these days.

We’re all familiar with different types of operation chaining, which can look like:

thing.moveOnce(x).unshift(y).spindle(z);

Or another way, setting up function pipelines, based on one (or more) methods with the same signature.
thing.apply(myProcessor).loop(myOtherProcessor);

But monads are even more powerful. They take a number of functions with different signatures, and map an input space onto an output space, using a core set of rules for governance.

You can think of a monad as: a problem space, functions that map from inputs into that space, and a “binding” rule that governs those functions.

Or…

If you have a big, complicated function that maps from a bunch of variables (the input space) to a bunch of variables (the output space) creating a monad is the same as breaking that big function into a bunch of independent, composable functions. These smaller functions are goverened by the monad so they play nice together.

Plus the monad can track information outside the values of the type it extends. For example, you can add a boolen “errror” field to String handling to handle errors without throwing exceptions.

The primary elements needed for a monad are:

  • a group of target values
  • functions that map inputs into those values
  • a “bind” function that invokes those functions, and enforces global rules between them
  • a “unit” or “return” function that kicks things off

Once you have these composable functions, and the bind to rule them (in the darkness, I suppose), then a complicated problem breaks down into a number of simple problems.

Better yet, the simple problems can be arranged, new ones added, and so forth, giving you a high degree of flexibility and extendability in your code.

In the programming realm, monads are a design pattern. They implement the pieces listed above.

My first cut wasn’t quite right, because I had the bind() function mapping back to the same class. So watch my blog for an upcoming example of a monad that does downcasts safely.

Leave a comment

Filed under design patterns, opinionizing, utility

Anti-pattern: Framework Superclasses

Michael Feathers called out the anti-pattern of frameworks that require extension of classes in the framework. Hooray!

http://michaelfeathers.typepad.com/michael_feathers_blog/2013/01/the-framework-superclass-anti-pattern.html

Thank you for saying this out loud! Frameworks based on class extension are extremely appealing at first, particularly to the control freaks who want tight coupling in their applications (unbelievably I work with quite a few of those). Over time the loss of design flexibility and moving control from the “application” or the “problem domain” over to the framework leads to a lot of stale code that is hard to test and extend. In particular, I’ve seen systems with useful business logic that can’t be reused because it’s locked into framework hierarchies.

This is one of those anti-patterns that once you see it, it’s hard to unsee it.

Essentially, when you’re doing class design, object hierarchies should follow the problem domain. So in an accounting model, you should have classes like “Account”, “Creditor”, “Ledger” and whatnot. When building an application, you end up modelling the application space, which is not as clean, but hard to get away from. So you end up modelling artifacts like “…Handler”, “…Request”, “…Response”, “…Manager”.

A lot of engineers I work with see the problem domain as dumb data objects you pass to Handler or Manager classes, rather than modelling them as functional classes directly. But oh well.

What the superclass anti-pattern calls out is that the framework is taking control of the modelling effort and forcing application artifacts into its own hierarchy. That really moves the modelling effort away from the problem domain and locks it into the framework’s domain. A lot of engineers don’t see why that’s bad, because they just want the framework to tell them what to do. But the system as a whole pays the price for it.

That’s why the surge of POJO-oriented technologies have become so popular. It’s the recognition that I should be able to take my class, as-in, in my own problem domain and hand it to a framework for handling. There’s growing recognition of the power that provides.

Leave a comment

Filed under computer architecture, design patterns, opinionizing