Thu 2 May 2013

In the previous two posts, we've built up a whole range of applicatives, out of Const, Identity, Reader, Compose, Product, Sum, and Fix (and some higher-order analogues). Sum has given us the most trouble, but in some sense has been the most powerful, letting us write things like possibly eventually terminating lists, or trees, or in fact any sort of structure with branching alternatives. In this post, I want to think a bit more about why it is that Sum is the trickiest of the bunch, and more generally, what we can say about when two applicative structures are the "same". In the process of doing so, we'll invent something a lot like Traversable en passant.

Let's do some counting exercises. `Product Identity Identity`

holds exactly two things. It is therefore isomorphic to `((->) Bool)`

, or if we prefer, `((->) Either () ())`

. That is to say that a pair that *holds* two values of type `a`

is the same as a function that *takes a two-valued type* and *yields* a value of type `a`

. A product of more functors in turn is isomorphic to the reader of the sum of each of the datatypes that "represent" them. E.g. `Product (Product Identity Identity) (Product (Const ()) Identity)`

is iso to `((->) (Either (Either () ()) ())`

, i.e. a data type with three possible inhabitants. In making this move we took Product to Either -- multiplication to sum. We can pull a similar trick with Compose. `Compose (Product Identity Identity) (Product Identity Identity)`

goes to ((->) (Either () (),Either () ())). So again we took Product to a sum type, but now we took Compose to a pair -- a product type! The intuition is that composition *multiplies* the possibilities of spaces in each nested functor.

Hmm.. products go to sums, composition goes to multiplication, etc. This should remind us of something -- these rules are exactly the rules for working with exponentials. x^n * x^m = x^(n + m). (x^n)^m = x^(n*m). x^0 = 1, x^1 = x.

Seen from the right standpoint, this isn't surprising at all, but almost inevitable. The functors we're describing are known as "representable," a term which derives from category theory. (See appendix on representable functors below).

In Haskell-land, a "representable functor" is just any functor isomorphic to the reader functor `((->) a)`

for some appropriate a. Now if we think back to our algebraic representations of data types, we call the arrow type constructor an exponential. We can "count" `a -> x`

as x^a, since e.g. there are 3^2 distinct functions that inhabit the type 2 -> 3. The intuition for this is that for each input we pick one of the possible results, so as the number of inputs goes up by one, the number of functions goes up by multiplying through by the set of possible results. 1 -> 3 = 3, 2 -> 3 = 3 * 3, (n + 1) -> 3 = 3 * (n -> 3).

Hence, if we "represent" our functors by exponentials, then we can work with them directly as exponentials as well, with all the usual rules. Edward Kmett has a library encoding representable functors in Haskell.

Meanwhile, Peter Hancock prefers to call such functors "Naperian" after John Napier, inventor of the logarithm (See also here). Why Naperian? Because if our functors are isomorphic to exponentials, then we can take their logs! And that brings us back to the initial discussion of type mathematics. We have some functor F, and claim that it is isomorphic to -^R for some concrete data type R. Well, this means that R is the logarithm of F. E.g. `(R -> a, S -> a) =~ Either R S -> a`

, which is to say that if log F = R and log G =~ S, then log (F * G) = log F + log G. Similarly, for any other data type n, again with log F = R, we have `n -> F a =~ n -> R -> a =~ (n * R) -> a`

, which is to say that log (F^n) =~ n * log F.

This gives us one intuition for why the sum functor is not generally representable -- it is very difficult to decompose log (F + G) into some simpler compound expression of logs.

So what functors are Representable? Anything that can be seen as a fixed shape with some index. Pairs, fixed-size vectors, fixed-size matrices, any nesting of fixed vectors and matricies. But also infinite structures of regular shape! However, not things whose shape can vary -- not lists, not sums. Trees of fixed depth or infinite binary trees therefore, but not trees of arbitrary depth or with ragged structure, etc.

