Author

Alejandro Alcalde

Data Scientist and Computer Scientist. Creator of this blog.

Alejandro Alcalde's posts | Porfolio

This post is part of a series on Category Theory for Scala I am writing based on Bartosz Milewski Book on the same topic. As I read the book, I take notes, I try to solve the Challenges Bartosz proposes in Scala and make them public in this posts. You can find all the code in my github repo elbaulp/Scala-Category-Theory, you can also visit the Table Of Contents of this series.

In the previous post I wrote an introduction to Category Theory talking about composition, in this post I am going to talk about Types and functions in Category Theory.

Types and Functions

You can compose arrows, but not any two arrows, the target object of one arrow must match the source arrow. In terms of programming languages: a function's output type must match the input type of the next function.

What are Types?

You can think of a Type as Sets, they can be finite (Boolean, Char) or infinite (String, Integer). In Category Theory there is a Category of Sets, called Set. In this category, objects are sets, and arrows are functions from a Set to another.

The above is defined in the mathematical world, in the real world you could think of sets as types in a programming language and functions in the Set as functions in a programming language. The problem is, a mathematical function just knows the answer, but in a programming language you must write the code of that function, and that function may never return. To solve this, many programming languages declare a Type called Bottom type, all types extends the bottom type. Haskell bottom type is denoted by _|_, in scala is denoted by Nothing (See Nothing API documentation). A function that returns bottom is called a Partial Function.

<!–ad–>

The Mathematical Model

If you are a developer, I am sure you have found yourself running an interpreter in your mind while debugging. We Humans aren't very good at this, since it is difficult to keep track of all variables. There is an alternative to know if a program is correct, it's called Denotational Semantics. In short, Denotational Semantics is an approach of formalizing the meanings of a programming language, it is concerned with finding mathematical objects called domains that represent what programs do.

Opposed to Denotational Semantics is Operational Semantics. Operational Semantics tries to proof certain properties of a program (such as correctness) by constructing logical proofs, this is often too complex.

By having a mathematical model (Denotational semantics) you can write formal proofs proving your software correctness.

Pure & Impure functions

Pure functions are those who always return the same result for the same input and without side effects. For example, mathematical functions are always pure. On the contrary, impure functions have side effects.

Examples of types

Lets see now a few types, starting from the Empty set.

Which type would define an Empty Set? Think about it a moment, I've mentioned it above. In haskell this type is Void, in Scala Nothing. This Set has no elements. Previously I said there is a Category called Set, in which Objects are sets and Arrows are functions. I this context, if A is a set, the empty set, only one function f exists from {} to A, the Empty Function.

Could you ever define a function that takes as parameter an object of type Void (an empty set)?, yes, you can, but you won't be able to call it, since you can't pass it a parameter which type is Void. However, the return type of this function could be any. This types of functions (Those who can return any type) are called polymorphic in the return type, here are some examples:

cantCallMe :: Void -> a

A lower case letter in a function's declaration in haskell means a can be of any type. Here are examples in scala:

def cantCallMe(a:Nothing) = 1
def cantCallMe(a:Nothing) = "str"

Moving on, what Type would be the one corresponding to the Singleton Set?, that is, a type with only one element (one possible value). In C++ this type is void, not to be confused with Haskell's Void, Void is the empty set, whereas void in C++ is a singleton set, because its a set with only one element, in fact, you can call functions receiving void arguments. An example of such functions is int f314() { ret 314 }, you can call this function, and it will return always 314.

Although it may seems this function is not taking any arguments, it is. Because if you can't pass it an argument, you could not call it. So it is taking a dummy value with only one instance (a singleton set, in this case 314). Lets see the same example in Haskell and Scala:

f314 :: () -> Integer -- from Unit to Integer
f314() = 314

Here it becomes clearer that f314 is taking a parameter, the Unit type (allowing only one value). You call this function with f314(), which denotes more explicitly this function is taking one parameter.

In Scala this type is also called Unit, and its unique value is denoted also by (), as in Haskell:

def f314() = 314 /* from () => Int */

All this may be seems like nonsense, but we are building the concepts bottom up, as you delve more deeply into Category Theory, it will gain more and more sense. For example, with this knowledge you can avoid mentioning explicitly the elements in a set, now you can reference them with Arrows (Functions in this case, since we are in the Category of Sets). Functions going from Unit to any type A are in one-to-one correspondence with elements in that set A.

What about functions returning void (C++), or Unit (Haskell, Scala)? Usually this kind of functions have side effects, but if they are pure what they are doing is mapping elements in a set A to a singleton, so, all elements in a set A will be mapped to the same value. Lets see a few examples:

fInt :: Integer -> ()
fInt x = ()

The special declaration using _ means it does not matter what argument you pass in to f, as the argument type doesn't matter, you can define the function above in a more generic way:

unit :: a -> ()
unit _ = ()

It won't matter what type you pass to this function, it will always be mapped to Unit. Here is the scala equivalent:

def unit[T](a:T):Unit = ()

The next logical type to see is a set with 2 elements, which corresponds with bool in C++, Bool in Haskell and Boolean in Scala. Functions to booleans are called predicates, examples of this functions: isDigit, isLower, isLetter and so on.

Challenges

Now I want to share with you two of the Challenges Bartosz proposes on his site that I solved. Please consider that they might be wrong or can be improved, I would like to hear your take on this challenges, so please comment below. You can see the complete list of challenges on Bartosz website (Linked in the refernces), I've only solved #1 and #6.

Challenge #1

Here is what I've done, I tried to do it with an immutable Map, but couldn't get it to work:

case class Memoize[A, B](f: A => B) {
  private[this] val values: mutable.Map[A,B] = mutable.Map.empty
  def apply(x: A) = values getOrElseUpdate(x, f(x))
}

you can test it with:

def f(a:Int) = {
  Thread.sleep(5000)
  a*a
}
val b = Memoize(f)
b(10) // Takes 5 secs
b(10) // immediate

Challenge #6

References

Types and Functions, by Bartosz Milewski

Spot a typo?: Help me fix it by contacting me or commenting below!

Categories:

dev

Tags:

Maybe this posts are also worth reading

«« Cryptography 101's Table of Contents Scala Category Theory - Table of Contents »»