-1
$\begingroup$

In my continuing effort to finally wrap my brain around advanced FP/categorical concepts, I've been reading dozens of articles and tutorials; what I have concluded is that:

1) Category Theory and Software Engineering use the same words in different ways; or, I think, Software Engineering uses category theory terms far too loosely. (Functor, Monad, Applicative, and so forth.)

2) The operations around functors/monads are like pizza toppings: Every single library/tutorial has its own terminology that is borrowed somewhat incorrectly from every other, and no one can agree on anything.

3) Using Haskell to explain these concepts is useless to anyone who doesn't already know Haskell, because Haskell is built to make implementing them so trivial that it doesn't translate back out to languages that don't.

To that end, I want to lay out what I THINK the full set of terminology is in a non-Haskell-ish language (a pseudocode that resembles Javascript, sort of), and the numerous variations I've seen, and invoke Cunningham's Law to ask people to correct me when (not if) I demonstrate I am still not grokking it.

I will update the post with corrections where possible, but if you're coming to this later please be sure to read the comments, too.


If you want to translate your basic category of types into a category with "more contextually useful stuff" (which could be logging, null/optional handling, IO awareness, etc.), there are a couple of things you need, in practice.

First, you need an operation that lifts a value from your type to your enhanced type; category theory canonically calls this unit. Haskell calls it return. In a non-typeclass language, it's usually implemented as the constructor of an class that represents "type plus context"; Eg, Maybe::constructor(val). I have also seen pack, lift, and of as static method names here that wrap the constructor. I've even seen join, which seems confusing with join as an alias of bind (below).

Second, you need a way to lift a unary function that takes a type T and returns the same type T to one that takes an enhanced version of T and returns an enhanced version of T. Haskell calls this fmap. Non-functional languages variously call it map, apply, then (if dealing with promises) or other things and assume that it will also be invoked when passed. So you end up with no simple lifting function, but a "lift and use" operation.

The combination of unit and fmap constitute a functor, because they're lifting a type and function to the enhanced type category.

You also need a way to convert the enhanced value back to unenhanced; In Haskell this is just referencing the value. In Rust it's called unwrap. Other names I've seen include flatten, value, get, etc. Sometimes there are multiple of these, such as Java's orElse and orElseGet, but those are convenience utilities not part of the core definition. Other non-core operations that vary depending on the type of enhancement may be isNothing (Maybe), logs (for a Writer), or some IO related stuff.

Third, you need a way to convert a unary function that takes a type T and already returns an enhanced T, and allow it to take an enhanced T as its parameter. This is a different operation from fmap. Haskell and others call this bind. In less powerful languages I've seen this also called flatmap, map, join and chain. (flatmap because it first calls flatten to extract the value, and then calls fmap, then rewraps it into an Enhanced T.)

In canonical Javascript, then works with either a T->T or a T->Enhanced function, effectively combining fmap and bind into a single function named then. Whether this is wise or not is a subject of some debate.

A function from T to Enhanced is (half of) a functor. bind allows you to combine those together in a way that follows the monoid laws. Thus, bind is a monad (a monoid for (endo)functors). Strictly speaking, from a category theory point of view only bind is a monad. In Software Engineering, though, it's quite common to refer to the whole set of things as a monad, since they're usually implemented as methods. bind also gets called join or chain in other languages. That is:

class Enhanced {

    private value;

    // These two are technically a functor.
    func constructor(value) { ... }

    static func fmap(function from T to T) returns function from Enhanced<T> to Enhanced<T>

    // Doesn't have a name in Haskell, but object-y languages always have it:
    public func value() returns the value itself

    // Also called `apply` in some versions.
    public func map(function from T to T) returns the result of applying the function to value

    // Strictly speaking, this is the monad.
    // Also called `join` or `chain`.
    public function bind(function from T to Enhanced<T>) returns the result of applying the function to value, but wrapped in Enhanced

}
// Colloquially, programmers call the whole thing a "monad", aka a monad pattern.

