Algebraic Structures: Things I wish someone had explained about FP

This gets handle by the Cats library in Scala (https://typelevel.org/cats/typeclasses/functor.html) by defining the type class the functor is being defined for as an abstract type on the functor itself.

It's very important for the type of `fmap f x` to be identical to `x` except in that its "inner" type has been modified. Without that, these kinds of interfaces lose all of their value.

This is irrelevant. The question isn't, does there exist a function, it's does the functor determine one. (Given any sets A and B there is always a function from A to B unless B is empty and A is nonempty. But that's not very helpful, is it?)

> I'm confused about this. Isn't the natural transformation from identity to another category (at least for small categories) equivalent to a functor?

This doesn't mean anything. A natural transformation is from one functor F:C->D to another functor G:C->D. Not from a functor to... a category? Huh?

Also smallness is irrelevant to all of this.

It is true that functors are morphisms between categories, but that's a morphism in CAT.

> I'm confused about this.

That's how these things go :-) Anyway, natural transformations are between two functors C -> D. This is an example of a 2-morphism in a 2-category. It's hard to come up with something to say other than they're just different, but think about this: a natural transformation is a consistent choice of morphisms F X -> G X (in D) for each object X (in C), but a functor needs to know where the morphisms of C go, too.

(An intuition is a natural transformations is kind of like a continuous path transforming one functor into another. This might just make things confusing, though.)

This is incorrect in a bunch of ways. First, Haskell types aren't truly just sets. As a simple, practical example you might have

    module Container (makeInt, Container, getValue) where
  
    data Container a 
      = Container { getValue :: a }
      deriving Functor

    makeInt :: Int -> Container
    makeInt = Container

More powerfully, we're only actually interested in discussing an interface in and of itself. A type may instantiate many interfaces of varying levels of power, but each interface needs to be well-defined and well-behaved on its own. Then their compositions need to be "glued together" properly.

So even if all Haskell Functors were actually TMapFunctors, it's still important to note that the interface TMapFunctor is a sub interface to Functor which allows more operations and has more laws.

An even stronger example of this is the fact that due to the way Haskell arrows work, all Haskell Functors are actually "strong" functors in the sense that we cannot even truly specify a non-string functor.

Strength is a way that fmap and products (or, really, category tensors) interact.

    strength :: Functor f => (a, f b) -> f (a, b)
    strength (a, fb) = fmap (\b -> (a, b)) fb

The notation "a -> f a" means a function that sends elements of 'a' to elements of 'f a', where 'a' is an object of the category Hask. (Functors don't look into the objects at the element level.)

Which one(s) you have been exposed to just depends on which mathematical subcultures you’ve interacted with.

Of course I added extra structure since I wanted to make a point about different kinds of algebraic structures which are all subsumed by the term "algebraic structure" or "algebra". And it's only possible to distinguish kinds of algebraic structures by differences in structure.

But adding extra structure in one example doesn't mean that I somehow exclude magmas from the definition. Here is the example again, extended to be include a component with no extra structure:

If I have a structure M with no structure but an operation, a structure S with an associative operation, and another structure G with an associative operation and a neutral element, I will say that M and S and G are different algebras, not "different magmas". Others looking at M or S or G will not ask "oh, what kind of magma do you have there", they will ask what kind of algebra.

Of course this extension by M doesn't change anything about the validity of the example. Magmas are just as included in the term "algebraic structure" as semigroups, groups, rings, and fields are.

> So you're saying people shorten the phrase "algebraic structure" to "algebra"; this hasn't been my experience.

<shrug> It has been mine. Wikipedia has lots of uses of the phrase "the algebra of": https://en.wikipedia.org/w/index.php?search=%22the+algebra+o..., always meaning something like "the algebraic structure of set X with operations f, g, and h".

As someone else pointed out elsethread, the term seems to be overloaded in different branches of mathematics.

https://en.wikipedia.org/wiki/Universal_algebra: "Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures. [...] In universal algebra, an algebra (or algebraic structure) is a set A together with a collection of operations on A."

Looks like I was wrong about this! You might want to retry your experiments with cheaper operations than sin and tan.

I wrote a little C benchmark to test this more:

    #include <stdio.h>
    #include <time.h>
    #include <math.h>

    extern void sinTanSeparate(double *a, double *b, int n) {
        for (int i = 0; i < n; i++) {
            b[i] = tan(a[i]);
        }
        for (int i = 0; i < n; i++) {
            b[i] = sin(b[i]);
        }
    }

    extern void sinTanFused(double *a, double *b, int n) {
        for (int i = 0; i < n; i++) {
            b[i] = sin(tan(a[i]));
        }
    }

    #define N (128 * 1024 * 1024)
    #define RUNS 5

    double a[N];
    double b[N];

    int main(void) {
        clock_t start, end;

        printf("will do %d runs over %zu MB of data\n\n",
               RUNS, sizeof a / (1024 * 1024));

        for (int i = 0; i < RUNS; i++) {
            start = clock();
            sinTanSeparate(a, b, N);
            end = clock();
            printf("separate: %f sec\n", ((double) end - start) / CLOCKS_PER_SEC);
        }

        printf("\n");

        for (int i = 0; i < RUNS; i++) {
            start = clock();
            sinTanFused(a, b, N);
            end = clock();
            printf("fused:    %f sec\n", ((double) end - start) / CLOCKS_PER_SEC);
        }

        return 0;
    }

    will do 5 runs over 1024 MB of data
    
    separate: 1.461349 sec
    separate: 1.020120 sec
    separate: 1.019002 sec
    separate: 1.019888 sec
    separate: 1.018454 sec
    
    fused:    1.014774 sec
    fused:    1.014724 sec
    fused:    1.013895 sec
    fused:    1.016440 sec
    fused:    1.013729 sec

But if we now comment out <math.h> and instead use some cheap "fake" implementations of in and tan:

    // #include <math.h>
    #define tan(x) (x + 1)
    #define sin(x) (x + 2)

    will do 5 runs over 1024 MB of data

    separate: 0.548558 sec
    separate: 0.154741 sec
    separate: 0.151271 sec
    separate: 0.150542 sec
    separate: 0.151337 sec

    fused:    0.078880 sec
    fused:    0.074742 sec
    fused:    0.078313 sec
    fused:    0.076987 sec
    fused:    0.077729 sec