Functional programming is a hot topic these days, one that I’ve become increasingly interested in over the last two years. One marker of its rising popularity is the publication of books on how to do FP in mainstream languages such as Python and Javascript.
While it seems worthwhile to adopt FP concepts and get their benefits wherever you can, these approaches inevitably run up against the fact that you need certain language features in order for FP to work smoothly in practice. In other words, there is functional programming as a paradigm, and there are functional languages, which provide crucial features that make the paradigm actually work effectively in the real world.
I’ve been gradually understanding this better while learning Scala. If, like myself, you’re a newcomer to functional languages, here are three prominent features that illustrate what I mean by things that a full-fledged functional language provides.
1) Lists: This data structure, implemented as a linked list, is a staple of functional languages. And since you use it everywhere, it’s important to understand its performance characteristics: appending to a list takes n time (where n is the size of the list) whereas prepending takes constant time; retrieving an element at index i takes i iterations over the nodes in the list; etc.
Coming from other languages, it might seem weird that the linked list (rather than the fixed-length array) plays such a prominent role, but the reason is that it’s great for iterative recursion: you process the “head” or first element of the list, and recursively call your function with the “tail” or the remaining elements in the list. A linked list makes this head/tail pattern very fast, because it avoids having to make a copy of the list on each recursive call: retrieving the list’s tail only requires advancing a memory pointer.
More broadly, because data is immutable in pure FP, a language needs persistent data structures so that when you manipulate those data structures, you avoid making unnecessary copies in memory. This isn’t a problem in the imperative paradigm, where mutating data is the norm.
2) Tail call optimization: Scala and other functional languages implement tail call optimization: if a function returns a recursive call to itself, it does not grow the call stack for each iteration. Since the result of the very last call will be the result of the first call in the recursive chain, it can safely circumvent the stack.
This is a crucial optimization. A problem with deep recursion is that you run the risk of overflowing the call stack. Without this language feature, deeply recursive code will crash.
3) Lazy evaluation: the ability to lazily evaluate functions allows you to do some very powerful things, such as create infinite data structures and invent custom control structures. A mechanism for lazy evaluation avoids having to jump through hoops to accomplish the same thing.
If you look through Functional Python Programming (which is a very good book), it addresses the fact that Python lacks the above features, and offers some options for simulating them or working around them somehow. To newcomers, such discussions and tricks can be a little confusing, because it’s hard to grasp why the lack of these features is a shortcoming in the first place.
This is why I think it’s best for people new to FP to approach learning Scala as a functional language. When I initially tried to learn it through resources and books that aimed to cover the language and API comprehensively, it was simply bewildering. But learning Scala through the lens of FP concepts and the features needed to support those concepts makes it much easier to understand why many of the seemingly odd constructs and idioms exist.
(As a footnote, this is exactly the approach taken by Martin Odersky’s Coursera course, “Functional Programming Principles in Scala”. I’m nearly done going through the lectures, and I think it’s a much better resource than any book I’ve perused.)