Patterns and idioms in functional languages

fp.md

I'll throw my opinion in here, but take it with a pretty large grain of salt as I've done no professional development in a functional language yet. Just tinkering with (quite a few of) them in my spare time. Some of the patterns I spotted are irrespective of type systems (static, dynamic).

• lists, sequences or similar primitives are ubiquitous

• abstract away duplicate code using higher-order functions

• no iteration constructs, recursion is the only way to traverse lists

• watch out your recursion, be sure it's tail-recursive

• abstract over this tail-recursive pattern with a higher-order function: foldLeft or foldRight. So, know your language's equivalent of foldLeft/foldRight and prefer these over explicit recursion.

• abstract over folds in an even more general way and provide folding functions for arbitrary data structures, not just list, e.g., trees.

• provide a few convenience higher-order functions (implementable using fold) like: map, filter, any/some, all/every, zip, zipWith. These allow easier manipulation/transformation over lists.

• if the language has laziness capabilities then be sure you'll find some functions that generate lazy, infinite sequences. For example, iterate, which takes a function (f) and an initial value (a) and produces an infinite list of values following this pattern:

  [a, f(a), f(f(a)), f(f(f(a))), ...]

These generator functions prove very useful when combined with functions such as zip or zipWith.

• most of these languages don't allow side effects, like mutation, so (apparent) copying is the only way around (under the hood, the implementation will most likely not do any copying at all). Another effect of this is that you'll have a hard time seeing statements in such languages. Everything will be an expression, i.e., it has a value. What would otherwise be called an "if statement" in an imperative language is an "if expression" in a functional language.

• another consequence of not having mutability is that you have to pass state around. Whenever you want to mutate some state, you just construct a new data structure based on the one you mutate and pass it to some other function.

• because threading state around is cumbersome, you abstract over it and end up with monads. Some languages provide syntatic sugar for this (do notation and monadic comprehension in Haskell, some macros in Clojure, sequence comprehensions in Scala, computation workflows in F#).

• you abstract even more and discover monads are good not only for state (i.e. State monad), you can use them for continuations, lists, maybe values.

• data type constructors are very important, even in dynamic languages (see Clojure and Erlang). Constructing and deconstructing lists or tuples is usually very succinct, and various shortcuts are provided, like pattern matching formal parameters.

• null values are usually inexistent, so some kind of Option/Maybe data type is provided.

• prefer composition over inheritance. Here, by inheritance I mean explicit delegation to some other function. Instead of calling a function b inside a, you compose a and b into a third function c. This way, neither a, nor b know of each other, so you end up with more decoupled code. Terse syntax usually makes this a breeze, see Haskell's . operator.

• higher-order functions, together with composition and small, focused functions gives rise to combinators. You write small building blocks that can be combined in several ways to achieve a much larger, and usually complex, goal. In my opinion, monadic parser combinators are a great example of this.

• if the programming language is statically typed, it's very likely that it has a very powerful type system, so people usually try to express business logic inside the type system. For example, the type system could cover cases where some user does not have rights to access a certain area of the file system. See this presentation by Don Stewart (Haskell) and this video with Yaron Minski (Ocaml). This shouldn't be so particular to FP, but it so happens (and I forgot the reason) that statically typed FP languages have some very powerful type systems which makes this kind of task feasible.

These are my findings thus far. I'm sure I've missed many others, and even made some mistakes in what I wrote above, so please feel free to correct me. I'm still learning this stuff.