I recently finished listening through LambdaCast, "a podcast about functional programming for working developers". Some notes on statically typed functional programming, basic category theory etc. will follow. I concentrate here mainly on the topics I haven't been using so much -> thus skipping some of the topics, focusing mainly on the category theorish parts. The podcast described category theory as the "math of maths".
On notation
I use here mainly Elm/Haskell-ish notation.
Parametric types
More notes later, but I'll mainly use Elm/Haskell-ish notation for parametric types:
List a means a list of values of type a, e.g. List String or List Int.- In Java/C# these are written e.g.
List<String> and in Scala as List[String]
- More on this below under "Polymorphism & type parameters".
Function type signatures
f: A -> B -> C means a function f that takes two parameters of type A and B and returns a type C.- With partial application, this can be interpreted as a function that takes parameter of type
A and returns function of type B -> C.
- So
f: A -> B -> C means the same as f: A -> (B -> C).
Some examples
List.length: List a -> Int - function that takes a list and returns it's length as integer.List.filter: (a -> Bool) -> List a -> List a - function that takes a "predicate function" and list and returns a new filtered list
Note that Haskell has roughly same notation but with two colons, e.g. f :: A -> B -> C.
Applying function
Write the function name followed by parameters. Note that no parentheses are used (as in e.g. JavaScript/Java/C#). For example, if we have addition function add: Int -> Int -> Int, it would be applied as add 1 2, evaluating to 3.
Function composition
Function composition is mentioned a couple of times. I'll use Haskell's infix dot notation, described by an example:
Let's say we have the two functions:
string2int :: String -> Int
int2bool :: Int -> Bool
We could chain the functions as (assuming we have a string str):
myBool = int2bool (string2int str)
This can be also written with function composition .:
myBool = (int2bool . string2int) str
Various terms
Domain and codomain
If there is a function fun: A -> B (that takes value of type A and returns a value of type B)
- All possible input values (
A) are called domain of the function
- All possible result values (
B) are called codomain of the function.
Note that domain here is different term than in domain-driven design.
Associative property
Associative property is a property of a binary operation. Roughly, for a binary operation ⊗ it means that (x ⊗ y) ⊗ z = x ⊗ (y ⊗ z). This holds true for example for addition, e.g. (2 + 3) + 4 = 2 + (3 + 4).
Types, categories and sets
These are somewhat related concepts and not totally identical. I'm going to cut quite many corners and mainly use the term type.
Some corners cut, a morphism is a mapping/relationship from a type to another. The word comes from ancient Greek morphe (“form, shape”). In programming context, a function f: A -> B from type A to type B is a morphism.
Note that the morphism can have same source and target type. Endomorphism (from ancient Greek endon, “inner, internal”) is such a morphism. Such a function would look like fun: A -> A, for example. As a practical example, function inc: Int -> Int (that increases it's argument by 1) is an endomorphism with type A being Int. For a more mathematical description, see Endomorphism in Wikipedia.
Isomorphism (from ancient Greek ísos, “equal”) is a morphism that has an "inverse morphism". This can be also described as "no data is lost in the transformation". With types A and B that would mean that there are functions fun1: A -> B and fun2: B -> A such that fun1 . fun2 = identity (i.e. fun1 (fun2 x) = x). For a more mathematical description, see Isomorphism in Wikipedia.
Homomorphism (from ancient Greek homós, “same”) is a morphism that "preserves structure", e.g. List.map or List.filter For a more mathematical description, see Homomorphism in Wikipedia.
Catamorphism (from ancient Greek katá, “downwards”) is a morphism from an algebra to another. List.fold was mentioned as an example. For a more mathematical description, see Catamorphism in Wikipedia. Dual/opposite of catamorphism would be Anamorphism (from ancient Greek aná, “on, up, above, throughout”). Cata- & anamorphisms (as well as pylo- & paramorphisms) are discussed within FP context in the paper Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire (link in the end)
With morphisms, denotational design/algebra was also mentioned. That would concentrating on the verbs and nouns of an "algebra" that would be e.g. HTTP requests. This sounded somewhat related to DDD. The following presentation was recommended: Denotational Design: From Meanings To Programs.
The name polymorphism comes from ancient Greek polús (“many"), indicating something that can have multiple different shapes.
First, in some contexts, especially object-oriented programming, polymorphism means usually subtype polymorphism. A common example of this is class hierarchy of classes Animal, Cat extends Animal and Dog extends Animal where instances of Dog and Cat are also instances of Animal. This is quite a different concept than described here.
In functional programming context (with static types), polymorphism means usually parametric polymorphism. This means having types that have type parameters. Java/C# generics is quite the same concept, some corners cut. Typical example would be list that is parameterized to contain elements of certain type.
In e.g. Elm/Haskell this is written as List a, in Scala List[A] and in Java/C# List<T>. As a detail, in Haskell the type parameter is typically written in lower case whereas in Scala/Java/C# it's typically written in upper case.
Semigroups and monoids (Episode 12)
A semigroup is type with a binary associative operation ⊕ that combines values of the type, resulting to a value of the same type. This operation is often called append or concat. Function signature would be append: A -> A -> A.
Many semigroups have an "identity" element e such as e ⊕ x = x ⊕ e = x for every x in the semigroup. A semigroup with an identity element is called a monoid.
Some examples of monoids:
- Integers under addition, 0 being the identity element
- Natural integers under maximum operation, 0 being the identity element
- Lists under append operation, empty list
[] being the identity element
- Strings under concat operation, empty string being the identity element
Algebraic data types (ADTs) (Episode 13)
Algebraic data type system is a type system, where types are derived from other types as product types & sum types.
Product types ("AND" types) are pretty much like typical struct/class types, a combination of values, e.g.
type Card = Card
{ suit : Suit
, rank : Int
}
The term product type comes from the idea, that all possible values of Card can be originated as multiplying all possible values of Suit with all possible values of Int.
Sum types ("OR" types) are types that have alternative "choices".
Following the playing card example, a very simple example would be Suit
type Suit = Diamond
| Heart
| Club
| Spade
So far this is like enums in many programming languages. What makes sum types more powerful is the possibility to add data to the values. Our earlier Card example did not support jokers but let's redefine it with a sum type:
type CardV2 = StandardCard Suit Int
| Joker
With this, a StandardCard value will consist of suit and rank, in addition to it's type. The term sum type comes from the idea, that all possible values of Card2 are possible values of StandardCard + Joker.
Very informally, a functor is a "containerish structure" (polymorphic type f a) that has a map operation (in Haskell world fmap), with the signature map: (a -> b) -> f a -> f b.
A "mathematical" functor follows two basic rules:
- Applying
map with identity function keeps the functor as it is: map id f == f
- Applying
map is composable: map (fun1 . fun2) x == map fun1 (map fun2 x)
List & Maybe are typi<cal examples of functor.
It's good to note that in mathematics context, the term functor is used mainly for the function/mapping, whereas in FP context the term is used more to describe the type that has map/fmap operation.
Note that partial application for map with a function (a -> b) results in a function of type (f a -> f b) that works "inside the functor" - this is called lifting.
Applicative functors (Episode 17)
Applicative functor is an abstraction between functor and monad, being somewhat new addition in Haskell world.
For an applicative functor type, there are two main operations (in addition to functors map/fmap)
- Function for wrapping a value inside applicative functor:
pure: a -> f a
apply: f (a -> b) -> f a -> f b
- Note that in Haskell
apply is named <*>
apply might feel a bit strange at first but with partial application that gives a possibility to apply a binary function to values inside two applicative functors.
As a simple example, we have two Maybes containing ints and we want to add them up (resulting up to a Maybe)
- We can map
Maybe Int to Maybe (Int -> Int) (e.g. having Just 5 would result as a function of one argument that increases it's argument by 5)
- The
Maybe (Int -> Int) can be given to apply with another Maybe, resulting as Maybe with sum.
Monad adds flatMap on top of applicative functor. Type signature is flatMap: m a -> (a -> m b) -> m b. In Haskell context, flatMap is named >>= and often called "bind".
- This kind of "forces" the operations to be sequential
- Haskell has "do notation" that makes it more convenient to work with monads.
Monads are not so complex topic to get grasp as they might sound. They have many applications
- Has lots of use with lists & maybes/optionals
- Used often with futures and promises so that the result from previous async operation is used to initiate the next one
- E.g. first do a HTTP request to fetch users and after that another to get some extra resources for the users.
- Haskell as
IO monad stating explicitly that something has side effects / state
Links