Which is equivalent to the following in a more type-robust functional language (Haskell, F#, etc.):

  • Maybe value ; Either value; or various other type constructors, equivalent of unit or the object constructor.

  • fmap, which can be a free-standing function because of more robust typing

  • bind, but it is so common it gets turned into an operator >== and the type system figures out which bind to use, since there's several.

Fourth, you need a way to lift non-unary functions. Haskell auto-curries everywhere so... it just sorta falls out naturally. In other languages it's generally a separate function (or static method), liftA2 for a 2-argument version, liftA3 for a 3-argument version, etc. That function is equivalent of fmap (or is it bind? Not sure here?) but for a binary and trinary function, respectively.

I... don't quite grok how you would then incorporate a liftA2ed function into an enahnced type, other than manually currying it.

Which then means if you want to have, as an example, a zero-division-safe arithmetic, you'd do:

func add(x, $y) => x + y;
func sub(x, $y) => x - y;
func mult(x, $y) => x * y;

func div(x, y) => {
    if (y == 0) return new Maybe();
    return Maybe(x / y);
};

func liftA2(fn) {
    // I am definitely wrong here.  Please advise.
    return func (a, b) => Maybe(a).map(fn).bind(b);
}

maybeAdd = liftA2(add);
maybeSub = liftA2(sub);
maybeMult = liftA2(mult);

At this point I run out, because I feel I'm missing a step along the way here. I suspect something related to Applicatives, because I haven't fully wrapped my head around those. (I haven't gotten to that chapter in Bartzoz's book yet.)

So that's where I am. Can anyone advise on where I'm going off the tracks and what the next piece of railroad tie is?

$\endgroup$
  • $\begingroup$ You keep saying "you need this, you need that". Need them for what? And in case I think you're getting of the tracks, what would constite a useful answer to you? $\endgroup$ – Andrej Bauer Sep 20 at 16:23
  • $\begingroup$ I think you need to be a lot more precise and careful here. You start by considering "your basic category of types" that you want to "translate" (into some other category that is not described). What is this "category of types", and what does "translate" mean here? $\endgroup$ – Andrej Bauer Sep 20 at 16:25
0
$\begingroup$

Can anyone advise on where I'm going off the tracks

You also need a way to convert the enhanced value back to unenhanced

No, generally speaking you don't have such conversion. For example, in JS you cannot get a value out of a Promise, you have to resolve the Promise .then(f). Same goes for Haskell, you cannot (without unsafe stuff) get a value a out of a Monad say IO a, since there is no monad interface function like: m a -> a. However, you can use >>= (bind) m a -> (a -> m b) -> m b to chain computations on such values, by providing a function a -> m b.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ At some point you need to convert back, otherwise you can't, well, print anything to the screen. You need access to the something. That's not the part I'm tripping up on; it's the subtle terminology differences and the way to deal with non-unary functions. $\endgroup$ – Crell Dec 25 '19 at 16:08
  • $\begingroup$ "At some point you need to convert back, otherwise you can't, well, print anything to the screen." Well you can return a new state of the world with something printed on the screen: "The universe as part of our program" -en.m.wikibooks.org/wiki/Haskell/Understanding_monads/IO $\endgroup$ – madnight Dec 25 '19 at 21:32
  • $\begingroup$ That's still not the question I'm asking, and plenty of implementations (eg, Rust) do include an unwrap command. The inconsistent terminology is the main thing I'm trying to confirm, and how to handle non-unary functions. Can you advise on that? $\endgroup$ – Crell Dec 27 '19 at 16:03
  • $\begingroup$ I can confirm the inconsistent terminology. This problem also exists in math, where different authors prefer different notation and sometimes different terms (depending on their background). In the end it's all about the definition, if two different terms have the same definition, then they are the same thing. I prefer to use the terms from category theory, so I say Functor instead of Mappable. $\endgroup$ – madnight Dec 28 '19 at 13:13
  • $\begingroup$ LiftA2 is defined as: liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c. So it takes a binary function (also called bivariate function, or function of two variables) and two Applicative Functors and returns an Applicative Functor. However, you don't need liftA2 for safe arithmetic. A safe division can be defined as: safeDiv :: Integer -> Integer -> Maybe Integer safeDiv x 0 = Nothing safeDiv x y = Just (x `div` y) $\endgroup$ – madnight Dec 28 '19 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.