Representable functors turn out to be extremely powerful tools. Once we know a functor is representable, we know exactly what its applicative instance must be, and that its applicative instance will be "zippy" -- i.e. acting pointwise across the structure. We also know that it has a monad instance! And, unfortunately, that this monad instance is typically fairly useless (in that it is also "zippy" -- i.e. the monad instance on a pair just acts on the two elements pointwise, without ever allowing anything in the first slot to affect anything in the second slot, etc.). But we know more than that. We know that a representable functor, by virtue of being a reader in disguise, cannot have effects that migrate outwards. So any two actions in a representable functor are commutative. And more than that, they are entirely independent.

This means that all representable functors are "distributive"! Given any functor f, and any data type r, then we have

distributeReader :: Functor f => f (r -> a) -> (r -> f a) distributeReader fra = \r -> fmap ($r) fra

That is to say, given an arrow "inside" a functor, we can always pull the arrow out, and "distribute" application across the contents of the functor. A list of functions from `Int -> Int`

becomes a single function from `Int`

to a list of `Int`

, etc. More generally, since all representable functors are isomorphic to reader, given g representable, and f any functor, then we have: `distribute :: (Functor f, Representable g) => f (g a) -> g (f a).`

This is pretty powerful sauce! And if f and g are *both* representable, then we get the transposition isomorphism, witnessed by `flip`

! That's just the beginning of the good stuff. If we take functions and "unrepresent" them back to functors (i.e. take their logs), then we can do things like move from `((->) Bool)`

to pairs, etc. Since we're in a pervasively lazy language, we've just created a library for memoization! This is because we've gone from a function to a data structure we can index into, representing each possible argument to this function as a "slot" in the structure. And the laziness pays off because we only need to evaluate the contents of each slot on demand (otherwise we'd have a precomputed lookup table rather than a dynamically-evaluated memo table).

And now suppose we take our representable functor in the form `s -> a`

and paired it with an "index" into that function, in the form of a concrete `s`

. Then we'd be able to step that `s`

forward or backwards and navigate around our structure of `a`

s. And this is precisely the Store Comonad! And this in turn gives a characterization of the lens laws.

What this all gives us a tiny taste of, in fact, is the tremendous power of the Yoneda lemma, which, in Haskell, is all about going between values and functions, and in fact captures the important universality and uniqueness properties that make working with representable functors tractable. A further tiny taste of Yoneda comes from a nice blog post by Conal Elliott on memoization.

**Extra Credit on Sum Functors**

There in fact is a log identity on sums. It goes like this:

log(a + c) = log a + log (1 + c/a)

Do you have a useful computational interpretation of this? I've got the inklings of one, but not much else.

**Appendix: Notes on Representable Functors in Hask.**

The way to think about this is to take some arbitrary category C, and some category that's basically Set (in our case, Hask. In fact, in our case, C is Hask too, and we're just talking about endofunctors on Hask). Now, we take some functor F : C -> Set, and some A which is an element of C. The set of morphisms originating at A (denoted by Hom(A,-)) constitutes a functor called the "hom functor." For any object X in C, we can "plug it in" to Hom(A,-), to then get the set of all arrows from A to X. And for any morphism X -> Y in C, we can derive a morphism from Hom(A,X) to Hom(A,Y), by composition. This is equivalent to, in Haskell-land, using a function `f :: x -> y`

to send `g :: a -> x`

to `a -> y`

by writing "functionAToY = f . g".

So, for any A in C, we have a hom functor on C, which is C -> Set, where the elements of the resultant Set are homomorphisms in C. Now, we have this other arbitrary functor F, which is also C -> Set. Now, if there is an isomorphism of functors between F, and Hom(A,_), then we say F is "representable". A representable functor is thus one that can be worked with entirely as an appropriate hom-functor.

June 3rd, 2017 at 1:12 am

The Comonad.Reader …[...] What web host are you the usage of? Can I get affiliate hyperlink in your host? I wish web site loaded up as quickly as yours lol[...]…

September 29th, 2019 at 10:31 pm

Possible computational interpretation of log(a+c) = log(a) + log(1+c/a):

log(a) + log(1+c/a) = log(a * (c/a+1))

x+1 can be interpreted as “x or nothing” aka “maybe x” aka “an optional x”

And we can interpret division as the inverse of tupling, i.e removing elements from a tuple.

