Why Kleisli Arrows Matter

We're going to take a departure from the style of articles regularly written about the Kleisli category, because, firstly, there aren't articles regularly written about the Kleisli category.

That's a loss for the world. Why? I find the Kleisli category so useful that I'm normally programming in the category, and, conversely, I find most code in industry, unaware of this category, is doing a lot of the work of (unintentionally) setting up this category, only to tear it down before using it effectively.

So. What is the Kleisli Category? Before we can properly talk about this category, and its applications, we need to talk about monads. 

Monads

A monad, as you can see by following the above link, is a domain with some specific, useful properties. If we have a monad, T, we know it comes with an unit function, η, and a join function, μ. What do these 'thingies' do?

• T, the monadic domain, says that if you are the domain, then that's where you stay: T: T → T.

"So what?" you ask. The beauty of this is that once you've proved you're in a domain, then all computations from that point are guaranteed to be in that domain.

So, for example, if you have a monadic domain called Maybe, then you know that values in this domain are Just some defined value or Nothing. What about null? There is no null in the Maybe-domain, so you never have to prove your value is (or isn't) null, once you're in that monadic domain.

• But how do you prove you're in that domain? η lifts an unit value (or a 'plain old' value) from the ('plain old') domain into the monadic domain. You've just proved you're in the monadic domain, simply by applying η.

η null → fails

η some value → some value in T.

• We're going to talk about the join-function, μ, after we define the Kleisli category.

The Kleisli Category

Okay. Monads. Great. So what does have to do with the Kleisli category? There's a problem with the above description of Monads that I didn't address. You can take any function, say:

f : A → B

and lift that into the monadic domain:

f^T : T A → T B

... but what is f^T? f^T looks exactly like f, when you apply elimination of the monadic domain, T. How can we prove or 'know' that anywhere in our computation we indeed end up in the monadic domain, so that the next step in the computation we know we are in that monadic domain, and we don't have to go all the way back to the beginning of the proof to verify this, every time?

Simple: that's what the Kleisli category does for us.

What does the Kleisli category do for us? Kleisli defines the Kleisli arrow thusly:

f^K : A → T B

That is to say, no matter where we start from in our (possibly interim) computation, we end our computation in the monadic domain. This is fantastic! Because now we no longer need to search back any farther than this function to see (that is: to prove) that we are in the monadic domain, and, with that guarantee, we can proceed in the safety of that domain, not having to frontload any nor every computation that follows with preconditions that would be required outside that monadic domain.

null-check simply vanishes in monadic domains that do not allow that (non-)value.

Incidentally, here's an oxymoron: 'NullPointerException' in a language that doesn't have pointers.

Here's another oxymoron: 'null value,' when 'null' means there is no value (of that specified type, or, any type, for that matter). null breaks type-safety, but I get ahead of myself.

Back on point.

So, okay: great. We, using the Kleisli arrows, know at every point in that computation that we are in the monadic domain, T, and can chain computations safely in that domain.

But, wait. There's a glaring issue here. Sure, f^K gets us into the monadic domain, but let's chain the computation. Let's say we have:

g^K : B → T C

... and we wish to chain, or, functionally: compose f^K and g^K? We get this:

g^K ∘ f^K ⇒ A → T B → TT C

Whoops! We're no longer in the monadic domain T, but at the end of the chained-computation, we're in the monadic domain TT, and what, even, is that? I'm not going to answer that question, because 1) who cares? because 2) where we really want to be is in the domain T, so the real question is: how do we get rid of that extra T in the monadic domain TT and get back into the less-cumbersome monadic domain we understand, T?

• That's where the join-function, μ, comes in.

μ : TT A → T A

The join-function, μ, of a monad, T, states that when you join a monad of type T to a monad of that same type, the result, TT, when joined, simplifies to that (original) monad, T.

It's as simple as that.

But, then, it's even simpler than that, as the Kleisli arrow anticipates that you're starting in a monadic domain and wish to end up in that domain, so the Kleisli arrow entails the join function, μ, 'automagically.' With that understanding, we rewrite standard functional composition to composition under the Kleisli category:

g^K ∘^K f^K ⇒ A → T B → T C

Which means we can now compose as many Kleisli arrows as we like, and anywhere we are in that compositional-chain, we know we are in our good ole' safe, guaranteed monadic domain.

Practical Application

We've heard of the Maybe monad, which entails semi-determinism, this monad is now part of the core Java language as the Optional-type, with practical application in functional mapping, filtering and finding, as well as interactions with data-stores (e.g.: databases).

Boy, I wish I had that back in the 1990's, developing the Sales Comparison Approach ingest process of mortgage appraisal forms for Fannie Mae. I didn't. I had Java 1.1. A glaring 'problem' we had to address with ingesting mortgage appraisals what that every single field is optional, and, as (sub-)sections depend on prior fields, entire subsections of the mortgage appraisal form were dependently-optional. The solution the engineering team at that time took was to store every field of every row of the 2000 fields of the mortgage appraisal form.

Fannie Mae deals with millions of mortgage appraisals

Each.

Year.

Having rows upon rows (upon rows upon rows) of data tables of null values quickly overloaded database management systems (at that time, and, I would argue, is tremendously wasteful, even today).

My solution was this, as each field is optional, I lifted that value into the monadic domain, that way, when a value was present, follow-on computations, for follow-on (sub-)sections would execute, and, as the process of lifting failed on a null-value, follow-on computations were automagically skipped for absent values. Only values present were stored. Only computations on present values were performed. The Sales Comparison Approach had over 600 fields, all of them optional, many of them dependently-optional, and only the values present in those 600 fields were stored. The savings in data storage was exponentially more efficient for the Sales Comparison Approach section as compared to the storage for the rest of the mortgage appraisal.

Although easy enough, and intuitive, to say, actually implementing Kleisli Arrows in Java 1.1 (the langua fraca for that project) required I first implement the concept of both Function and Functor, using inner classes, then I needed to implement the concept of Monad, then Maybe, then, with monad, I needed to implement the Kleisli Arrow monadic-bind function to be able to stitch together dozens and hundreds of computations together, without one single explicit null-check.

The data told me if they were present, or not, and, once lifted into the monadic domain, the Kleisli arrows stitched together the entire Sales Comparison Approach section, all 600 computations, into a seamless and concise workflow.

Summary

Kleisli arrows: so useful they are recognized as integral to the modern programming paradigm. What's fascinating about these constructs is that they are grounded in provable mathematical forms, from η to μ to Kleisli-composition. This article summarized the mathematics underpinning the Kleisli category and showed a practical application of this pure mathematical form that translated directly into space-efficient and computationally-concise software delivered into production that is still used to this day.

June 2021 1HaskellADay Problems and Solutions

• Today's #haskell problem: what is 'today' in a data-set. Interesting question. In today's #haskell solution, we build a SQL query, ... WITH HASKELL! 

May 2021 1HaskellADay 1Liners: problems and solutions

• 2021-05-24, Monday:
  Map.partitionWithKey's discriminator is
  p :: k -> a -> Bool
  But I have a function that discriminates only on the key:
  part :: k -> Bool
  write a function that translates my discriminator that can be used by Map.partitionWithKey:
  g :: (k -> Bool) -> (k -> a -> Bool)
  • Social Justice Cleric @noaheasterly:
    g = (const .)
• 2021-05-09, Sunday:
  

  THE SEQUEL!

  Okay, kinda the same, ... but not:

  You have: f :: m a
  You want: g :: b -> m b

  Where g runs f, but accepts an argument, b.
  g drops the result of f (... on the floor? idk)
  g returns the argument b lifted to the domain, m

  GO!

  • Denis Stoyanov Ant @xgrommx:
    g (phantom . pure)
    This is just joke)
  • Social Justice Cleric @noaheasterly: (f $>)
