Variance expression in functional programming

LMAX Exchange

This time we’re going to explore how functional programs express
variance. We’ll consider the same case as we did for TDA – getting a
stored value from a Map, and storing a new value in a Map.

Retrieval

lookup :: Ord k => k -> Map k a -> Maybe a

In Haskell, the variance is expressed in the return type.

data Maybe a = Nothing
             | Just a

We might express this as follows:

variance ⊂ return type

Storage

We want to put a new value into the map.

Once again, the entropy of this function is two, see the previous
variance post for further discussion.

Here’s the comprehensive version:

insertLookupWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)

This function actually allows the caller to do more than our original
requirement, so a little explanation of that type signature is perhaps
necessary.

(k -> a -> a -> a)

The caller passes in this function, which takes the key, the new value
and the old value and produces the value that will be stored (most
implementations will simply return the new value, rather than
performing a calculation, mind).

Data.Map will only call this function if a value is already
present – this information is present in the last part of the type signature:

k -> a -> Map k a -> (Maybe a, Map k a)

This is the part we’re going to focus on. Here we pass the key, new
value, and the map to operate on. Note that the return type contains
both the possibility of an old value (the presence of which tells us
our value transforming function was called) and the new map.

Diversion one: encapsulation in FP

It’s starting to look as though functional programs eschew
encapsulation in favour of type signature totality (definitely a
thing). This is not true.

  • What if Maybe didn’t export its two constructors?

I fear the answer for some may be “huh”? So, a brief explanation of
how this might work.

Haskell makes it relatively simple to obscure your implementation
details. At the moment, we know that:

Maybe a = Just a
        | Nothing

In fact though, we only get to know this because the original author
allowed those constructors out to play. It would be just as valid to
export two functions that did the same but obscure the constructors, like so:

module Maybe (Maybe,just,nothing) where

data Maybe a = Just a
             | Nothing

just :: a -> Maybe a
just = Just
nothing :: Maybe a
nothing = Nothing

instance Functor Maybe where
fmap f (Just a) = Just $ f a
fmap _ Nothing = Nothing

Now, at the point of invocation, we can’t pattern match any more. We
have to use the fact that Maybe is an instance of Functor in order
to do anything with the value inside; there’s no way at all for us
to get it out.

Example: reversing the value, if it exists.

fmap reverse $ lookup "key" map

So, it looks like the core of the FP world; Functors and Monads
are very interested in not letting us execute a function on a value
directly; you pass the function you would like executed to the
enclosing context, and it can choose (based on the value inside) how
to execute it.

In particular in Haskell, syntactic sugar (do,<-, etc) is provided
to make it appear to the eye that this is not the case. That’s only
for humans, though; in reality the value never escapes.

Uh, so what now?

We used the term “return type” on the assumption that it is the last
thing we see in the type signature of a function. This is either almost
true or almost completely false.

Tony
Morris
tells us that all Haskell functions take one argument, and, once
you’ve read that link, I’ll hope you’ll agree he is right.

This means that for a function which appears to take n arguments
there are in fact n - 1 return types. Or, perhaps, they have one
return type, and it’s everything we see after the first ->.

We’ll stick with:

variance ⊂ return type

Totalitarianism, dogma and consequences

That’s enough pretentious subheadings -Ed

Just as we distilled OOP into a very dogmatic TDA, we’ve taken a very
dogmatic view of what FP is. Effects are delayed until the last
possible moment, and mutable state is excised.

Oddly, unlike in the TDA case, our chosen implementation language,
Haskell, is very keen on enforcing this dogma. Attempting to perform
calculations or effects outside of a function’s type signature is* a compile
error.

From here on out, we’ll assume dogmatic FP === FP and that non
dogmatic usages of FP languages are charlatanic. This isn’t
necessarily true, but it will save us a few words here and there.

(*almost always is. There is always Debug.trace)

Diversion 2: A mirror image

Cast your mind back to our purified TDA map insert. What would it look
like if we translate it to Haskell?

put :: (Ord k) => Map k a -> k -> a -> (a -> IO()) -> IO() -> IO()

You can think of a -> IO() as being a bit like Consumer and IO()
as being like Runnable. Haskell’s lazy predisposition allows us to
pass around putStrLn "nothing here" as an expression without
executing it.

Let’s rename that, and fiddle with argument order:

tda_insert :: (Ord k) => k -> a -> Map k a -> (a -> IO()) -> IO() -> IO()

Let’s also consider the core of the FP signature:

fp_insert :: (Ord k) => k -> a -> Map k a -> (Maybe a, Map k a)

Now, recall our stricter, non pattern matching Maybe implementation
from earlier. This told us that Maybe is actually a context for
executing functions that take an a. It also provides the following:

