(Pure) Functional Programming Claims IRL

So, THIS happened:

– question from a young programmer

So, does functional programming stack up in the real world? In industry?

Yes. Check my linkin profile. I have been programming, in industry, as long as you have been alive.

Here are some (pure) functional programming examples to back up this claim, because academics can talk all they want, but they are not in there, in the trenches, with you where it counts.

I am, because I happened to have dug a few of those trenches. You're welcome.

Case study 1: ATS-L

Worked on a project in DHS called 'ATS' ('Automated Targeting System'). The existing system ATS-C was a 100,000-line Prolog behemoth that used pure dynamic types (no type hints, nor boxed types) and every rule started with an assert and ended with a retract. And 100,000 lines.

It was impossible to know what was going on in that system, without running the code in the debugger and pulling from the dynamic environment. Consequently, the ATS-C guy had (still has) job security. Not his aim, but that is a nice plus.

It took us 72-hours to go through every line of his code to correct the Int-rollover problem when the primary key exceeded two billion for the index.

So, I was called in to 'help.' HA! But then eventually I built ATS-L. I wrote it in 10,000 lines of purely functional Prolog (yes, that is possible to do, and remain authentic to logic programming in Prolog), so every rule called gave the same truth-verification from the same set of arguments, every time.

Shocker! I know.

I had the same level of functionality of ATS-C and handled 1,000x the number of transactions per hour. And as it was purely functional Prolog, I could reason about my program in the large and in the small. Importantly, so could others, as I passed on that work after maintaining it for three years.

In short: 1/10th the SLOC with the same level of functionality with increased real-time responsiveness and a vastly reduced level of maintenance.

Oh, and I also wrote 726 unit tests and put them on an automated midnight run, generating a report every single day. If my system broke, or something changed, I knew it, and management knew it when the report was automatically emailed to them.

Case Study 2: CDDS

Worked three years in Fannie Mae devising within a team an appraisal review process, CDDS. We had a good team of five engineers and I was given the 'Sales Comparison Approach' which had 600 elements out of 2,100 data elements in over 100 data tables, one of the tables ingested 100 million elements per month. All the elements were optional. All of them, so primary key dependencies were an ... interesting problem. The upshot was that Sales Comparison Approach was an impossible task to code, as we coded it in Java, of course.

What did I do? I coded it in Java.

After I implemented the Maybe type, then the Monad type-class ... in Java.

After I completed the system and tuned it, storing only the values that were present in the submitted forms, my manager reported up the chain that SCA and CDDS would have failed if I had not been there to implement it.

How did I implement it? In Java. I didn't use one for-loop and my if-statements were not there. I used the Maybe-Monad to model semi-determinism, lifting the present data to Just x and the absent data ('null') to Nothing, and then I executed action against the monadic data.

Simple. Provable. Implemented. Done.

Oh, and I had written 1,000 of the 1,100 unit test cases. SCA had 1,000 unit test cases, the rest of the system had a total of 100 unit test cases.

My code coverage was fiiiiiiine.

Case Study 3: Sunset Dates

This one was interesting.

I worked at Freddy Mac for a year, and they had a problem, and that problem was to calculate the sunset date for a mortgage based on the most recent date from one of possibly five indicators, that changed with each possible mortgage transaction.

Three different software teams tackled this problem over a period of six months and none of them implemented a system that passed UAT.

I sat down with the UATester and kept getting part of the story. I lifted our conversations up into the categorical domain, and then dropped that into a Java-implementation (I used both monads and comonads which I had implemented).

It took me two solid months working with this tester and a front-end developer, but we passed UAT and we got the customer and their SMA to sign off on it.

Three person team, purely functional programming ... in Java won that work where standard imperative approaches failed, over and over again.

Funny story. I was seriously asked on that project: "What's a tuple?"

Case Study 4: Dependency Graphs of Program Requirements ('TMQER')

I can't compare what I wrote, in Haskell, to an alternative system, because the alternative, traditional imperative approach was never essayed. We had a set of 521 requirements for a program with many (multiple) parent and child dependencies, so it wasn't a tree, it was a graph. So, I parsed the requirements document into a Haskell Data.Graph and provided not only a distance matrix, as requested (which is not what the customer wanted at all: it was just what they said and thought they wanted), but also clustering reports of which requirements were the 'heaviest' having the most dependencies and which requirements were show-stoppers to how many follow-on requirements.

Then I uploaded my Haskell Graph into Neo4J, making heavily-clustered requirements an obvious visual cue. And we won that contract.

The project wasn't attempted in Java. The project was attempted in R, and it couldn't be done. They estimated the graph manipulation algorithm would be 200-lines of code in R, that they couldn't get working.

With comonads, I did it in one line of Haskell. One line for a graph deforestation algorithm to get to the bare essentials of what was important to the project. Wanna see it?

How hard was that? In Haskell, a pure functional programming language, not hard at all.

Not only that, that we won a contract that our competing companies said was impossible, but our VP got wind of this and started vetting my tech to other companies.