• 2021-05-08, Saturday: two-parter
  1. You have f :: a -> m b
     You want g :: a -> m a

     That is to say: g is a function that returns the input and drops the output of f.

     so:

     blah :: (a -> m b) -> (a -> m a)
  2. What is a gooder name for the blah-function?
  • Jonathan Cast #AJAA #Resist @jonathanccast:
    returnArg = (*>) <$> f <*> return
  • Social Justice Cleric @noaheasterly:
    liftA2 (<*)

April 2021 1HaskellADay 1Liners Problems and Solutions

• 2021-04-20, Tuesday:

  So, I had this problem

  I have pairs :: [(a, IO [b])]

  but I want pairs' :: IO [(a, b)]

  sequence a gives me something like I don't know what: distributing the list monad, not the IO monad. Implement:

  sequence' :: [(a, IO [b])] -> IO [(a, b)]

  • p h z @phaazon_:
    fmap join . traverse (\(a, io) -> fmap (map (a,)) io)
  • lucas卞dicioccio, PhD @lucasdicioccio:

    Just to annoy you I'll use the list-comprehension syntax you dislike.

    solution xs = sequence [fmap (a,) io | (a, io) <- xs]

  • Benkio @benkio89:
    fmap concat . traverse (\(a,iobs) -> fmap (a,) <$> iobs)
  • Social Justice Cleric @noaheasterly
    fmap concat . traverse (getCompose . traverse Compse)
  • Social Justice Cleric @noaheasterly
    fmap (concatMap getCompose) . getCompose . traverse Compose. Compose
  • Basile Henry @basile_henry: Slightly less polymorphic:
    sequence' = traverse @[] (sequence @((,) _) @IO)
  • Basile Henry @basile_henry: I think it's just
    traverse sequence ;)
  • Jérôme Avoustin @JeromeAvoustin: there surely is a shorter version, but I could come up with...
    fmap join . sequence . (fmap . fmap) sequence . fmap sequence
