How we used Category Theory to solve a problem in Java | Hacker News Reader

How we used Category Theory to solve a problem in Java

techblog.realestate.com.au

134 pointsit32 comments

This post really needs to explain why plausible alternative solutions (ideally ones used in real world open source projects) which are not monoids rapidly lead to having to deal with increased complexity. Otherwise, it's just bringing in a lot of terminology waving their hands saying "We came up with a solution that let us have mutiple extensions!" which, on the surface, seems pretty boilerplate.

Imagine you've got ten pieces you need to stick end to end

    a b c d e f g h i j

How many ways can you do that with a binary operation? i.e. how many ways can you completely parenthesise that expression. e.g.

    ((a (((b (c d)) e) ((f g) h)) i) j)

I haven't worked it out exactly, but I think it's about a trillion.

On the other hand, suppose your binary operation is associative. How many different ways are there now? Effectively one.

That's a huge reduction in complexity. The notion of associativity is extremely useful in developing composable programs.

Are you sure of that? Isn't the answer to your question the Catalan numbers, for which this case the answer is 4862?

I'm not sure at all! My calculation came out very wrong, and a quick sanity check should have told me it's implausible that it's in the trillions.

Anyway, 4862 times is still a substantial complexity reduction.

Thanks for the correction.

I totally agree with this, it was like 'here's a solution using category theory', but what were the alternatives? How is this useful/applicable to me, and why should I learn category theory?

It's worse than that, I think. They had some code that expects input in a certain format, they wanted it to accept input in a variety of other formats, and category theory was apparently necessary to come up with the idea of a format converter from each new format to the original format. Extremely basic. Trying to pretend it's a CT application is just pretentious in the extreme.

As far as I can tell, this is what category theory is for. It lets you take some quite basic structure or piece of work, and describe it in rigorous, impressive-sounding terms.

I never really gave it that much thought but I guess we use extensive category theory as well in our code base via RxJava and our own functional abstractions. IMO modern Java both code and design really has been going in that direction for some time (Guava, RxJava, Java 8, reactive programming etc). I think it boils down to the fact that composition of async things without functor like behavior is a rough. That is I want to say how the process should be but not actually run the process and delegate that to something else.

Yes! This isn't an accident. Erik Meijer, who contributed extensively to the Reactive Framework at Microsoft, has been very vocal about his use of category theory for software design. (https://www.youtube.com/watch?v=JMP6gI5mLHc) He currently runs Applied Duality which is uses category theory as its guiding design principle (http://www.applied-duality.com/)

They lost me at the point, after demonstrating how a functor can be defined on a list, when they claimed that a functor can similarly be defined on a binary tree.

One of the ten or so "Aha!" moments that each Haskell novice must experience on one's journey to mastery is the realization that you can't make Set an instance of Functor, at least as Functor is commonly defined in the standard Prelude. And the reason why one cannot do so is echoed by their misleading diagram in which their functor replaces each node in a binary tree with its mapped value. What needs to be appreciated is that the resulting tree is no longer ordered (assuming that the original was), and cannot be used to locate an element in logarithmic time.

They didn't say it was a binary search tree. The term Tree can simply be a root value and subtrees of children with a parent node, represented as a set of linked nodes.

That's fair, and one might usefully structure data thus if coding in a Lisp.

So this is an interesting bit of thought but I'm trying to figure out what it corresponds to in Haskell. Clearly what they're doing with `S` is effectively a `Reader s` monad in `Control.Monad.Reader`, and clearly what they're doing with `a -> a` is the `Endo a` monoid in `Data.Monoid`.

We can definitely create a `newtype` which composes any applicative with a monoid in the appropriate way:

    newtype ApMonoid a m = ApMonoid (a m)
    instance (Applicative a, Monoid m) => Monoid (ApMonoid a m) where
        mempty = pure mempty
        mappend (ApMonoid x) (ApMonoid y) = Wrap $ mappend <$> x <*> y

Then they have two data types: (1) they pull in a bunch of `Extras` up front and then each transformer successively pares down the extras to some subset of data that it cares about, then (2) each function transforms the search `Results`. We could say that this is:

    data Extras = Extras {e1 :: {- type1 -}, e2 :: {- type2 -}, ... eN :: {- typeN -}}

and their resulting transformation looks like:

    transN (eN extra) . ... . trans2 (e2 extra) . trans1 (e1 extra) :: Results -> Results

so I guess I'm trying to store `transN . eN` as something like an `ApMonoid (Reader Extras) (Endo Results)` via the above. The logic looks pretty solid.

However, if it doesn't kill the basic logic, it might be more Haskell-y to compose these by lifting the monoid to an applicative using `Const`, so that in this case:

    newtype ApAp a b x = ApAp (a (b x)) deriving (Functor)
    instance (Applicative a, Applicative b) => Applicative (ApAp a b) where
        pure = pure . pure
        (<*>) = liftA2 (<*>)