maybe :: b -> (a -> b) -> Maybe a -> b

If we just plug b = IO() into that, we get:

maybe :: IO() -> (a -> IO()) -> Maybe a -> IO()

and with some further shuffling, it becomes this:

maybe_ish :: Maybe a -> IO() -> (a -> IO()) -> IO()

Now, if we elide Map k a from fp_insert (thus making the state
change implicit)

fp_insert_ish :: (Ord k) => k -> a -> Map k a -> Maybe a

…and now, we almost have

tda_insert = maybe_ish . fp_insert_ish

This is very interesting! It feels like we’ve come across a little
piece of symmetry between the two approaches.

One way to think of this, perhaps, is that our TDA insert has
inlined Maybe. It acts both as an associative container and as a
context for function execution. The only difference (mind out though,
it’s a big one) is that fp_insert is far stricter about what those
functions are allowed to do.

We perhaps shouldn’t be surprised at this; what we’ve really found is
an artifact of tight encapsulation, which we introduced by definition
in both cases.

Why compose isn’t quite working

fp_insert_ish, as far as . is concerned, has type

fp_insert_ish :: (Ord k) => k -> (a -> Map k a -> Maybe a)

and maybe_ish is really wanting a Maybe a to start with. One can bind
enough of fp_insert_ish‘s parameters to get this to work; we’ll not
spend the time doing that here.

Having found some symmetry (admittedly with a little bit of hand
waving), let’s consider a less friendly asymmetry.

Interactions between FP and OOP

A lot of hot air has been generated about the exciting possibility of
combining the powers of OOP and FP approaches, as if they are some
sort of transformer robots that get a attack bonus, amazing music and
lens flares whenever they touch.

It’s not particularly clear whether this is true. We won’t try to
answer this question here at all. All we can do here is look at
TDA‘s interaction with FP.

  • Can FP code call TDA code?

No

The TDA approach deliberately obscures some variance in its type
signatures. You’d have to do some serious
gymnastics
to express the same thing in Haskell, and, once the core is infected
with mutability, the IO() virus spreads inexorably outwards.

  • Can TDA code call FP code?

Just about.

One can start to preach the church of return type in the core of an
application and gently push it outwards (TDA style callers can update a
mutable reference to the newly returned FP core, then send out the
(also returned) events).

This will cause some dissonance, but, and this is the very important
point, only at changeover points. Purity, unlike mutability, isn’t
upwardly mobile.

Diversion 3: Not today…

Whether this has any bearing on OOP / FP interweaving is left
temporarily as an exercise to the reader.

Serendipitously, Eric Meijer just wrote
something
excellent on the
wider question of hybrid OOP/FP approaches.

Conclusion

We found a tiny Maybe hidden in our TDA code; a symmetry due to the
encapsulation shared between our two approaches.

One wonders if other exercises TDAing the living daylights out of
other data structures would uncover any other fundamental types.

We found also one asymmetry between TDA and FP; implicit mutation
simply isn’t permitted in FP, so we can nest the approaches in one
direction only.

Extremely satisfying summary

Once we start to mutate, anyone above must mutate with us.

So: Pick the point of no return very carefully.

Next time

A selection from:

  • Do our truths about TDA tell us anything about OOP?
  • Does our TDA world bring us any new problems?
  • Does our TDA world bring us any benefits?
  • Will we ever get to talking about the Actor model?

Post script

There may be a small hiatus over the next couple of months while I
develop related material into a workshop for 2014′s SPA
Conference ( This
session is
mine ).

James Byatt LMAX Exchange Staff Blogs   LMAX   LMAX Exchange  

Any opinions, news, research, analyses, prices or other information ("information") contained on this Blog, constitutes marketing communication and it has not been prepared in accordance with legal requirements designed to promote the independence of investment research. Further, the information contained within this Blog does not contain (and should not be construed as containing) investment advice or an investment recommendation, or an offer of, or solicitation for, a transaction in any financial instrument. LMAX Group has not verified the accuracy or basis-in-fact of any claim or statement made by any third parties as comments for every Blog entry.

LMAX Group will not accept liability for any loss or damage, including without limitation to, any loss of profit, which may arise directly or indirectly from use of or reliance on such information. No representation or warranty is given as to the accuracy or completeness of the above information. While the produced information was obtained from sources deemed to be reliable, LMAX Group does not provide any guarantees about the reliability of such sources. Consequently any person acting on it does so entirely at his or her own risk. It is not a place to slander, use unacceptable language or to promote LMAX Group or any other FX and CFD provider and any such postings, excessive or unjust comments and attacks will not be allowed and will be removed from the site immediately.