Using that we can interpret the above as log (a or c) = log (a and maybe (c with a removed))”

For example if we had a choice of a carton of a dozen eggs or a carton of 18 eggs:

log(Egg^12 or Egg^18) = log(Egg^12 and (Egg^18/Egg^12 or nothing)) = log(Egg^12 and (Egg^6 or nothing))

In other words to handle a choice of 12 or 18 eggs we don’t need a 12 egg carton and an 18 egg carton but instead only a 12 egg carton and an optional additional 6 egg carton.

November 17th, 2019 at 7:00 pm

[...] A link to the blog post Gershom mentions on applicatives. [...]

January 10th, 2022 at 7:59 am

customized water bottles…Find the the top Printed Gear currently now available in addition at reasonable prices now only!…

January 10th, 2022 at 10:46 am

reusable face masks…Hire the the top promotional products that’s now available in addition at good rates now only!…

January 10th, 2022 at 5:17 pm

read more…Find the best badge holder that’s now available and on sale now only!…

January 10th, 2022 at 11:45 pm

imprinted promotional gifts…Hire the best badge reels that’s now available and on sale now only!…

January 11th, 2022 at 7:23 am

how to reverse diabetes permanently…Find the best endocrinologist currently now available in addition at good rates now only!…

January 11th, 2022 at 9:58 am

engraved pens…Hire the the top embroidered hats currently now available in addition at reasonable prices now only!…

January 11th, 2022 at 9:41 pm

endocrinologist…Get a top knee doctors in omaha ne that’s now available and at reasonable prices now only!…

January 12th, 2022 at 5:18 am

personal promotional products…Find the best custom surgical masks that’s now available and with reasonably pricing now only!…

January 12th, 2022 at 8:05 am

tradeshow signs…Hire the best safety kits that’s now available in addition at good rates now only!…

January 12th, 2022 at 11:51 am

imprinted knee pads…Get the the top safety kits that is now available in addition at good rates now only!…

January 12th, 2022 at 12:06 pm

best diabetes doctor…Get a top diabetes cure type 2 currently now available in addition at reasonable prices now only!…

January 12th, 2022 at 2:36 pm

customized lanyards…Get the best Printed Gear currently now available and at reasonable prices now only!…

January 12th, 2022 at 7:17 pm

diabetes prognosis…Get a top how to reverse diabetes naturally in 30 days that is now available and at good rates now only!…

January 13th, 2022 at 12:46 am

business gifts…Get a top read more that’s now available and at reasonable prices now only!…

January 13th, 2022 at 2:16 am

best diabetes doctor near me…Find the the top diabetes ketoacidosis treatment currently now available in addition at reasonable prices now only!…

January 13th, 2022 at 3:46 am

embroidered hats…Get a top corporate gifts that’s now available and at reasonable prices now only!…

January 13th, 2022 at 8:00 pm

branded products…Get the best reusable face masks that’s now available and on sale now only!…

January 13th, 2022 at 11:11 pm

imprinted safety glasses…Get a top customized water bottles currently now available in addition with reasonably pricing now only!…

January 14th, 2022 at 5:22 am

branded products…Hire a top customized lanyards that is now available and with reasonably pricing now only!…

January 14th, 2022 at 8:22 am

personalised engraved pens…Find the best imprinted promotional gifts that is now available in addition at reasonable prices now only!…

January 14th, 2022 at 11:38 am

logo safety glasses…Find the the top custom lanyards that is now available in addition at good rates now only!…

January 14th, 2022 at 2:00 pm

bezpłatne ogłoszenia…The Comonad.Reader » Representing Applicatives…

January 14th, 2022 at 8:53 pm

Printed Gear…Get a top corporate gifts that’s now available in addition at good rates now only!…

January 15th, 2022 at 12:06 am

wholesale promotional products…Find the best custom surgical masks that is now available in addition at good rates now only!…

January 15th, 2022 at 2:54 am

engraved pens…Get the best customized water bottles that is now available and on sale now only!…

January 15th, 2022 at 8:35 am

orthopedic doctor…Get the best nebraska orthopedic omaha that is now available and at good rates now only!…

January 15th, 2022 at 8:48 am