We would instead say that this is `ApAp (Reader Extras) (Const (Endo Results))`. Can anyone with more experience with such things comment on whether those are the same? I'm a little shaky here.

Also, there's no generic way to "drop" an applicative to be simply a monoid, right? We need an existing Monoid to feed to `ApMonoid`, no?

`type Extension s = s -> Endo Result` is already good enough IMO, since it's `Monoid` and we can also contramap thanks to `Profunctor (->)`. We don't have to bring in `ApAp`, which is anyway called `Compose` in `Data.Functor.Compose`.

Looks to me like a very long blog post about why you should use clojure.

I.e., use map and comp and avoid objects (to add 'extensions' the way you want).

The category theory + Java part certainly helps selling this to big enterprises though.

I'm slightly amazed that realestate.com.au has such an advanced tech blog...

Note: I should note that the reason for this was getting to be about 9 years ago, L.J. Hooker (who I believe owns realestate.com.au) were using Btrieve in it's original incarnation to manage all their listings. Total nightmare.

Yeah, it is interesting, as the other big RE listings player in Australia also has a tech blog: http://tech.domain.com.au/

realestate.com.au is Murdoch, in fact, but was a Melbourne startup many years ago.

"default <T> Extension<T> contraMap(Function<T, S> f) { return (T src, Results results) -> Extension.this.apply(f.apply(src), results); }"

Java 8 Lambdas provide such an elegant syntax for anonymous classes... When lambdas were first introduced in Java , a lot of people were underwhelmed by them. It is hard to evaluate at first the impact they can have on a well designed API.

Is this

    foldMap :: Monoid m => (a -> m) -> t a -> m

?

Interestingly, your comment can be read both as a naive "did I understand your code example", but also as "look how horrible this syntax is, and how much it obfuscates the underlying thought-process". It tells a lot about Java as a language.

Though the right comparison is

   default <T> Extension<T> contraMap(Function<T, S> f)
   foldMap :: Monoid m => (a -> m) -> t a -> m

I also prefer the Haskell syntax, but it looks like more of a difference because the implementation is inline.

To be fair, I afterwards thought that for some people, especially when taught with OOP, would see some functional abstractions as obfuscation. Each type of abstraction (objects, higher-order functions or continuations) work best with specifically designed syntax. I didn't like Scala too much for this reason, as it seemed a too bizarre combination (from a syntactic POV), as a contrast with Ocaml.

Anyway, tastes and education play a role there, but to me the arrow notation is way easier to read, as it is what I would write on paper.

I agree - I really had to deobfuscate / parse the signature first before even being able to start comprehending what it is about.

Not saying that there are no monster type signatures in Haskell (just recovering from one such instance in purescript-halogen), but it's really the most leightweight syntax for annotating types out there.

I often use Haskell signatures in comments when writing JS or whatever, just to keep the types straight.

It's just that OP quoted a multi-line function signature plus implementation in one line, which obfuscates things. Looking at just the comparable signature is pretty clear.

    <T> Extension<T> contraMap(Function<T, S> f);

It's this

  contramap :: (a -> b) -> f b -> f a

  http://hackage.haskell.org/package/contravariant-1.3.3/docs/Data-Functor-Contravariant.html#v:contramap

I thought "Extension" in this example is a Monoid. So maybe foldContramap? :)

That just seems broken?

If `f` is Function<T, S> then given `T src`, like we have, then f.apply(src) has type S. But Extension.this.apply is applied to values of S even though T is the thing qualified as an Extension.

Actually, I'm just entirely not sure I know how to read Java type signatures.

The part you're missing is the `this` in `Extension.this`. This method is a member of Extension<T>, and it returns an Extension<S>. So `this` (of type Extension<T>) is transformed by the method to Extension<S>.

Ah, thanks!

What I understood is that the goal was to reduce the information contained within some search results.

Why would one need anything special to think this through?

You wouldn't. I think saying you used category theory to design something just sounds cool and is basically a shibboleth. In fact, any time you compose functions you're using category theory. I think it sounds a little pretentious to be honest. No one says they used boolean logic when they wrote some code so saying you used category theory or type theory sounds equally weird.

I work with a guy that has a PhD in some heavy duty categorical machinery and I haven't heard him once say he used category theory to design some piece of code.

I'm skeptical that an ordinary Java person would ever think of this particular solution.

Composing a list of `A -> A` functions into a single one is already sort of a tall order. They would also have to realize that `(B, A) -> A` is equivalent to `B -> (A -> A)`, and that they can compose `A -> A` under the `B` environment. I just don't see this happening.

Reply on news.ycombinator.com