When some programmers pick up a functional programming language like Microsoft Excel, they stop caring about identifier names.
A1 = blah B1 = function(A1, C2) ...
Can this observation be explained while maintaining consistency? I think it can.
Some programmers are married to the imperative, side-effecting mindset. This makes them fearful of Scala’s implicit keyword (among many other high-level programming constructs and abstractions). You can read all sorts of amateurish criticism of this language construct on various websites, but I plan to show why they are a necessity to the language being useful (in the intellectually true and meaningful sense — not in a “Java” “pragmatist” sense (I know I’m treading on thin ice here, but the point is worthwhile)).
I also do not plan to address the amateurish claims specifically, since if you are like me, you simply acknowledge their existence, feel a bit sad, then get over it and move on. I mention these cases so that they can be contrasted to my plan to address a discussion I had with someone (who shall remain nameless for now and leave it up to them if they wish to reveal themselves) who put forward an intellectually constructed argument about why they can/should be eliminated. These kind of discussions are very purposeful. While my opponent’s argument was well thought-out (in contrast to the aforementioned), I still think it is wrong. Here is why.
You can do away with implicit definitions in favour of named functions with partial application. This is true, but is it useful? Furthermore, Scala is not exactly friendly to partially applying function arguments, requiring varying levels of awkwardness in certain contexts. I will assume, since I am a nice guy, that this is not the case. I will now alter the argument to what I consider to be equivalent, “Haskell can do away with type-classes”. I altered the argument simply for the sake of brevity in discussion — I will tie it back to Scala code examples at the end.
Let us assume we get rid of just one Haskell type-class, Monad. A monad is a useful abstraction, so we would certainly have to represent it (if you don’t believe this, then it is almost certain that you have reinvented monads inadvertently). We might do this as follows:
{-# LANGUAGE RankNTypes #-} data Monad' m = Monad' { unit :: (forall a. a -> m a), bind :: (forall a b. m a -> (a -> m b) -> m b) }
Then, when it comes to instances, we would write:
listMonad = Monad' (return :: a -> [a]) (>>=) maybeMonad = Monad' (return :: a -> Maybe a) (>>=)
Now when we wish to write the all-important functions over monads, we have to do the following:
sequence' monad [] = unit monad [] sequence' monad (x:xs) = let (>>>=) = bind monad in x >>>= \y -> sequence' monad xs >>>= \ys -> unit monad (y:ys) mapM' monad f as = ... etc. etc.
The proposal by my opponent in the discussion is that we now write a version of each monad function for each instance by partially applying the monad instance. This is very cumbersome and importantly, less useful.
listSequence = sequence' listMonad maybeSequence = sequence' maybeMonad listMapM = mapM' listMonad ... and so on.
This creates what would otherwise be code in the order of O(1) to turn into O(n) code! This is not good. Do we get any benefit? No, there is no benefit, other than, in the case of Scala, appeasement of ‘the irrational squad’ i.e. those fervently offended by the suggestion to divorce imperative programming. Let us just address this irrationality, even if just briefly, so we can move on.
Unlike Scala, Haskell’s side-effects are controlled, so the mind-shift is forced by the compiler (a successful form of counselling?). A Scala implicit function can perform side-effects. This would be very bad; if they were controlled, would these irrational objections be raised? The answer is no and it is quite easy to expose.
A claim to the contrary is often a case of doublethink. Java is a programming language that deliberately encourages side-effects and by implication (also, by its poor type system), makes abstraction and composition extremely difficult to the point of impossibility very early on (see Functional Java for evidence). Yet even in this language — perhaps the most contrived available — we find implicit conversions that attract no objections whatsoever!
Imagine this Java signature int toInt(char c). Such a user-defined function could indeed perform side-effects and any language feature permitting implicit use of this function is likely to attract criticism. Yet, this is one example of such a function built right-in to the Java language, which is guaranteed by the language specification to perform no side-effects. It is the fact that it is internalised by the user to perform no side-effects that makes it acceptable.
This is valid Java:
int i = c; // where c is of type char
I don’t wish to labour this point, other than to make it clear how easy it is to crush these irrationalities (it continues on in a usual uninteresting fashion).
Requiring code to blow out to O(n) from O(1) is itself not bad, but to further observe that there is no gain from it is conclusive. Interestingly, this is similar to a complaint by David MacIver (and myself — I am just less vocal about it) that Scala lacks default function argument lists in preference for overloading. This also creates unnecessary code-bloat (O(1) -> O(n)) for no benefit. (I hope I am not misrepresenting David here — I have lost the reference to his complaint).
Here is the equivalent Scala code to the above, however, Scala’s type system lacks the ability to pass the unit and bind functions — instead requiring the use of traits.
trait Unit[U[_]] { def unit[A](a: A): U[A] } trait Bind[M[_]] { def bind[A, B](ma: M[A], f: A => M[B]): M[B] } case class Monad[M[_]](u: Unit[M], b: Bind[M]) object Monad { val listMonad = Monad[List](new Unit[List] { def unit[A](a: A) = List(a) }, new Bind[List] { def bind[A, B](ma: List[A], f: A => List[B]) = ma flatMap f }) def sequence[M[_], A](m: Monad[M], as: List[M[A]]): M[List[A]] = as match { case Nil => m.u.unit(Nil) case x :: xs => m.b.bind(x, (y: A) => m.b.bind(sequence[M, A](m, xs), (ys: List[A]) => m.u.unit(y::ys))) } def listSequence[A](as: List[List[A]]) = sequence[List, A](listMonad, as) def optionSequence[A](as: List[List[A]]) = sequence[Option, A](optionMonad, as) // etc. etc. O(n)! }
As you can see, I was being very nice when I converted the argument to Haskell. The argument against such a proposal becomes even stronger in the context of Scala.
To my opponent, thanks for the discussion; it was fun and the intellectual maturity is admirable 
Here is the Applicative functor type-class (see Applicative Programming with Effects, Conor McBride, Ross Paterson):
class Applicative f where pure :: a -> f a (<*>) :: f (a -> b) -> f a -> f b
Here are the laws for the Applicative functor type-class:
pure id <*> u == upure (.) <*> u <*> v <*> w == u <*> (v <*> w)pure f <*> pure x == pure (f x)u <*> pure x == pure (\f -> f x) <*> uHere are those laws stated using Reductio. I have changed pure to unit and the language is Scala:
object ApplicativeLaws { def identity[A[_], X](implicit a: Applicative[A], aax: Arbitrary[A[X]], e: Equal[A[X]]) = prop((apx: A[X]) => apx === a(a.unit((x: X) => x), apx)) def composition[A[_], X, Y, Z](implicit a: Applicative[A], aayz: Arbitrary[A[Y => Z]], aaxy: Arbitrary[A[X => Y]], aax: Arbitrary[A[X]], e: Equal[A[Z]]) = prop((apyz: A[Y => Z], apxy: A[X => Y], apx: A[X]) => a(apyz, a(apxy, apx)) === a(a(a(a.unit((f: Y => Z) => (g: X => Y) => f compose g), apyz), apxy), apx)) def homomorphism[A[_], X, Y](implicit a: Applicative[A], ax: Arbitrary[X], axy: Arbitrary[X => Y], e: Equal[A[Y]]) = prop((f: X => Y, x: X) => a(a.unit(f), a.unit(x)) === a.unit(f(x))) def interchange[A[_], X, Y](implicit a: Applicative[A], ax: Arbitrary[X], apxy: Arbitrary[A[X => Y]], e: Equal[A[Y]]) = prop((f: A[X => Y], x: X) => a(f, a.unit(x)) === a(a.unit((f: X => Y) => f(x)), f)) }
Pretty neat eh? Let’s test the Applicative instance for List:
List(identity[List, Int], composition[List, Int, Long, String], homomorphism[List, Int, String], interchange[List, Int, String]). foreach(p => summary println p)
This runs 100 unit tests per property, so 400 unit tests altogether. Here is the output:
OK, passed 100 tests. OK, passed 100 tests. OK, passed 100 tests. OK, passed 100 tests.
Woot woot!
Runar recently made mention of these so-called Functors and Monads in his excellent post about concurrency/actors in Java. There are all sorts of tutorials out there for understanding what a Monad is, however, I am of the opinion that one must first understand what a Functor is. This is because it is less complex and more general (all monads are functors plus more).
The Java Posse also made a couple of false claims about Runar’s article, but one in particular needs addressing. This is the notion that a functor is applicable to “Functional Programming”. This is false. A functor is applicable to programming. You really, really need to understand what a functor is, if you’re ever going to be skilled in any type of programming; even if it’s just Java web applications for the rest of your life. This concept does not exist ‘on the other side of the fence’ in the imaginary ‘functional programming world’. These suggestions are understandable of course and I don’t intend to labour the point — only make this point clear, since these apparent divides seem to pop up often. On with the story…
In Java, we have an interface called CharSequence. A few things can be said about CharSequence. How about:
All implementations guarantee that for some integer
n, then ifn >= 0 && n < length(), thencharAt(n)will not throw an exception.
We might call this a law about CharSequence that all implementations must satisfy. We could even find other laws that must satisfy about implementations of the CharSequence interface.
A Functor is an interface and it has two laws. Sadly though, this interface cannot be expressed using Java’s type system — it is simply not clever enough. We must use a hypothetical Java to express it. First though, we have to make up for Java’s missing first-class functions by using an interface. This is easy:
interface Function<A, B> { B f(A a); }
OK, so this a just an interface like any others. It needn’t satisfy any laws; it just takes an argument (A) and returns (B). We could write bazillions of implementations of this interface in Java. We’re going to need this interface to write the Functor interface.
Now, the missing part of Java is called higher-kinds — a term you needn’t concern yourself with too much. I hope this hypothetical syntax is enough to make the point clear:
interface Functor<E<_>> { <A, B> E<B> fmap(Function<A, B> f, E<A> fa); }
So the foreign part here is E<_>. Consider E to stand for ‘Environment’. It is a type parameter that takes yet another type parameter (which is why it is denoted E<_>). This means I could use List or Set, but not Integer as the type parameter value for E, since List and Set take another type parameter while Integer does not. You might think of the Functor interface as ‘applying the given function within the environment’.
We might write an implementation like this:
class ListFunctor implements Functor<List> { public <A, B> List<B> fmap(Function<A, B> f, List<A> list) { // todo: apply the given function on all elements in 'list' and return the result } }
In general discussion, we would call this the list functor, simply because the value for the environment has been applied. In Runar’s article, he was talking about the Callable functor; yet another environment. There are many possibilities for the environment here; List and Callable are but two.
Let us not forget the laws Just like all implementations of CharSequence have laws to obey, so do all functors. They are called identity and composition.
Remember the Function interface? Here is an implementation:
class Identity<A> implements Function<A, A> { public A f(A a) { return a; } }
If we are given an implementation of Functor — which I will call f — then it must satisfy f.fmap(new Identity is equivalent to x (for any value of x). So that’s the identity law out of the way. Mapping the identity function across a functor yields the same value.
The law of composition is a little less friendly when it comes to expressing it in Java so I will refrain While it is an important part of making up the concept of a functor, it may be best to defer this final piece of the puzzle for now.
For completeness, I will state the law using a shorter syntax, but if this is foreign or worrying, then please ignore it: f.fmap(a compose b, x) is equivalent to f.fmap(a, f.fmap(b, x)) (for any value of a, b and x — a and b are Function objects).
That’s all there is to a Functor. If you use the map function on lists or perhaps the map method on scala.Option, then you are using one specific instance of a functor, since these functions/methods satisfy the conditions for a functor. Even throwing an exception is using a specific functor! Perhaps that can be explained another time
I should also add that when referring to a functor (unqualified), we are referring to a covariant functor. Other types of functors include contra-variant and invariant functors. We can talk about those another day
Next: Just What the Flip is a Monad?
Questions?
In the spirit of yesterday’s post that denoted the Functor Laws using Reductio, I will also give the Monad Laws. Before I do however, here is an example use of the FunctorLaws object that runs 600 unit tests when testing a Functor implementation for scala.Option[A], scala.List and finally, for the scala.Either[A, _] functor just to make it a bit quirky and probably confuse a few of you (in that case, ignore it for now!)
val prop_OptionIdentity = identity[Option, Int] val prop_OptionComposition = composition[Option, Int, String, Long] val prop_ListIdentity = identity[List, Int] val prop_ListComposition = composition[List, Int, String, Long] val prop_EitherIdentity = identity[Apply1Of2[Either, String]#Apply, Int] val prop_EitherComposition = composition[Apply1Of2[Either, String]#Apply, Int, String, Long] // OK passed 100 tests. (appears 6 times — once per property)
…and the obligatory Monad Laws follow (import statements omitted this time, but they are the same as previous)…
object MonadLaws { def leftIdentity[M[_], A, B](implicit m: Monad[M], am: Arbitrary[M[B]], aa: Arbitrary[A], ca: Coarbitrary[A]) = prop((a: A, f: A => M[B]) => m.bind(f, m.unit(a)) === f(a)) def rightIdentity[M[_], A](implicit m: Monad[M], am: Arbitrary[M[A]]) = prop((ma: M[A]) => m.bind((a: A) => m.unit(a), ma) === ma) def associativity[M[_], A, B, C](implicit m: Monad[M], am: Arbitrary[M[A]], ca: Coarbitrary[A], cb: Coarbitrary[B], amb: Arbitrary[M[B]], amc: Arbitrary[M[C]]) = prop((ma: M[A], f: A => M[B], g: B => M[C]) => m.bind(g, m.bind(f, ma)) === m.bind((a: A) => m.bind(g, f(a)), ma)) }
Woot! Woot!
A somewhat intricate and extremely useful code snippet using Reductio for testing the laws of any Functor instance (note that the Functor type is part of Scalaz):
import reductios.Property._ import reductios.Arbitrary import reductio.Coarbitrary import reductios.Arbitrary._ object FunctorLaws { def identity[F[_], A](implicit f: Functor[F], af: Arbitrary[F[A]]) = prop((fa: F[A]) => f.fmap((a: A) => a, fa) === fa) def composition[F[_], A, B, C](implicit f: Functor[F], af: Arbitrary[F[A]], ac: Arbitrary[C], cb: Coarbitrary[B], ab: Arbitrary[B], ca: Coarbitrary[A]) = prop((fa: F[A], h: B => C, i: A => B) => f.fmap(h compose i, fa) === f.fmap(h, f.fmap(i, fa))) }
Many people struggle to understand those fluffy things called Monads and why they are important. I’m not going to attempt to alleviate this to a large degree, but I have had a recent success with a friend in having them attempt to write a familiar Scala function as a method. That is, the List.flatten function, which simply takes a List of List of some type A and returns a List[A]. It does this by concatenating all the lists together. I think most people are familiar with this function and have a good mental model of how it works. If this is the case and you are less confident about List.flatMap, then I hope to bring a point to your attention that might help you bring it home.
If you take a look at List.sort, you see it takes a function (A, A) => Boolean. This is because the type parameter to List is ‘just any A’. It would be nice if it was ‘any A, so long as it has defined order’. That way, you can just call list.sort and be done with it. This would require the creation of a new class with a more restricted type parameter; for example, you might pass the function at list creation time, like you do with a TreeMap.
Imagine writing List.flatten on the List[A] class as a method using the same technique. You wouldn’t be able to, since the method belongs on a List[List[A]]. You’d need to write the method such that it takes an argument: A => List[A] before you could then call flatten. When you have a List[List[A]], you’d just call this method with the identity function x => x to obtain your resulting List[A]. Here is how the method would look:
def flatten(f: A => List[A]): List[A] = ...
Guess what?! This method is flatMap! Let’s ignore the fact that the Scala API is significantly broken, including the List.flatMap method using Iterable in place of List here. Notice though, that flatMap is actually generalised by taking another type parameter, so we have just invented an unnecessarily specialised version of flatMap. Let’s fix it:
def flatten[B](f: A => List[B]): List[B] = ...
Woot woot! In other words, flatten(list) is equivalent to list flatMap (x => x). Furthermore, this should hold for more than just list, but for other type constructors too (sadly, Option is missing a flatten function: Option[Option[A]] => Option[A]). This is a special relationship that all monads have (join is a synonym for flatten and bind is a synonym for flatMap):
join = bind id
We can express this using Reductio (the Scala API of course!):
val prop_flat = prop((t: List[List[Int]]) => List.flatten(t) == t.flatMap(x => x)) // OK passed 100 tests.
I hope this helps. If it doesn’t, ask a question or ignore my ranting
From http://www.news.com.au/comments/0,23600,23907216-462,00.html on the recent price rise by ABC Learning Centres (i.e. child care):
ABC Learing centres have now increased there fees three times since early 2007. There justification for these raises in no way benefit the children in they’re care or they’re staff!.
The Applicative Functor pattern is an incredibly powerful abstraction. I recently added it to a branch of Scalaz. However, it would be nice if I could alter the fixity of functions so that the parentheses below are not required to make the expression right-associative.
val add = (a: Int) => (b: Int) => (c: Int) => a + b + c val none: Option[Int] = None // Grrr Scala // Some(24) println(Some(7) <*> (Some(8) <*> (Some(9) > add))) // None println(Some(7) <*> (none <*> (Some(9) > add))) // List(87, 88, 89, 91, 92, 93) println(List(1, 2, 3) <*> (List(77) <*> (List(9, 13) > add)))
Having to write that silly none value is annoying too. At the very least a none function would suffice:
def none[A]: Option[A] = None
That way. I could use none[Int] and be done with it.
Still, this pattern is a nice tool to use and I will surely be using it in the future.
When disciplined programmers write unit tests, they often make reference to the fact that their tests provide a means of documentation the software that it is testing. This documentation is more appropriate than what would otherwise be informal and potentially ambiguous comments using English. Take the simple example of adding two numbers. We might document using informal language:
/**
* Adds the two arguments.
*
* @param a Add this argument to the other one.
* @param b Add this argument to the other one.
* @return The sum of the two arguments.
*/With unit tests, we might instead write something more formal and unambiguous:
assertEqual(add(2, 2), 4) assertEqual(add(4, 3), 7) ... so on
It might be argued that both these forms of documentation complement each other. After all, while the unit tests have less room for misinterpretation, they are incomplete; for example, what about add(88, 37)? The English description makes up for this shortcoming.
We could reword our English to be a little more succinct:
/**
* Passing 0 as one argument returns the other argument,
* otherwise, the result is the same as subtracting 1 from one argument and
* adding 1 to the other argument then passing those values instead.
* e.g. add(2, 8 ) is the same as add(1, 9) and so on until one of the arguments reaches 0.
*/Wouldn’t it be nice if we could express this formally in unit tests? You can, read on.
While this example is trivial, it scales in proportion to the amount of discipline that the programmer is willing to exercise by controlling side-effects in their program. If we write our programs such that most of our methods retain the property of referential transparency, we can use this advanced method of tests as documentation. When we refactor our code to make tests easier to write, it is often the case that we are doing exactly this anyway. Win win!
We’ll give a slightly less trivial example next, but not so trivial that it takes away from the important points. In fact, let’s unit test a specific part of the Java Collections library — the java.util.Collections.reverse method. There are various ways of testing this method and we will choose one here that serves to illustrate the point of unit tests as documentation.
The reverse method can be described as follows:
(a.append(b)).reverse() == b.reverse().append(a.reverse())It is an interesting observation here that we have completely specified the reverse method. That is, under some reasonable assumptions, it is not possible to write a method that is not equivalent to reverse that also satisfies our statements above. This is the ultimate form of code documentation!
We will ignore the first statement for the sake of interest and verbosity and focus on expressing the other two. This is because statements 2 and 3 have free variables, while statement 1 is merely an assertion that does not illustrate any interesting points. Let us start with the second statement and articulate it using Reductio:
Property p2 = property(arbInteger, new F<Integer, Property>() { public Property f(Integer i) { return prop(single(i).equals(reverse(single(i)))); } });
That pretty much sums up statement 2 doesn’t it? What about statement 3:
Property p3 = property(arbLinkedList(arbInteger), arbLinkedList(arbInteger), new F2<LinkedList<Integer>, LinkedList<Integer>, Property>() { public Property f(LinkedList<Integer> a, LinkedList<Integer> b) { final LinkedList<Integer> x = reverse(append(a, b)); final LinkedList<Integer> y = append(reverse(b), reverse(a)); return prop(x.equals(y)); } });
Yep. Notwithstanding the absence of statement 1, we have completely specified the behaviour for the Java Collections.reverse method. We have exhaustive and formal documentation instead of one or the other as we traditionally do. What an improvement!
That’s not hard either. How many unit tests do you want to run? By default, Reductio will run 100 unit tests per Property declaration. You can adjust this and various other factors about how your unit tests are executed. If you want to take the default, then a few more lines of code are enough to do just that:
list(p2, p3).foreach(new Effect<Property>() { public void e(Property p) { summary.println(p.check()); } });
If you run this line of code, you will see the result of your 200 unit tests on the standard output:
OK, passed 100 tests. OK, passed 100 tests.
Is that too magical for you? Don’t believe me? Want to see it fail? OK, let’s fail it. In the expression of statement 3, change the line b.addAll(a) to a.addAll(b) and run again. What did you see? Here is what I saw:
OK, passed 100 tests. Falsified after 4 passed tests with arguments: [[3, 2, -3, 4, -3],[2, -3, 4, -3]]
Yep, it failed alright When those two list values are used as our free variables, the property is false and the unit test fails.
import fj.Effect; import fj.F; import fj.F2; import static fj.data.List.list; import static reductio.Arbitrary.arbInteger; import static reductio.Arbitrary.arbLinkedList; import static reductio.CheckResult.summary; import reductio.Property; import static reductio.Property.prop; import static reductio.Property.property; import java.util.Collections; import static java.util.Collections.singletonList; import java.util.LinkedList; public class ListReverse { public static void main(String[] args) { Property p2 = property(arbInteger, new F<Integer, Property>() { public Property f(Integer i) { return prop(single(i).equals(reverse(single(i)))); } }); Property p3 = property(arbLinkedList(arbInteger), arbLinkedList(arbInteger), new F2<LinkedList<Integer>, LinkedList<Integer>, Property>() { public Property f(LinkedList<Integer> a, LinkedList<Integer> b) { final LinkedList<Integer> x = reverse(append(a, b)); final LinkedList<Integer> y = append(reverse(b), reverse(a)); return prop(x.equals(y)); } }); list(p2, p3).foreach(new Effect<Property>() { public void e(Property p) { summary.println(p.check()); } }); } static <A> LinkedList<A> single(A a) { return new LinkedList<A>(singletonList(a)); } static <A> LinkedList<A> reverse(LinkedList<A> as) { LinkedList<A> aas = new LinkedList<A>(as); Collections.reverse(aas); return aas; } static <A> LinkedList<A> append(LinkedList<A> as1, LinkedList<A> as2) { LinkedList<A> aas = new LinkedList<A>(as1); aas.addAll(as2); return aas; } }