promotional coffee mugs…Find a top custom surgical masks that is now available in addition at reasonable prices now only!…

January 15th, 2022 at 3:18 pm

ortho knee…Hire the the top diabetes foot exam that’s now available in addition at good rates now only!…

January 15th, 2022 at 9:59 pm

knee doctor omaha ne…Hire the best ortho knee that’s now available in addition with reasonably pricing now only!…

January 16th, 2022 at 2:31 am

custom logo design…Get the the top imprinted safety glasses that’s now available and on sale now only!…

January 16th, 2022 at 11:17 am

personalised engraved pens…Hire the the top imprinted knee pads that is now available and at reasonable prices now only!…

January 16th, 2022 at 11:35 am

diabetes mellitus treatment…Hire the the top endocrinologist diabetes that’s now available in addition at good rates now only!…

January 16th, 2022 at 1:16 pm

orthopedics omaha ne…Find a top treatment for neuropathy pain that’s now available in addition on sale now only!…

January 16th, 2022 at 2:34 pm

this page…https://www.thingiverse.com/bandbinsurance/designshotel motel insurance companies…

January 16th, 2022 at 2:53 pm

this page…Find the best type 1 diabetes treatment that is now available and at good rates now only!…

January 16th, 2022 at 3:19 pm

knee doctors near me…Hire the best prediabetes treatments that’s now available and at reasonable prices now only!…

January 16th, 2022 at 3:24 pm

insurance for lodges…Get going with the best hotel insurance programs now on a best offer and gets your business ROI immediately!…

January 16th, 2022 at 4:17 pm

hotel insurance companies…Procure top quality venue insurance today on a best offer and gets your money flowing immediately!…

January 16th, 2022 at 5:14 pm

innkeepers liability insurance…Procure highly amazing bed & breakfast insurance now on a best offer and gets your business ROI immediately!…

January 16th, 2022 at 5:58 pm

personal promotional products…Hire the the top promo products suppliers that is now available in addition at good rates now only!…

January 16th, 2022 at 6:17 pm

diabetes and endocrinology…Find the the top treatment for diabetes type 1 that is now available and with reasonably pricing now only!…

January 16th, 2022 at 9:20 pm

omaha orthopedic…Get a top dka diagnosis that’s now available and with reasonably pricing now only!…

January 16th, 2022 at 9:23 pm

venue liability insurance…https://www.thingiverse.com/bandbinsurance/designsthis website…

January 16th, 2022 at 9:36 pm

knee doctors near me…Find a top diabetes ketoacidosis treatment currently now available and on sale now only!…

January 16th, 2022 at 10:04 pm

ortho doctor…Find the best orthopedics omaha ne that’s now available and at good rates now only!…

January 16th, 2022 at 10:31 pm

branded face masks…Get a top promotional coffee mugs that’s now available and at reasonable prices now only!…

January 16th, 2022 at 11:05 pm

nebraska orthopedic…Get a top gestational diabetes currently now available and with reasonably pricing now only!…

January 16th, 2022 at 11:20 pm

event venue insurance…Get going with highly amazing event venue insurance immediately on a best offer and creates efficiency for you immediately!…

January 17th, 2022 at 12:46 am

engraved pens…Find the best corporate gifts currently now available and with reasonably pricing now only!…

January 17th, 2022 at 2:34 am

knee doctor near me…Get a top diabetes treatment options that is now available in addition at good rates now only!…

January 17th, 2022 at 3:45 am

diabetes center…Find a top type 1 diabetes treatment currently now available in addition at reasonable prices now only!…

January 17th, 2022 at 4:10 am

nebraska orthopedic…Find a top diabetes doctor that’s now available and with reasonably pricing now only!…

January 17th, 2022 at 4:17 am

hotel motel insurance companies…https://ask.sqlservercentral.com/users/61894/bandbinsurance.htmlb&b insurance…

January 17th, 2022 at 4:28 am

diabetes mellitus treatment…Get the the top diabetes ketoacidosis treatment currently now available in addition on sale now only!…

January 17th, 2022 at 5:00 am

