loading...
Cover image for Semigroups

Semigroups

moosch profile image Ryan Whitlie ・3 min read

Write You Some FP Maths

Another article in a series where I'll be looking at some mathematical concepts and functional programming stuff in JavaScript.

FP FTW!

Semigroups

This time we're looking at Semigroups 🎉
But what are they?

Well, according to Wikipedia:

a semigroup is an algebraic structure consisting of a set together with an associative binary operation.

In non-mathematic terms, and in our case functional programming terms, it's a way to bind/join/concat two things together. Check out the Fantasy Land spec. Pretty simple huh? So let's jump right in!

Wait! As we know JavaScript is not type safe, so it's a good idea to make sure we don't get any unexpected errors, only a TypeError we can handle if required. So lets create a utility function to get the type of some data:

const getDataType = (a) => {
  if (a === undefined) {
    return 'Undefined';
  }
  if (a === null) {
    return 'Null';
  }
  return (a).name || ((a).constructor && (a).constructor.name);
}

// In use
getDataType('Strings'); // => String
getDataType(['Array']); // => Array
getDataType({ obj: 'Object' }); // => Object
getDataType(5); // => Number
getDataType(null); // => Null
getDataType(); // => Undefined

Excellent! This can be a useful function in many cases, and we're going to use it in our Semigroup.

What's next?
Well, next we need to actually define our Semigroup. Like a lot of FP stuff, it's a good idea to start with a container. Let's create a container for our initial data and define a concat method that will be called to bind/join/concat a second piece of data to the first. The concat method will have to return a new container that holds the result of the join, that way the data can continually be reused by calling the concat method again.

const Semigroup = (a) => ({
  a,
  toString: () => `Semigroup(${a})`,
  concat: (b) => Semigroup(a + b),
});

You may notice the toString method, this is common in many languages to print the contents of a container.
Great! Except it's not so great just yet because if we create a container with an array like to const oneSemigroup = Semigroup([1]) and try call our concat method with an object oneSemigroup.concat({ a: 'a' }) our container value will then be 1[object Object]. So let's use some type safety to make sure we are joining the same datatypes.

We do this by adding a guard to our concat method, making it a guarded function. This simply means the input has to pass some form of validation before the rest of the function is executed. In mathematics these guards are called constraints.

Our guard function should take in both our initial value and the second value to compare types:

const typeGuard = (a, b) => {
  const aType = getDataType(a);
  const bType = getDataType(b);

  if (aType !== bType) {
    throw new TypeError(`Type mismatch. Expected ${aType} datatype`);
  }
}

Now we're ready to guard up our Semigroup:

const Semigroup = (a) => ({
  a,
  toString: () => `Semigroup(${a})`,
  concat: (b) => {
    typeGuard(a, b);
    return Semigroup(a + b);
  },
});

Boom💥 Fully guarded function. There's just one super tiny little issue...and it's a big one! If we try to use the add operator + on some datatypes we may not get what we expect. For example {} + {} gives us [object Object][object Object]. Not that helpful. We need a way to join two of the same datatypes regardless of what their type are. What we're going with here is a simple switch statement that handles various cases. Time for another useful utility function:

const typeSafeConcat = (a, b) => {
  const type = getDataType(a);
  switch (type) {
    case 'Number':
    case 'BigInt':
    default:
      return a + b;
    case 'String':
    case 'Array':
      return a.concat(b);
    case 'Object':
      return { ...a, ...b };
    case 'Boolean':
      return Boolean(a + b);
    case 'Function':
      throw TypeError('Cannot concat datatype Function');
    case 'Symbol':
      throw TypeError('Cannot concat datatype Symbol');
    case 'Null':
      return null;
    case 'Undefined':
      return undefined;
  }
}

Wonderful. We've reached a happy place where we can create a Semigroup and call our concat method on it as much as we want safe in the knowledge that we'll either get a TypeError if we do something silly, or get a new Semigroup containing the data we'd expect.

You can find the finished code in this gist.

If you have any questions of feedback feel free to comment 🙂

Happy coding λ

Posted on by:

Discussion

markdown guide
 

Hi Ryan thanks for the article. My issue with your content is that you have created very monomorphic structure from this.

You are creating global concat to work with all possible inputs in some one 'right' way. Semigroup is just a pair (data:T,concat:T->T->T). In other words you have to have data type and function which for a given two elements create third element, and this function obeys Semigroup rules.

My point is - such hardcoded implementation gives no place for defining custom 'concat' for specific data type. And this is the whole point, I want 'concat' for type T works like that and for type Y differently.

 

Hello again Maciej, thanks for the comment.

Hhmm you want to have a custom concat for type T and another for type Y. This is what I was trying with the typeSafeConcat method, but only with the input of concat, not taking into account the init of Semigroup. The "hard coding" part is necessary in JavaScript as these structures are not built into the language, they have to be defined and then can be abstracted away within a library.

As for this Semigroup being monomophic, that is correct. A Semigroup doesn't have to be polymorphic. My initial thought was if it was, it may disobey the associativity law, but I don't think that's the case. If our "concat' is perhaps a string template, something like ${T}${Y} then I think anything would still obey associativity. Thinking about it from your comment, I think a simple example would be:

const _Semigroup = (a) => ({
  a,
  toString: () => `Semigroup(${a})`,
  concat: (b) => {
    return `${a}${b}`;
  },
});

And to define a concat per data type, something like this

const _strConcatStr = (a, b) => `${a}...${b}`;
const _strConcatNum = (a, b) => `${a} ${b}`;
const _strConcatArr = (a, b) => `${a} List(${b})`;

const _Semigroup = (a) => ({
  a,
  toString: () => `Semigroup(${a})`,
  concat: (b) => {
    if (Array.isArray(b)) {
      return _strConcatArr(a, b);
    }
    if (typeof b === 'string') {
      return _strConcatStr(a, b);
    }
    if (typeof b === 'number') {
      return _strConcatNum(a, b);
    }
    // ...
  },
});

const stringGroup  = _Semigroup('Answer:');
stringGroup.concat("42"); // => 'Answer:...42'
stringGroup.concat(42); // => 'Answer: 42'
stringGroup.concat([4,2]); // => 'Answer: List(4,2)'

Is this more what you were thinking?
Thanks again for the comment, it's good to hear more opinions to make me think more :)