We have a contract in the works, right now, using Haskell and Neo4J on AWS that is answering questions about fuzzy relations in social networks that a company that is expert in social engineering needs us to answer.

And I can answer these questions using graph theory and purely functional programming.

Case study 5: the one that got away

Oh, and then there was the one that got away. It had to do with a neural network I built in Mercury, a purely functional logic programming language with Prolog-like syntax that was able to classify images into 'interesting' and (mostly) 'not-interesting' but 'interesting' had very specific, different meanings, and it was able to classify these images, using a pulse-coupled neural network, in ways that eliminated 99% of waste images quickly so that analysts could concentrate on doing work, as opposed to sieving through the deluge of useless images to get the the ones they needed to see.

I build a working prototype and demoed it.

This had never been done before. Ever.

Then, a Big Six came in and said, 'we can do that for you with 250 programmers and Java' and stole the project. After ten years and billions of dollars, they were unable to reproduce my work.

Pure Functional Programming Claims IRL

So, let's do a real-money tally.

ATS-L in one month, in the three years I maintained it (it is still up and running ten years later, ladies and gentlemen) made $26 million dollars in seizures and rescued three teens being human-trafficked over the border.

CDDS has been in production since the year 2010 and has verified appraisals helping Fannie Mae to make 62 Billion dollars in net profit in one quarter the year it went live, actually contributing to the rescue of Fannie Mae from insolvency.

TMQER has rescued a government run program from failure that has the funding price-tag of over 100 Million dollars of Government (your) taxpayer (your) money. You're welcome.

Sunset dates I wish I had a dollar amount, but you can estimate for me: three teams of business analysts and software engineers over a six month period said it couldn't be done (or tried it and failed). I scrapped all that code, wrote the system from first principals (Category Theory) and got it working and approved in two months. You do the math.

... Oh, and then there's my current project. I might actually be able to own this thing. Hmmmm.

So, yes, Virginia,

1. there is a Santa Clause
2. those academics are actually onto something. (Pure) functional programming actually does matter. It actually does allow you to program better, faster and more cleanly, and with these enhanced skill-sets you become the one they turn to when other teams throw up their hands at an 'impossible' task. And then you deliver, ahead of expectations on both time to deliver and budget costs.

Hm.

matchingSub is Comonadic (obviously!)

So!

Today’s 1HaskellADay problem was an interesting NP-hard problem ... until I reread the problem statement carefully, then it became trivial. ‘Consecutive’ is the keyword here that unlocked the puzzle for me, eventually.

The heart of the algorithm here is simple enough. It says, in words, ‘are these next n numbers in the list the sum specified?’ If they are, return them as a solution, if they are greater, return nothing, if they are less than the sum, keep trying.

Those are the words, here is the implementation:

inquiry :: Int -> Int -> DList Int -> [Int] -> [Int]

inquiry _ _ _ [] = []

inquiry goal sub accum (next : rest) =

   let tote = sub + next

       naccum = accum << next

   in  case (compare tote goal) of

          LT -> inquiry goal tote naccum rest

          EQ -> dlToList naccum

          GT -> []

Simple enough, and I use a difference list as an accumulator, just because that’s how I roll (and the fact, too, that difference lists append an element in constant time is sweet!)

So, now all we need to do is move an index over the list to test each possible scenario.

Enter the (Comonad) Dragon

Of course, iterating over a list, keeping the context of the list itself active can be done functionally in many ways, but what suggested itself to me right away was the Comonad.

The Comonad of the list is the list itself and all of its tails, and this is exactly the paradigm we need to solve this problem simply, so, writing matchingSub became simply a comonadic extension:

matchingSub’ :: Int -> [Int] -> [[Int]]

matchingSub’ goal domain =

   domain =>> inquiry goal 0 emptyDL

Now, this doesn’t quite give the requested solution sets for the given examples, as it returns the empty list as ‘no solution,’ not ‘nothing at all’ as requested, but filtering out the empty list is easy enough: we just need a predicate to test if the list is not empty and then return only the lists of answers:

isCons :: [a] -> Bool

isCons [] = False

isCons _ = True

matchingSub :: Int -> [Int] -> [[Int]]

matchingSub goal = filter isCons . matchingSub’ goal

And there we have it!

I like comonads. They’re sweet!

Okay, prove it, buster!

(Who is this 'buster'-person, by the way, and why is he always having to prove things?)

All the above code is in Haskell programming, but it is also mutually-translatable to and from Idris. Nearly the same syntax (intentionally so), and nearly the same semantics (Idris's eager evalution looks and tastes very much like Haskell's normal order evaluation).

In Haskell, we'd hand-verify the above with the provided samples and we're done. We'd run it through quickcheck to be done-done.

In Idris, we can prove that what we specified is actually (heh: 'actually') correct in its implementation.

So, let's prove it.

prvSample : (expected : List (List Int)) 

            -> (actual : List (List Int))

            -> (so (expected == actual)) -> ()