innkeepers liability insurance…Get going with top quality hunting lodge insurance today on a best offer and creates efficiency for you immediately!…

January 17th, 2022 at 5:07 am

logo face masks…Find a top personalised engraved pens that’s now available and with reasonably pricing now only!…

January 17th, 2022 at 6:07 am

diabetes doctor endocrinologist…Find a top diabetes specialist that is now available in addition at good rates now only!…

January 17th, 2022 at 6:14 am

diabetes wound care…Hire the the top ortho knee surgery that is now available in addition at good rates now only!…

January 17th, 2022 at 6:29 am

hunting lodge insurance…Get going with highly amazing insurance for b&b immediately on a best offer and gets your money flowing immediately!…

January 17th, 2022 at 6:50 am

hospitality insurance…Get going with highly amazing motel insurance brokers today on a best offer and gets your business ROI immediately!…

January 17th, 2022 at 7:36 am

custom printed face masks…Hire the the top custom surgical masks that’s now available and with reasonably pricing now only!…

January 17th, 2022 at 9:13 am

see it here…Find the best knee specialist near me currently now available in addition at reasonable prices now only!…

January 17th, 2022 at 10:33 am

nebraska orthopedic…Find a top type 1 diabetes treatment that is now available and on sale now only!…

January 17th, 2022 at 11:00 am

ketoacidosis diabetes…Hire the best ortho knee that is now available and on sale now only!…

January 17th, 2022 at 11:06 am

hunting lodge insurance…https://artmight.com/user/profile/381821b&b insurance…

January 17th, 2022 at 11:44 am

treatment for diabetes type 1…Get the the top diabetes cure type 2 that’s now available and at good rates now only!…

January 17th, 2022 at 11:48 am

hotel insurance requirements…Get going with highly amazing hunting lodge insurance immediately on a best offer and gets your business ROI immediately!…

January 17th, 2022 at 12:54 pm

ortho knee tests…Find the best neuropathy diabetes currently now available and at reasonable prices now only!…

January 17th, 2022 at 1:19 pm

omaha orthopedic clinic…Get the the top treatment for neuropathy in legs and feet that is now available in addition at good rates now only!…

January 17th, 2022 at 1:34 pm

hunting lodge insurance…Procure the best hotel motel insurance companies now on a best offer and creates efficiency for you immediately!…

January 17th, 2022 at 1:37 pm

see here…Procure top quality hotel insurance coverage today on a best offer and gets your business ROI immediately!…

January 17th, 2022 at 2:24 pm

tradeshow signs…Find a top logo printed face masks that is now available in addition with reasonably pricing now only!…

January 17th, 2022 at 2:41 pm

diabetes doctor specialist…Find the best ortho doctor that’s now available in addition at reasonable prices now only!…

January 17th, 2022 at 5:45 pm

knee doctors in omaha ne…Hire the the top knee doctor omaha currently now available in addition at good rates now only!…

January 17th, 2022 at 6:04 pm

navigate to this website…Find the the top diabetes mellitus treatment that is now available in addition on sale now only!…

January 17th, 2022 at 6:12 pm

read more…Get a top safety kits that is now available and on sale now only!…

January 17th, 2022 at 6:29 pm

knee doctors in omaha ne…Hire a top neuropathy diabetes that is now available and on sale now only!…

January 17th, 2022 at 6:35 pm

insurance bed and breakfast…Procure highly amazing hotel insurance programs immediately on a best offer and creates efficiency for you immediately!…

January 17th, 2022 at 7:39 pm

knee doctors near me…Hire the the top treatment for diabetes insipidus that is now available in addition at good rates now only!…

January 17th, 2022 at 8:21 pm

orthopedics omaha ne…Find the best knee doctor near me that’s now available in addition at good rates now only!…

January 17th, 2022 at 8:22 pm

my company…Locate highly amazing insurance for event space today on a best offer and gets your money flowing immediately!…

January 17th, 2022 at 8:27 pm

gestational diabetes complications…Hire a top diabetes cure type 2 that’s now available and on sale now only!…

January 17th, 2022 at 9:08 pm

tradeshow signs…Hire the best metal water bottles currently now available in addition with reasonably pricing now only!…