• 2021-04-16, Friday:

  You have a monad, or applicative, and you wish to execute the action of the latter but return the result of the former. The simplest representation for me is:

  pass :: IO a -> b -> IO b

  so:

  return 5 >>= pass (putStrLn "Hi, there!")

  would return IO 5

  GO!

  • D Oisín Kidney @oisdk flip (<$)
  • ⓘ_jack @Iceland_jack ($>)
• 2021-04-12, Monday:

  A function that takes the result of another function then uses that result and the original pair of arguments to compute the result:

  f :: a -> a -> b
  g :: b -> a -> a -> c

  so:

  (\x y -> g (f x y) x y)

  curry away the x and y arguments.

• 2021-04-07, Wednesday:
  you have (Maybe a, Maybe b)
  you want Maybe (a, b)

  If either (Maybe a) or (Maybe b) is Nothing
  then the answer is Nothing.

  If both (Maybe a) and (Maybe b) are (Just ...)
  then the answer is Just (a, b)

  WHAT SAY YOU?

  • Jérôme Avoustin @JeromeAvoustin: bisequence
  • p h z @phaazon_ with base: uncurry $ liftA2 (,)
  • greg nwosu @buddhistfist: (,) <$> ma <*> mb

April 2021 1HaskellADay Problems and Solutions

• 2021-04-28: We build a recommendation-system from spotty data for today's #haskell problem. runRecs rekt the run of the ... rektrun? Bah: today's #haskell solution, with implication to the rescue!  
• 2021-04-26: Today's #haskell problem, on m̸͈̣̈́̉̉̊̈́y̴̢͌̇̕ ̷̡̗͎̰̠͚̓̈́͠B̷̙͋͊̈̕͘Į̷̻̱͔̼̙͖͚̥̄͝R̴͉̖̻̬̗͕͋̽̉̚͝T̵͈̮͙͚̤̘̦̮͐̓́̔̂͑̋̐̐̄H̶̬̳͔͔̳̀̉̇̋͒D̵̢̡̧̦̖̝͖͕͕̤̊Ȃ̷̧̩̼͔̱͙̟̺̕Y̴̡̢̮̘͛̄̽͛̆̃͌ we solve what every Gubmint agency faces every hour of the day: what does this 'TLA' stand for? Today's #haskell solution: Don't mind me. I'm just TLA'ing over here. 
• 2021-04-23: WHO WOULD WIN THIS FIGHT: Ragnarr Loðbrók or Miyamoto Musashi? Today's #haskell problem gives a bean-counter's approach, ... LITERALLY! Today's #haskell solutions shows that the winner of the Viking-Samurai deth-match is: ViewPatterns! ... obviously. 😎
  
  
  
  
  
  
• 2021-04-22: In today's #haskell exercise we try to find the opposite of Kung Fu Fighting, and we fail (because there is no opposite of awesome ... besides fail. GEDDIT?) So we try to find the dual of Kung Fu Fighting. Easy, no? "Your WuShu Praying Mantis-style is strong, but can it match my Tiger Claw-style?" Narrator: "We find out the thrilling conclusion in today's #haskell solution!" 
• 2021-04-14: In today's #haskell exercise we learn it requires 'Expert Timing' to be 'Kung Fu Fighting.' So, we have fighting; we have noodles. We have everything we need for today's #haskell solution. 
  
  
  
• 2021-04-12: For today's #haskell problem we are lifting a "plain" method into the monadic domain ... yes, I'm influenced by @BartoszMilewski writing. Why do you ask? Today's #haskell solution: Function: lifted. 
• 2021-04-09: We get all officious, ... sry: 'OFFICIAL' ... with today's #haskell problem. Today's #haskell solution shows us that you haven't met real evil until your TPS-report cover letter is ... Lorem Ipsum. 
  
  
  
• 2021-04-08, Thursday: In today's #haskell problem we optionally parse a string into some value of some type. Some how. Today's #haskell solution shows us the sum of the numbers in the string was 42 (... no, it wasn't). 
• 2021-04-07, Wednesday: decode vs. eitherDecode from Data.Aeson is today's #haskell exercise. In today's #haskell solution we find that it's nice when eitherDecode tells you why it failed to parse JSON.  
• 2021-04-05, Monday: Today's #haskell exercise is to make a vector that is Foldable and Traversable. Today's #haskell solution gives us Vectors as Foldable and Traversable. YUS! 
• 2021-04-01, Holy Thursday: In today's #haskell exercise we learn the WHOPR beat the Big Mac. We also learn how to make a safe call to an HTTPS endpoint, but that's not important as the WHOPR beating the Big Mac. "Would you like to play a game?" Today's #haskell solution says: "Yes, (safely, please)." 
   

  

  
  
  
  

