Overview of Functional Programming

The developer community seems to be in the midst of a paradigm shift, moving away from object oriented programming (OOP) principles and toward functional programming (FP) principles. We’re at the beginning of this shift. I have seen a number of job postings out there saying they’d like FP experience but would accept someone who wanted to learn.

My intention in this blog series is to explain how to think about this shift by describing the main ways we will need to adapt. In subsequent posts, I will introduce you to a few of the significant FP tools that look to me to be the right horses to bet on, namely Phoenix and Elixir as an alternative to Ruby on Rails and Elm as an alternative to JavaScript. Although not a pure FP tool, React.js, especially when used in conjunction with Redux, will be discussed as well. Rest assured, there are many other FP options out there like Haskell, Scala, and Clojure to name a few, so don’t hesitate to check those out too.

For this first post, let's get into the main things that set FP apart.

• Usage of functions as input to and output from other functions, higher order functions

• Usage of map, filter, and reduce type functions instead of looping

• Immutable state

• Recursion in place of looping

• Composing functions from other functions

• Distinguishing “pure” functions from functions with side effects

There are other features of FP, like parametric polymorphism or monads, which strike me as less core and also generate more debate. I will stick to the core here so we can get our feet wet.

The paradigm is called functional programming largely because functions can return functions, and functions can consume functions. Add to that the idea of chaining functions together allowing function composition, and things are looking pretty darn functional.

First, a trivial example to demonstrate how it works:

 // return a function which can be used to build other functions
function addValue(valueToAdd) {
    return function(valueThatGetsAddedTo) {
        return valueToAdd + valueThatGetsAddedTo;
    };
}
function add2() {
    return addValue(2);
}
function add3() {
    return addValue(3);
}
add2()(7) // returns 9
add3()(7) // returns 10 

The addValue function returns another function, which will have a hard coded number to add. It is used to create the functions add2 and add3, which do the actual arithmetic. Now I will give a complex example so you can get an idea of why this is powerful.

I have a pet project that I have implemented in Ruby, Objective-C, Java, Swift, and most recently Elm. In my career as a consultant, I often need to pick up new languages and development environments, and I’ve found it handy to reimplement my pet project each time. That way I can focus on how to accomplish nontrivial tasks in the new environment, but I don’t have to spend time designing.

My pet project is called Wounds. It’s essentially the game of chess, with the addition of the ability for pieces to get wounded instead of getting captured. I will be using this project in subsequent blog posts in this series to demonstrate concepts in Elm and React/Redux/React Native.

Here’s what the Wounds game board looks like:

Following are two versions of a function for generating the legal moves for a single piece: first, some Java code for the Android version and then some FP code in Elm for the web version.

This is not a comparison of how many lines of code each of these takes. They could be quite a bit more terse. Nor is this a complaint that FP tools are lacking in Java. I wrote the Java implementation before I started looking into FP and also before playing around with map, filter, and reduce. A lot of languages have FP tools like Lambda functions, and the Java example could certainly be coded more in an FP style.

Notice that the pieces look like diagrams of their movement capabilities. They are made up of individual prongs that represent individual abilities. These prongs can be broken off, resulting in a wound. When a prong is broken off, the piece loses that movement ability.

Below is the Java code. If you are more comfortable with Objective-C or Ruby, see these code examples on GitHub.

 public ArrayList<Move> generateLegalMoves(int x, int y, Board
                        board, Player player, int fromIndex)
{
  ArrayList<Move> generatedMoves = new ArrayList<Move>();
  if(board.squares.get(fromIndex) != null)
  {
      Man man = board.squares.get(fromIndex);
      if(man.player == player)
      {
          for(Ability ability:man.abilities)
          {
              int dest_x = x + ability.delta_x;
              int dest_y = y + ability.delta_y;
              int dest_index =
            board.indexFromXY(dest_x, dest_y);
              if(!ability.slide) // slide is like a bishop, rook, or queen
              {
                  if(board.isOnBoardXY(dest_x, dest_y))
                  {
                      Move move = new Move();
                      move.attacking_man = man;
                      move.from_x = x;
                      move.from_y = y;
                      move.to_x = dest_x;
                      move.to_y = dest_y;
                      boolean addThisMove = false;
                      if(board.squares.get(dest_index) != null)
                      {
                          addThisMove = true;
                      }
                      else
                      {
                          if(board.friendlyPiece(dest_index, player))
                          {
                              addThisMove = true;
                              move.defending_man =
                        board.squares.get(dest_index);
                          }
                      }
                      if(addThisMove)
                      {
                          generatedMoves.add(move);
                      }
                  }
              }
              else // it’s a slide, like a bishop, rook, or queen
              {
                  boolean ranIntoAnEnemy = false;
                  while(board.isOnBoardXY(dest_x, dest_y) &amp;&amp;
            !board.friendlyPiece(dest_index, player)
                &amp;&amp; !ranIntoAnEnemy)
                  {
                      Move slideMove = new Move();
                      slideMove.attacking_man = man;
                      slideMove.from_x = x;
                      slideMove.from_y = y;
                      slideMove.to_x = dest_x;
                      slideMove.to_y = dest_y;
                      if(board.enemyPiece(dest_index, player))
                      {
                          ranIntoAnEnemy = true;
                          slideMove.defending_man =
                    board.squares.get(dest_index);
                      }
                      generatedMoves.add(slideMove);
                      dest_x += ability.delta_x;
                      dest_y += ability.delta_y;
                      dest_index = board.indexFromXY(dest_x, dest_y);
                  }
              }
          }
      }
  }
  return generatedMoves;
}