January 17th, 2022 at 9:15 pm

knee doctors in my area…Get the the top knee doctor omaha currently now available and on sale now only!…

January 18th, 2022 at 12:01 am

omaha orthopedic…Hire the best diabetes treatment that is now available in addition at reasonable prices now only!…

January 18th, 2022 at 12:35 am

diabetes cure type 2…Get a top ortho knee that’s now available and on sale now only!…

January 18th, 2022 at 12:56 am

knee pain doctor near me…Find a top management of diabetes that’s now available and on sale now only!…

January 18th, 2022 at 1:22 am

bed and breakfast insurance…https://myopportunity.com/profile/b-and-b-insurance/nwHomepage…

January 18th, 2022 at 1:28 am

treatment for diabetes type 2…Get the the top orthopedic doctors omaha ne that is now available and with reasonably pricing now only!…

January 18th, 2022 at 3:28 am

motel insurance program…Get going with top quality insurance bed and breakfast immediately on a best offer and creates efficiency for you immediately!…

January 18th, 2022 at 3:44 am

orthopedic doctor for knee pain…Find the the top best diabetes doctor currently now available in addition at reasonable prices now only!…

January 18th, 2022 at 4:02 am

Homepage…Procure top quality insurance bed and breakfast now on a best offer and creates efficiency for you immediately!…

January 18th, 2022 at 4:07 am

knee specialist omaha…Get the best knee doctors currently now available in addition at good rates now only!…

January 18th, 2022 at 6:00 am

west omaha orthopedic clinic…Hire a top ortho knee surgery that’s now available and with reasonably pricing now only!…

January 18th, 2022 at 7:10 am

reverse diabetes naturally…Find the best knee specialist near me currently now available in addition with reasonably pricing now only!…

January 18th, 2022 at 7:50 am

tote bags…Find the best business gifts that is now available in addition at reasonable prices now only!…

January 18th, 2022 at 8:39 am

knee doctor in my area…Hire the the top treatment for nephrogenic diabetes insipidus currently now available in addition with reasonably pricing now only!…

January 18th, 2022 at 10:39 am

ski lodge insurance…Get going with top quality bed and breakfast insurance rates now on a best offer and gets your business ROI immediately!…

January 18th, 2022 at 10:56 am

diabetes treatment options…Hire a top diabetes endocrinologist that’s now available in addition on sale now only!…

January 18th, 2022 at 11:03 am

prediabetes treatments…Find a top diabetes insipidus diagnosis currently now available in addition with reasonably pricing now only!…

January 18th, 2022 at 11:06 am

first aid kits…Get the the top logo safety glasses currently now available in addition with reasonably pricing now only!…

January 18th, 2022 at 11:13 am

type 1 diabetes treatment…Get the best treatment for neuropathy in feet currently now available in addition at reasonable prices now only!…

January 18th, 2022 at 11:31 am

hospitality insurance companies…Locate top quality insurance for bed and breakfast today on a best offer and creates efficiency for you immediately!…

January 18th, 2022 at 1:13 pm

omaha orthopedic clinic…Hire the the top best diabetes doctor that is now available in addition at good rates now only!…

January 18th, 2022 at 2:04 pm

diabetes cure…Find a top diabetes lab tests currently now available and on sale now only!…

January 18th, 2022 at 3:23 pm

this website…Hire a top treatment for nephrogenic diabetes insipidus that’s now available and at good rates now only!…

January 18th, 2022 at 3:52 pm

reverse diabetes…Get the the top treatment for diabetes insipidus currently now available in addition on sale now only!…

January 18th, 2022 at 4:33 pm

great post to read…Procure top quality bed & breakfast insurance immediately on a best offer and creates efficiency for you immediately!…

January 18th, 2022 at 5:04 pm

diabetes physical exam…Get a top knee doctors omaha currently now available in addition on sale now only!…

January 18th, 2022 at 5:48 pm

this website…Locate highly amazing hotel insurance companies now on a best offer and gets your business ROI immediately!…

January 18th, 2022 at 5:56 pm

my review here…Get the best diabetes mellitus currently now available and with reasonably pricing now only!…