If you've been exposed to lambdas (whether in Java or Kotlin), you already know at least the basics of what lambdas are, the syntax for using them, that they're more succinct than instantiating anonymous classes etc etc.
Rather than talking about that, I figured we would talk about functions and lambdas on a higher level.
I think most of us are familiar with map and, having used it quite a bit, have an intuitive understanding of what any given call to map will do.
Does anyone know a bit more about map, what it is and where it came from?
A lot of Functional Programming derives from a field of Mathematics called Category Theory.
Very briefly, Category Theory is the study of functions, where "function" refers to a process that associates to each element of a set X a single element of a set Y.
Pure functions have only inputs and outputs- no access to anything other than what was sent in, and no ability to mutate what was sent in or generate other side effects.
Now, I suck at math, but fortunately we don't need to know math to learn more about concepts programming languages have borrowed from Category Theory.
Learning about it can make us better programmers if we go from an intuitive, but maybe a bit vague, understanding of things like map to fully understanding them!
A Functor is anything that can be mapped over. Map, the defining function of a Functor, is quite simple.
interface Functor<A> {
fun <B> map (function: (A) -> B) : Functor<B>
}This just says
Given a Functor of A, when map is called with a function of A to B, return a Functor of B
This is all just a bunch of mumbo jumbo, but in our day to day programming, Functors (or potential Functors) are everywhere!
Lists are a great candidate for a concrete example.
class BoringList<A>(val backingList : List<A>) { }The above class is just a wrapper (with no added behavior) around a list. Let's make it do something interesting by declaring it a Functor.
class InterestingList<A>(val backingList : List<A>) : Functor<A> {
override fun <B> map(function: (A) -> B): InterestingList<B> {
//implement - DON'T CHEAT by simply calling map on backingList
}
}
fun main(args: Array<String>) {
//experiment
}Example implementation (very imperative, but that's ok)
class InterestingList<A>(val backingList : List<A>) : Functor<A> {
override fun <B> map(function: (A) -> B): InterestingList<B> {
//the current InterestingList is of type A but we need to return
//a InterestingList of type B, so first, make a new backingList
//of type B
val transformedList = ArrayList<B>()
for (item in backingList) {
//apply the provided function to each item
val transformedItem = function(item)
//add them to the transformedList of type B
transformedList.add(transformedItem)
}
//return an InterestingList of type B
return InterestingList(transformedList)
}
}
fun main(args: Array<String>) {
val interestingList = InterestingList(listOf("foo", "bar"))
//when calling map on InterestingList<String> with a function: (String) -> Int, we get InterestingList<Int>
val mappedInterestingList = interestingList.map { string -> string.length }
}Now, we've used List as an example, but remember: Functors (or potential Functors) are everywhere! It's easy to think of Functors as "containers", but it's more useful to think of them as a "computational context", since eg Options and Futures can also have map.
-
The Functor of List applies the function to all elements in the list
-
The Functor of Option applies the function if it's non-empty. (or rather, any function applied to Nothing is still Nothing)
-
The Functor of Future applies the function to a result once a result is available.
Now, can someone think of a few important things to keep in mind when implementing map?
Eg, what if your implementation of map for a List always returned an empty list, or a list twice the size of the given list? Or what if it mutated the items it mapped over, or called a bunch of other god knows what functions? That would be not so good!
So when implementing Functors you actually have to observe the Functor Laws. There is nothing mysterious about these laws; their role is to guarantee map behaves sanely and actually performs a mapping operation (as opposed to some other nonsense). The first law is:
map id = id
id is the identity function, which returns its argument unaltered. The first law states that mapping id over a functorial value must return the functorial value unchanged. Next, the second law:
map (g . f) = map g . map f
It states that it should not matter whether we map a composed function or first map one function and then the other (assuming the application order remains the same in both cases).
A Monad is anything that can be flatMapped over. Sounds scary! It's actually surprisingly easy to understand, but can be a little more complex to implement. Don't feel bad if you don't get it right!
FlatMap, the defining function of a Monad, is quite simple.
interface Monad<A> {
fun <B> flatMap (function: (A) -> Monad<B>) : Monad<B>
}This just says
Given a Monad of A, when flatMap is called with a function of A to Monad B, return a Monad of B
If you recall Functor
interface Functor<A> {
fun <B> map (function: (A) -> B) : Functor<B>
}Which just says
Given a Functor of A, when map is called with a function of A to B, return a Functor of B
The two are EXACTLY the same except instead of a function of A to B, it's a function of A to Monad B.
Let's return to the concrete example of the list: if you call map on your list with a function of A to List B, what will you end up with?
You would end up with a list of lists! And all flatMap does is "flatten" that into a single list.
interface Monad<A> {
fun <B> flatMap (function: (A) -> Monad<B>) : Monad<B> //yes!
fun <B> flatMap (function: (A) -> Monad<B>) : Monad<Monad<B>> //no!
}Implementing is left to the overachievers.
Remember: just like Functors, Monads (or potential Monads) are everywhere!
-
The Monad of List flattens lists of lists.
-
The Monad of Option allows chaining many potentially absent things together, short circuits if any of them are empty, and returns a flattened end result.
-
The Monad of Future allows chaining together computations that don't have a result yet, and returns a flattened end result.
Just like when implementing map for Functors the implementation must satisfy the Functor Laws, when implementing flatMap for Monads, the implementation must satisfy the Monad Laws. I will not get into them here, but for anyone who's interested this is a great resource https://en.wikibooks.org/wiki/Haskell/Understanding_monads
As we've seen, map and flatMap really shouldn't be these random functions that sometimes get added to things and sometimes not. Functional programming languages usually have an interface Functor, and an interface Monad etc which all classes that implement map and flatMap extend, and there's no reason why it shouldn't be like that in Java or Kotlin as well.
Unfortunately, neither Java nor Kotlin do this, which is kind of a missed opportunity.
Most of us instinctively reached for looping language constructs like for and while.
So since we're so used to that, where's the benefit in all this new map, flatMap etc nonsense? It's difficult to understand, hard to read etc etc.
A few differences could be pointed out.
//this looks fine but will actually blow up, can you tell why?
int[] array = {1, 2, 3};
int[] doubled = int[array.size];
for (int i = 0; i <= array.size; i++){
doubled[i] = array[i] * 2;
}
//even if it didn't blow up, there's still a lot of noise about *how* to
//double that is completely besides the point of *what* we actually want,
//which is simply to multiply the items by 2loops describe in detail how to do something while map hides implementation details and let's you focus on what to do. And since describing in detail how to do something isn't required, the risk of bugs in the how part is completely eliminated.
loops are literally stateful operations where we're, well, looping through a collection item by item (in a certain order) using something to keep track of how far we've looped. Sometimes the state matters to what's happening inside the loop, eg when we find what we're looking for and return early. Mapping operations have no such state, so the risk of bugs due to state are completely eliminated.
loops have no real meaning. Eg, it's possible to loop through things and do nothing, mutate the items as you loop through them, mutate the collection you're looping through, return something from an enclosing method... Loops can do anything. Map on the other hand is a specific thing, has a specific use case, does no more and no less, makes guarantees as to what it does and doesn't do etc etc. This allows us to reason about code more effectively than with loops where we have to play compiler and debugger and keep a bunch of state in mind all the while trying to understand what's actually being done inside.
These are just a few examples, I'm sure more could be thought of!
This is pretty good and might be worth publishing on Medium.
However the direction of writing makes an unexpected turn after
Unfortunately, neither Java nor Kotlin do this, which is kind of a missed opportunity.. I was expecting that you'd explain why classes that implement map/flatMap should implement Functor/Monad but instead go on to explain the flaws of an imperative coding style. This would be greatly improved if you could provide an example of why not implementing Functor/Monad for classes that have map/flatMap methods is a missed opportunity as you've said.