March 2021 1HaskellADay 1Liners

• 2021-03-23:

  You have [a] and (a -> IO b).

  You want IO [(a, b)]

  That is, you want to pair your inputs to their outputs for further processing in the IO-domain.

  • Chris Martin @chris__martin:

    \as f -> traverse @ [] @ IO (\a -> f a >>= \b ->

    return (a, b)) as

  • cλementd Children crossing @clementd:

    traverse (sequenceA . id &&& f)

    (actually, tranverse (sequence . (id &&& f)))

    Or p traverse (traverse f . dup)

• 2021-03-23: You have

  [([a], [b])]

  You want ([a], [b])

  so: [([1,2], ["hi"]), ([3,4], ["bye"])]

  becomes ([1,2,3,4],["hi","bye"])

  • karakfa @karakfa:

    conc xs = (concatMap fst xs, concatMap snd xs)

March 2021 1HaskellADay Problems and Solutions

• 2021-03-31, Wednesday: Let's go on 50 last dates for today's #haskell problem. Today's #haskell solution shows us the fifty last dates were the fifty best dates. 
  
  
  
• 2021-03-30, Tuesday: Directorizin' ... WITH STYLE! ... is today's #haskell problem. Today's #haskell solution: BEHOLD THE MIGHTY POWER OF THE <*>! 
• 2021-03-29, Monday: Today's #haskell problem tackles plurality and connectives to list the contents of our Fruits Basket. Today's #haskell solution gives us fruits, in the basket, properly-speaking, thanks to George Boole. 
• 2021-03-25, Thursday: Today's #haskell problem has me FORTHing AT THE MOUTH! ... AGAIN! ... no, ... wait ... 
• 2021-03-23, Tuesday: Let's go FORTH! and conquer! for today's #haskell problem. Today's #haskell solution gives us a little FORTHer to go FORTH and FORTH! ... and also demonstrates Gauss' sum formula ... IN FORTH! ... which is nice. 
• 2021-03-22, Monday: Fixing-up and validating a JSON-as-string (and don't get me started) is today's #haskell problem. Today's #haskell solution uses Data.Aeson to transform some JSON, ... typefully. 
• 2021-03-19: pi. Not pie. Not tau. pi... you know, or: close enough, is served as today's #haskell problem (via @AnecdotesMaths). PI! for today's #haskell solution. And a pie recipe from Sumeria, if you're in a baking-mood. 
  
  
  
• 2021-03-18: Today's #haskell problem is to update lookup tables with new values. Today's #haskell solution gets the indices for foo, bar, quux, and ... Joe??? Okay. 
• 2021-03-16: Today's #haskell problem uses natural language processing to consolidate words in the cloud. et, voilà: Grace Hopper wikipedia entry word-cloud, trimmed and stemmed, for today's #haskell solution. 
  
  
  
• 2021-03-15: Today's #haskell problem explores Grace Hopper's wikipedia entry as a word-cloud generated by d3js.org for #WomensHistoryMonth Today's #haskell solution removed some obvious things (punctuation and citations) to simplify Grace Hopper's word-cloud. #WomenHistoryMonth
  
  
  
• 2021-03-11: It's not every Tom, Dick, and Harry that can do today's #haskell exercise...  In today's #haskell solution you want an id? YOU GOT AN ID! 😤 
• 2021-03-09: Let's query a directory and do something with each file in that directory for today's #haskell problem. Today's #haskell solution? THAT WAS EASY! ... so! What are we doing tomorrow? 😃 
• 2021-03-05: Today we're shell-scripting ... WITH HASKELL! 😤  Today's #haskell solution says: "Well, hello there, good lookin'!"  
• 2021-03-04: Today's #haskell problem: you have a time-series of values, not necessary gapless, get the latest value; then, get 'yesterday's' value. Today's #haskell solution gives us some useful functions to navigate a time-series of values. 
• 2021-03-03: Today's #haskell problem asks: "Where in the world are these wineries?" Then answers that question. Ooh! Wineries! Wineries all over the globe! is in today's #haskell solution. 
  
  
  
  
  
  
  
  
  
  
  
  
• 2021-03-02: For today's #haskell problem, let's add approved matched data to wineries in the graph-store. The #haskell solution! ... with a pic! 
  
  
  
• 2021-03-01: Today's #haskell problem approves matched wineries for (eventual) storage. We approve wiki-to-graph winery metaphone matches for today's #haskell solution.