prvSample expected actual pred = ()

Using the 'so' assertion, we're (almost) done.

Let's run our sample-set through our prover, such that it is:

sample1 : ()

sample1 = (prvSample [[1..4]]

                     (matchingSub 10 [1..5])) oh

sample2 : ()

sample2 = (prvSample [[1,1], [1,1]] 

                     (matchingSub 2 $ replicate 3 1)) oh

sample3 : ()

sample3 = (prvSample [[1,1], [1,1]]

                     (take 2 $ matchingSub 2 $ repeat 1)) oh

Code compiles? Yes? We're done: we've delivered functionality as specified.

Sweet!

'W' is for It's My BIRTHDAY today! ... and Comonads

'W' is for 'Whaaaaat...?' (Comonads) ... and 'W' is for 'It's my birthday today! YAY!'

That's actually a 'Y' in 'YAY,' but when you string two Y's together: YY, you get something that looks like a W ... or two martini glasses next to each other, husband and wife, take your pick.

And 'Wife' starts with the letter 'W,' so there you go!

Wife, n: ORIGIN Old English wīf [woman,] of Germanic origin; related to Dutch wijf and German Weib.

All very ... Vikingescque. 

... In a good way.

So, 'W' is for 'It's my party and I'll cry if I want to, cry if I want to, cry if I want to! You would cry, too, if this happened to you. Da-da-da-da-da-dat!' (youtube vid)

But I don't feel like crying at all! I (ain't) happy, I'm feeling glad, I've got sunshine, in a bag, I'm useless, but not for long, my future is coming on! [Gorillaz cartoon clip] 

So, yeah, that.

Okay, so to the (mathematical) topic. Why do I say 'W' is for comonad? And what is a comonad, anyway, and what is the meaning of life, the universe, and everything?

That last one is a piece of cake:

42.

I'm so glad Deep Thought covered that ground for me. Otherwise I would have looked like I didn't have the answer to something, and would've had to have made something up to assuage the masses!

Like ketchup!

But anyway, why are we even having a blog-post day for the letter 'W,' when, after all, it's as plain as day that there's no such thing as the letter 'W'! I mean, 'double'-'u' it's two 'v's together, and even 'v' is a constructed thing from 'u,' (in the Greek there is no 'v,' they use 'β' so it's Blad, the impaler), so 'v' and 'w,' today and yesterday, are silly posts for silly days for letters that don't even exist!

AND it's my birthday today, and did I get cake? Huh? Did I? Huh? Or am I here, all alone, writing this blog entry about the non-extant letter 'W' and comonads? Huh? Huh? I ask you!

(Cue entry of my daughter, EM, baring gifts of gold, frankincense and cake.)

Ooh! Cake! What flavor is that?

EM: Dark chocolate mousse.

Ooh! My favorite!

Excuse me a moment whilst I indulge after much being-sung-Happy-Birthday-to.

(nom-nom-nom!)

Okay, I'm back.

Okay. 

W. 

Comonads.

Okay, geophf, how in the world does 'W' have anything to do with Comonads?

Okay, so Comonads are the dual to monads, and, in the literature, the monadic types are represented by 'm' and monadic functions are prefixed with a little-m or suffixed by a capital-M (depending on their mode of use:

msum :: Monad m, Num a => [m a] -> m a

liftM :: Monad m => (a -> r) -> m a -> m r

mapM_ :: Monad m => (a -> m b) -> [a] -> m ()

You see how that works? m-functions work with monads, simplifying them, whereas function-Ms work with non-monad forms, putting them into the monadic domain), complexifying simpler objects.

So that explains the 'M' for monads ...

... although there is the whole question lingering as to why they are even called 'monads' (one thing) as they are the triple:

(M, μ, η) where:

M is the monadic type,

μ is the join-function such that join :: Monad m => m (m a) -> m a; and,

η is the unit-function such that unit :: Monad m => a -> m a

(the unit-function, in Haskell, is known as the return-function)

Monads from mathematics were originally called 'triples,' because that's what they are, monads from philosophy mean something else entirely, so occasionally we get a logician in the mathematics forum asking what the hell we're all taking about!

So, 'monads' (misnamed) are represented by 'm' for their type-families.

So, comonads (mis-co-named) are monads' duals, so their type-families are represented by the inverted symbol of monads, comonads have the type-variable: w.

Get it? Got it? Good!

Now, I could go all 'w' is 'ω' and say that it represents Ohm, and Ohm's laws, ...

but then this post would be all chanting:

Ohm, Ohm, Ohm, Ohm, Ohm, Ohm, Ohm, ... (youtube link)

And there's something in that for some, I suppose, but not here nor now.

Here and now we're talking about the comonad.

The Comonad is the dual of the monad, so it is a co-triple of the form:

(W, δ, ε) where:

W is the Comonadic type

δ is the duplicate-function such that duplicate :: Comonad w => w a -> w (w a); and,

ε is the extract-function such that extract :: Comonad w => w a -> a