Let’s see how this looks in Elm. First, we create a function that can append a move to the move list if it’s legal. I won’t explain Elm’s syntax here except to say that local constants are defined in the let block at the top. It’s not important to understand the Elm code here, just that the function returns a list of legal moves.

 addMoveToList : Ability -> Board -> Int -> Man -> List Move -> List Move
addMoveToList ability board index man moveList =
  let
    file = (rem index board.width)
    rank = (index // board.width)
    toFile = file + ability.xOffset
    toRank = rank + ability.yOffset
    defendingMan = getMan board toFile toRank
    defendingAbility = Man.getDefendingAbility defendingMan ability
    nextIndex = (toRank * board.width) + toFile
    isLegalMove board toFile toRank man defendingMan =
      (toFile >= 0) &amp;&amp; (toFile < board.width) &amp;&amp; (toRank >= 0)
    &amp;&amp; (toRank < board.height) &amp;&amp; not (sameTeam defendingMan man)
  in
    if isLegalMove board toFile toRank man defendingMan then
      if (ability.abilityType == Slide) &amp;&amp; (defendingMan == Nothing) then
        moveList ++ [Move file rank toFile toRank man defendingMan
        ability defendingAbility]
        ++ addMoveToList ability board nextIndex man moveList
      else
        moveList ++ [Move file rank toFile toRank man defendingMan
        ability defendingAbility]
    else
      moveList — move was illegal, so return the list unchanged

Elm has the concept of Maybe, which is “maybe” the most difficult part of learning the language. If a value can be null or undefined, then it has a type of Maybe. But not just Maybe by itself. Notice below we have a value of Maybe Man.

This function, generateLegalMovesForPiece, gets called from a function that doesn’t know if a square is occupied. The square maybe has a man in it (or not). To get the real man, if there is one, you need a case statement like the one below. If there’s a real man, the case Just maybeMan -> will be the execution path.

Note the other path, _ ->, which is a catchall default. The underscore refers to a parameter that will not be used. In that situation, we return an empty list. Even though the calling code will never pass an empty square, so this branch will never get executed, Elm requires that all branches be addressed. This is in keeping with Elm’s airtight architecture.

The first (optional) line declares the type signatures for the function. The second line actually declares it, naming the parameters so they can be referenced. Also note the syntax of the lambda (anonymous) function, enclosed in parentheses and beginning with a back slash, which is supposed to look kind of like a Greek lambda character. ability is the input param, then the code to the right of -> is the actual function. After the lambda is the List param, man.abilities, that List.map will operate on.

 generateLegalMovesForPiece : Board -> Maybe Man -> Int -> List Move
generateLegalMovesForPiece board maybeMan index =
  case maybeMan of
    Just maybeMan ->
      let
        man = maybeMan
        moveList = []
        moveListList = List.map
        (\ability -> addMoveToList ability board index man moveList)
        man.abilities
      in
        List.concat moveListList
   _ ->
      []

I had to play a few games that I will later refactor. The function addMoveToList has to have a consistent return value. So I can’t have a function that returns a move if the move is legal and nothing if it’s not. So I use a kluge. I pass an empty list into the function and then return that list either empty or with a legal move. Then I use the function List.concat moveListList to concatenate the resulting list of lists.

This is not good functional programming.

The main point here is that instead of having a loop construct, which cycles through the Man’s Abilities, we have a call to List.map, which operates on each ability in the list. Note that the input list is a list of type ability, and the output list is of type move.

!Sign up for a free Codeship Account

A common example of state would be whether or not a user is logged in. I am used to thinking that I have a variable somewhere that holds this state. When a user logs in, I set it to true. When they log out again, I set it to false.

In functional programming, this is a no-no. The closest I can come is to return a modified copy of state from a function. Some other function, maybe the header that gets displayed at the top of the page, will consume this result. I found this FP concept the most challenging because it seems like magic that you don’t have the state tucked away somewhere. It’s as if it is a ball being juggled. I will extoll the virtues of this in detail in Part II of this series.

In C-style languages (C, C++, Java, JavaScript, C#), you see things like this:

 for(i = 0; i < sizeof(array); i++) {
  array[i] = array[i] * 2;
}

The looping variable i is mutable. FP tends to avoid this construct altogether. Here’s an example of an FP looping construct from the Elixir website:

 defmodule Recursion do
  def print_multiple_times(msg, n) when n <= 1 do
    IO.puts msg
  end
  def print_multiple_times(msg, n) do
    IO.puts msg
    print_multiple_times(msg, n - 1)
  end
end
Recursion.print_multiple_times("Hello!", 3)
# Hello!
# Hello!
# Hello!

Admittedly, this example suffers from example-itis: it looks unnecessarily complicated and verbose while failing to make the case for being a useful technique. What I have discovered is that the FP way of doing this required some trust on my part, and then a paradigm shift, and now it feels like a powerful tool where I get to express what I want done, instead of the little steps required to do it.

But I think you have to play around with it before you fully grasp the power of it. This practice is so well accepted in FP circles that many FP languages don’t have keywords for loops such as while or until. It is more common to gather a list of items and call a function that operates on each of them, such as map, filter, or reduce.

In keeping with the immutable state requirement, map takes a list as input and transforms each item to return a new modified list. filter returns a new list where the items fulfill a given condition, and reduce aggregates the list into a single return value.

Be on the lookout for my next post which will include:

• Better (but more complicated) examples of the benefits of immutable state and recursion using the AI code from Wounds

• Composing functions from other functions

• Distinguishing “pure” functions from functions with side effects