For monads, you can only push 'plain-old' objects up into the monadic domain and once there, you never leave it. You can't get an object out of a monads.

For comonads, you can only extract 'plain-old' objects from the comonadic context, and once extracted, it's free of the comonad. You can't make comonads from plain-old objects.

For monads, they have join and monadic-bind, stringing together operations in the monadic domain:

(>>=) :: Monad m => m a -> (a -> m b) -> m b

m >>= f = join . fmap f

(given that the monad is a functor, as well)

For comonads, they have duplicate and comonadic-extention, extending the comonadic context over the computation:

(=>>) :: Comonad w => w a -> (w a -> b) -> w b

w =>> f = fmap f . duplicate

(again, when the comonad is a functor as well)

So, like, Monads and comonads are, so, like, totes the opposite.

Dude. (The Dude Abides)

For me, personally, I didn't 'get' comonads for a long, long time. What was the point of them? I wondered, but now I see them everywhere.

The object-model of object orientation is not so well-understood as the categorical representation of functional programming, but one approach is the Ω-calculus.

That's one way of seeing OOP. I see it, perhaps in the same way, but, I don't think so. I see object-orientation with inheritance from the Art of the MetaObject Protocol, and from that perspective, objects and inheritance are totally comonadic. You have the computational context of the parent class and you extend that to your child class (or your child class extends the computational context).

Totally comonadic.

For-loops, modeled by folds, yes, but these are also an entirely comonadic thing. You're extending the context of your loop over the life of your computation.

Comonads are everywhere!

... except not maybe so much in if-then-else ... monads fit that so much more naturally, or a transformation on the Either type.

Either way.

Comonads. Don't worry about it if you heard about them but you just don't get them. I was there for years. Just keep doing what you're doing, 'normal' functional programming, and you're way ahead of the game. Monads and applicative functors? Go to town! Arrows? You rock.

But, for me, one day it came to the point that I was monad-ing myself to death, and I wondered, 'is there a better way?'

And then that's when I looked at comonads, again.

So, where do I use them now? and for what? and how?

The 'how' is so trivial it's really pointless to go over them. Most people, for this very reason, look at comonads, and say, 'yeah, but ... that's the map-function, right?' and eh-onto other things.

Kind of like how monads should be used.

"Eh, but that's a function, right?" and eh-move onto your next task.

But monads are so novel for most people, that we're still in the honeymoon phase, and we will be there, for, oh, another fifty years or so (it will take that long for the very idea to be introduced and then absorbed into the mainstream programming culture).

But until that time, there'll be this love-affair with monads, with the dual-neglect of comonads (note that on the wikipedia page, comonads are a footnote to monads. This dismissive treatment of comonads is not uncommon). Sigh.

I use comonads to look at things in other ways.

Say I have this list-of-lists:

Date,Open,High,Low,Close,Volume,Adj Close

[[2011-03-30,64.56,64.86,63.50,63.96,1554600,63.76],

[2011-03-29,63.51,64.26,62.80,64.13,2336800,63.93],

[2011-03-28,63.06,64.33,62.47,62.70,1410900,62.50],

[2011-03-25,62.74,63.77,61.91,62.65,2171800,62.46],

[2011-03-24,62.52,62.99,59.75,62.63,5398500,62.44], ... etc.

And instead of that raw data, I wish to observe some trends in it:

Date,Open,High,Low,Close,Volume,Adj Close,sma 15,ema 12, ema 26, accum_over_distr,adx 20

[[2011-03-30,$64.56,$64.86,$63.50,$63.96,1554600,$63.76,63.96,62.509083019265475,62.37404736199129,-502958.8235294094,65.70247372791911],

[2011-03-29,$63.51,$64.26,$62.80,$64.13,2336800,$63.93,64.13,62.18995668453236,62.18995668453236,1920657.5342465467,72.12083595494798],

[2011-03-28,$63.06,$64.33,$62.47,$62.70,1410900,$62.50,62.7,61.88254869299201,61.88254869299201,-1061967.7419354776,77.72261629109732],

[2011-03-25,$62.74,$63.77,$61.91,$62.65,2171800,$62.46,62.65,61.81630406119281,61.81630406119281,-443701.07526881865,73.52367287149414],

[2011-03-24,$62.52,$62.99,$59.75,$62.63,5398500,$62.44,62.63,61.73466415405274,61.73466415405274,4198833.333333336,100.0], ... etc

Comonads allow me to do this quite simply by using a little, simple technique called regression:

> regression :: ([Row] -> a) -> [Row] -> [a] -- your classic comonad

> regression f rows = rows =>> f 

That takes a formula, in this case an indicator, such as the SMA (simple moving average) or the EMA (exponential, or weighted, moving average), and scanning the entire screen, giving the result for each row, returning the entire screen to you, again, but now enhanced by the comonadic function applied throughout the screen.

That's what a comonad is. You have this whole big thing, like a stock-screen of GMCR ('Green Mountain Coffee Reserves'), and the comonad takes the entire thing to operate on, and gives the result an unit (or a row) at a time.

Comonads are perfectly-fitted to the uses for which I intend them, now that I see them, finally, and know what they are and how to use them. I have this big old thing. I want to see it in a different way, and I know what result I want piece-by-piece, but, unlike for monads, that deal piecewise-at-a-time, comonad gives you the entire scope of the computational context, so if you need the previous row, for example, you have it and every other row in the history.

'W' is for Comonad. Don't worry if you don't 'get' them. They are there. They'll wait for you.

It's just that when you do start using them, you'll see their usefulness in a lot more places that you had heretofore neglected to use them, and you'll find, going forward, your work is cleaner and simpler because of them.

Abstract Nonsense, chapter 1: the List

Abstract Nonsense: Rambling thoughts of a Category Theorist

Synopsis: Looking at things through the lens of category theory, where 'things' may be anything from writing a good (a really, awesomely good) piece of code to ... well, what else is there in this life?

Chapter 1: the List

We consider the list: to monad or not to monad.

We consider the monad: to monad or to comonad, and, if we consider the monad, shall we consider the monoidal implications that monad lends itself it to?

A monad is not intrinsically monoidal, but, then again, the monad and the comonad are not intrinsically functors, but thinking of monads and comonads and thinking of them not as functors is a blocker for me ... it gives me a bit of a headache, thinking of a monad (the triple (T, mu (or 'join'), eta (or 'unit')). I mean, it is simple to think of monads as monads only when considering the join function, but what is the point of eta if you are not thinking of the monad in terms of a functor?

So I do not consider the monad, or the comonad (W, epsilon (or extract), delta (or duplicate)) (definition from "Introduction to Higher-Order Categorical Logic), http://books.google.com/books?isbn=0521356539, as being independently or intrinsically defined from the functor, Fa, as, after all unit and extract are functorable.

Okay. So we consider lists. We can consider lists free of the monadic and comonadic implications, because, after all, a list is simply a structure, and can be viewed as tree-like structure, where we define 

data list a = nil | (a, list a) 

we see that, firstly list is monoidal on a where mzero = nil and mappend is easily defined as append or (++).

So, anywhere along the list, one can grab the pair, and the tree falls out of the structure:

(a, |->) -> (b, |->) -> nil

The pairwise operators, fst and snd, are head and tail on list a, and the fundamental constructor of the list is cons, where cons :: a -> list a -> list a

(which looks like a continuation, now that I look at it, OMG!)

(The continuation monad is the 'mother of all monads', and the continuation is the 'mother of all function calls,' perhaps?)

from cons, mappend is simply defined:

nil ++ b = b

  a ++ b = cons (head a) (tail a ++ b)

             

Since list a is functor a (leaving aside nil) we have fmap for lists, too:

fmap f nil = nil

fmap f (head:tail) = cons (f head) (fmap f tail)

as you can see, list definitions lend themselves naturally to induction.

Okay. Lists qua lists (of course, as monoids and functors) are very easily defined in just a few lines of code in any programming language with any heft (I've demonstrated Haskell here, the definitions are similar in Java once monoid and functor are properly established as types. This requires that Arrows and functors be defined, but that is not part of the scope of this article ... it's hard, but doable).

Monadic Lists

Now let's consider the case of lists as monads.

First, monad:

class Monad m where

    return :: a -> m a

    join :: m (m a) -> m a

That definition is unusual in the programming community, but not to a categorist. Programmers are used to the more applicative definition of monad:

class MonadForProgrammersButNotForMeTheCategorist m where

    return :: a -> m a

    m >>= f :: m a -> (a -> m b) -> m b

The issue with defining monads in terms of bind (>>=) is that sometimes wrapping your head around what bind should be for a particular monad can be tricky (sometimes it isn't, but sometimes it is), but if one knows what join is for a monad, and, if that monad is a functor, then we have a very simple, and a very general, definition of bind:

bind m f = join . fmap f

proof

bind is defined as above

bind (m a) f = (join . fmap f) (m a) = m b (supposition)

                 = (join . fmap (a -> m b)) (m a)

                 = (join . (m a -> m (m b))) (m a)

                 = (join (m (m b)) = m b

Q.E.D.

So, given that we have join and fmap defined for a monad, bind falls out easily from their composition, and that's why I declare monads as per category theory, as being the triple of the monadic type, the unit function (in Haskell, it's called 'return') and the join function.

Now, the monadic aspect of list a is simply this:

instance Monad list where

  return a = [a]

  join [] = []

  join (head:tail) = head ++ join tail (where head and tail are (monadic) lists)

... or join for list [a,b,c] is a ++ b ++ c.

And thus we have have monadic lists defined and may therefor use lists monadically, e.g.:

[1,2,3] >>= return . succ = [2,3,4]

and, even better:

[1,null, 3] >>= return . succ = [2,4]

It. Just. Works.

(side note: it really works in Haskell, as, after all, 'null' is not a number so the list [1,null, 3] does not exist in Haskell.

In Java, null very much exists, but if we make monadic list construction dependent on the monadicity of the units then the lifting function (which we will cover later) from a 'plain' list to the monadic list gets us into the a good position already:

return [1,null, 3] = [1,3] (monadic)

And if we don't do that, then the binding operation will use the Maybe type to guarantee the safety of the operation:

[1,null,3] >>= return . succ == succ (Just 1) : succ (Nothing) : succ (Just 3) = [2, 4]

end side note.)

Comonadic Lists

Now that we have monadic lists defined, let's define comonad lists.

Why? Because whereas with monads we have bind, which lends itself nicely to each element of lists, with comonads we have extend which also extends itself very nicely to operations on lists as a whole, iteratively reductively.

So, a comonad is

class Comonad w where

    extract :: w a -> a

    duplicate :: w a -> w (w a)

Again, instead of making extend intrinsic to the definition of comonads, I chose, instead, the mathematical definition, again, using duplicate.

Again, for gainful reasons, because extend can be defined in terms of duplicate:

extend :: w a -> (w a -> b) -> w b

Or: 

extend f (w a) = (fmap f . duplicate) (w a) = w b (supposition)

proof:

extend f (w a) = (fmap f . duplicate) (w a)

                     = (fmap (w a -> b) . duplicate) (w a)

                     = ((w (w a) -> w b) . duplicate) (w a)

                     = ((w (w a) -> w b) (w (w a))

                     = w b

Q.E.D.

So for lists:

instance Comonad list where

    extract [] = doesn't happen. Really

    extract (head:_) = head

    duplicate [] = []

    duplicate list@(_:tail) = list : (duplicate tail)

... and we're done.

So, if we have the basic list type defined as (a, list a) or nil

Then we convert to mlist (monadic list) or wlist (comonadic list) by defining nil for each of the particular types and then just adding elements (with cons) to each of those container types:

asMonad [] = m[]

asMonad (h:t) = h m: asMonad t

asComonad [] = w[]

asComonad (h:t) = h w: asComonad t

and in the derived times

asMonad mlist = mlist

asComonad wlist = wlist

Piece of cake.

Or.

Is.

It?

Constructing Lists: Lists as Streams.

The 'problem' of these functional list types is that they look more like Stacks than Queue, so we can interact very easily with the most recent element and cdr down through the list in an orderly fashion, but if we have a preexisting list of one type and wish to view it from a different aspect, not only do we have to build it iteratively, but we have to make sure that iterative build is not penalized (linearly) for each insert at the end of the list (which turns out to be an exponential punishment).

How do we do this?

Lists are functions in a functional aspect.

So, the problem commonly faced by users of them in the functional domain is that when one has to construct a large one iteratively, one faces the problem of continuously appending the next element to the end of the list, and since naïve append is O(N) time (linear), then doing that, iteratively incurs a near O(N*N) time cost.

(side note: the cost is actually O(N*(N-1)/2) time)

What can we do about that?

Simple, actually, if you come from a Prolog programming background, just use difference lists.

A difference list is a list representation of a pair of lists, one list representing the whole and one representing a part of the this:

data dlist a = DL { realize :: list a -> list a }

In Prolog, logic variables are used to provide the (declarative) representation (and consequently, the implementation):

List = [1,2,3|L] - L

Since we have L and L is a part of the whole list, we have a reference into a latter part of the list that in standard list representations we do not. Further, as L can be anything, it can even be the 'end' of the list, and so 'prepending' onto L allows us, by consequence (actually: 'by accident') to 'postpend' onto the list we're working with.

We saw how to represent difference lists using unification and logic variables in Prolog. How do we represent difference lists functionally?

It comes down to the fundamental function of lists, cons:

cons :: a -> list a -> list a

that is, if we give cons an element and a list we get a cons'ed list in return.

What happens if we don't give cons the list to cons to, but instead, we defer it? We then get the partial or curried function:

(cons x) :: list a -> list a

Which is no different than before.

Or.

Is.

It?

Well, recall that a difference list is the difference of two lists. Look at the signature of (cons x) above and what do we have? We have a function that, when given a list, returns a list.

What is a difference list again? A think that, when given a list, gives the full list back.

(cons x), that is: the curried cons function, and the difference list type can be viewed as the same thing, and from that we have our difference list definition (of the realize function):

realize = cons x

So, given realize, we can define prepend and postpend operations:

prepend :: a -> dlist a -> dlist a

prepend x dl = DL { cons x . realize dl }

x |> dl = prepend x dl

postpend :: a -> dlist a -> dlist a

postpend x dl = DL { realize dl . cons x }

dl <| x = postpend x dl

So what? Well, for prepend, there's no big deal, the operation occurs in constant time, but so does cons for (regular) lists. But for postpend, the operation takes the same constant time, but for regular lists, if we were to define postpend in the regular fashion:

postpend :: a -> list a -> list a

postpend a list = list ++ [a]

we would be traversing to the tail of the list each time to append the new element, and that traversal incurs a linear-time cost. Upshot: postpend for regular lists has an O(n) cost, but for difference lists, it occurs in constant time.

And that's the payoff, if you are working with a large list from an external source and need to enlistify it in an order-preserving fashion, doing so with a regular list would incur an exponential cost (nearly O(N*N)) but using difference lists has a logarithmic flattening effect (O(2N)).

Using difference lists saved my bacon on a project where I did a scan-then-process operation on a framework that processes large documents.

Back to Java.

One way to convert from one representation of lists to another is to rebuild the list in the new type. Unfortunately, Java doesn't have the linear construct

mlist [] = m[]

mlist (h:t) = h m: mlist t

So what it does is iteratively build the new list with mappend (as lists are monoidal).

Well, using the O(N) mappend in an iterative fashion incurs an exponential-time cost for list-revisualization.

So, I've replaced my fromCollection() methods in Java from:

public static <L> L fromCollection(Collection coll, L basis) {

  L ans = basis.mzero();

  for(T elt : coll) {

    ans = ans.mappend(basis.singleton(elt)); // exponential cost

  }

  return ans;

}

to be:

public static <L> L fromCollection(Collection coll, L basis) {

   DifferenceList ans = DifferenceList.nil(basis);

   for(T elt : coll) {

      ans = ans.postpend(elt); // constant time cost

   }

   return ans.realizeFrom(basis);

}

so list construction that was at a cost of exponential time now become linear time, as it should be.

This way, I can work with a list either monadically or comonadically and pay only a linear cost when I change my (aspect) perspective on the list.

CoReader x CoState == Silver Bullet

Thesis:

The title reads: 'CoReader x CoState == Silver Bullet' ... of course, it isn't a silver bullet, but it surely reduces (exponential) complexity AND provides just-in-time realized constants that (e.g.) would, and do, strain and break production systems working on very large data sets.

So, it isn't a silver bullet, but it sure-as-heavens-to-betsy puts the 'oh, I'll just generate the (resource intensive) constant' approach and then 'oh, I just wrap each layer in another layer of if-then-else (kill me with code complexity)' approach up and down walls and mops them off the floor, please, and thank you.

Antithesis:

Okay, so the CoReader (co)monad is suppose to give you a constant, and it does ...

CoReader readValue context = (context, readValue) -> context

with the askC function:

askC :: (CoReader r c) -> r

and so you have your constant.

The thing is, the CoReader depends on the context to be preexisting, which can be troublesome for data that are realized from an environment that is established at some point after the program begins to run, and that problem is that if you want a realized constant, you can't have the CoReader be a final value in some program component (the context isn't there yet), and then, if you wait to establish the CoReader until after the data set is realized, then you have all this checking code and establishment code, that can be rerun at any time (and, most likely, every time) you ask for that constant, which means that you don't have a constant at all, but a new value every time you ask over a data stream.

Sub-optimal.

So, how does one get a realized constant from a data stream that takes time to establish and guarantee that, yes, that constant I asked for upstream or in another branch is the same constant that I'm getting now from my CoReader, because I'm not re-creating it each time I ask for a constant from the data stream I get after the program is started and initialized?

... e.g. (or, 'i.e.' in my particular case): a database connection takes time, and is usually not available with a system that needs a CoReader to be constant from the get-go.

My solution, after much head-banging with trying to make the CoReader, itself, be something that it isn't, is to have the CoReader not read the stream directly, because it may not be there or be ready, but to have the CoReader read a different 'stream' entirely: the State monad ...

Or actually, since I don't want to push all my computations thereafter up into the monadic domain, to use the CoState comonad, a.k.a. the Context comonad:

Context context value = Context (context -> value) context

with the very helpful putC function:

putC :: Context (context -> value) context -> newValue -> Context (context -> newValue) context

You're probably scratching your head, saying, "I don't see any putC in the literature..."

And, sure, you are correct, there's 'experiment' and 'modify' but then you see where I'm going ... a little this plus that gets you to putC and that's what we want from our CoState comonad: I'm in a context, gimme the thing I stowed away in there for later use without me having to thread all the baggage of a monad throughout my computation.

You wrap that in a CoReader and then you have the constifying functionality you need to say, hey, once the state is establish, then give me that constant value from then on.

So, given a data stream, context, that comes to us somewhere down the road, we have a CoState comonad, which I'll call box (for a mutable boxed type indexing into that stream, or 'context'), paired with the CoReader, reader, to give you a constant value in the pure-functional (not monadic) domain.

That's half of it.

The other half is this: now that you've got CoState paired with CoReader, you, functionally, know that this is the first read into the context, or if this the nth read where you're just returning the read/realized value.

So, what if you want to do something the first time, that you don't want to do anytime thereafter.

AND, what if you don't wish to encumber yourself with the old

if this-is-the-first-time-i'm-reading-and-initializing-this-stupid-constant
then do-something-special-here
else just-return-the-stupid-constant

logic that, well, encumbers too much programming logic everywhere?

The answer is surprisingly easy, once you have the CoState x CoReader pairing ...

With a little bit of monadic magic to provide the glue.

Because, the first time you read the constant, or, that is to say, just before the first time the constant value is ground to what (it is just about to) be(come), it's value is ... wait for it ...

Nothing.

As in Nothing :: Maybe.

That is, if you lift that (non)value into the monadic domain:

uninitializedValue = Nothing
value x = Just x

And, boom! You use mplus (or (+)) to do something magical the first time:

val (+) magical-initialization-code

equals your solution with dispensing with stupid boolean flags called 'inited' and stupid if-then-else tests everywhere that are now totally unnecessary, ... just redefine askC:

askC reader = realAskC reader (+) magical-initialization-code

and then you just ask for the constant, the reader gives it to you, in the pure-functional domain, and automagically does initialization code only on the first read of that constant.

Synthesis:

Real-world example.

"Yeah, geophf," you're saying, "nice whitepaper, but what can I use it for?"

Um, impress hot babes at cocktail parties?

Get a free 'tall' latte at sbux, ... that is, after you pass over a fiver?

(Okay, seriously, 5 bucks for a small coffee? What has the world come to?)

AND:

So, let's say you're working on one of the world's largest databases (every company claims to have at least one of them ...), and you're getting 10,000 records per hour, and one section is generating up to 5 indices, but you don't know which indices you need, and which you don't, as it depends on data down-stream, and since these records are highly hierarchical XML files, with each of the layers of the hierarchy optional, we're talking WAY down stream.

So, one approach, you just getSequence from the database for all the sequences you may need, and then you're good, you insert rows with the prepopulated sequence.

Hm, 10000 records per hour, 24x7 data feed, and int is how big? 2 billion ... only?

(start-rant: Okay, does EACH AND EVERY TEAM have to relearn that you exhaust int much sooner than expected so that your 'vital system' crashes with dev and production teams working round the clock to change int into a much bigger number, when, after all, these are sequences, not (necessarily) numbers (GUID are hexa-strings-of-numerals, so why not make your precious sequence strings that you will NEVER do arithmetic on anyway, so you've set it as an int, why? :end-rant)

So, from a purely optional data input, you are probably generating all these sequences, and bringing your project to a screeching halt much sooner.

How about this.

Wrap your sequence generator in a CoReader comonad, and wrap each optional insert in the Maybe monad.

What does this give you?

In a hierarchy, it give you that you don't create a sequence you don't use, ever.

And, five levels down, when you actually do do an insert of a child record who's parent wasn't there in the data feed? It 'automagically' generates the parent record from the dataflow trace, inserts that parent first, and then inserts your child record without throwing an 'integrity violation, parent not found' error, and since it's done in the monadic domain, you wrote 0, zero, zip, nada conditional code at each later.

> return layer1 (+) deferInsert1 >>= \deferred1 -> insertm (reader1 askC) [] >>
> return layer2 (+) deferInsert2 >>= \deferred2 -> insertm (reader2 askC) [deferred1] >>

etc, etc, to your heart's content.

Which is a very different thing than:

let seq1 = getSequence
    seq2 = getSequence
    seq3 = getSequence
...
in do val1 <- return layer1
        val2 <- return layer2
        val3 <- return layer3
...
        insertm seq1 val1
        insertm seq2 val2
        insertm seq3 val3
...

This example trivializes things a bit. Looking at it, it's obvious you want to defer the creation of the sequence until you know you have that row to insert into your database. Unfortunately, it is that obvious, and we intend to create thing only when needed, but then the 'real world' rears it's ugly head, and you're looking at a branching data flow where your sequence may be needed downstream if any of the branches result in an insert, and your tree is not binary, but nary, and several layers deep.

What do you do as a programmer?

Well, you just create the sequence, because you know you're going to use, because your test data says so, but the real stream is never that dogmatic and a whole lot sparser than your 'in-a-perfect-world' test cases anticipated.

And you have hundreds of tables, ... and just one of the tables has 100 million records added to it, each month.

Do you see where 'just create the sequence' can be a key factor in crippling your application soon after it goes live?

'Just create the sequence, because for each layer, a layer of complexity is added to this already complex system,' is one approach, and in industry, pretty much the standard approach.

I propose another way; in sum: the way proposed in this paper. Use the CoState x CoReader comonadic pairing to take all the complexity, put it into a paper bag, and then throw that bag into a black hole where you'll never see it again. If your data set is rife with optionality, that is: semideterminism, then wrap that semideterminism in a Maybe monad, and you have a powerful framework that is simple to understand and easy to use.

In a DBMS system I'm working on, the SLOC (lines of code) count decreased, AND the number of sequences generated decreased by a factor of 2-4. We were generating twice to four times as many sequences that we needed, ... per input record. With the CoState x CoReader x Maybe framework in place, this spurious sequence generation stopped, and the code became more declarative: I was saying what was to be done, much more so than how to go about doing it.