Advice on Learning "How to Think Functional"?

Question

As a newbie in functional languages (I started touching Erlang a couple of weeks ago -- the first functional language I could get my hands on).

I started to writing some small algorithms (such as left_rotate_list, bubble_sort, merge_sort etc.). I found myself often getting lost in decisions such as "should I use a helper List for intermediate result storage?" and "should I create a helper function to do this?"

After a while, I found that functional programming (bear with me if what I am talking does not make sense at all) encourages a "top down" design: i.e., when I do merge_sort, you first write down all the merge sort steps, and name them as individual helper functions; and then you implement those helper functions one by one (and if you need to further dividing those helper functions, do it in the same approach).

This seems to contradict OO design a little, in which you can start from the bottom to build the basic data structure, and then assemble the data structure and algorithms into what you want.

Thanks for comments. Yes, I want to get advice about how to "think in functional language" (just like "thinking in Java", "thinking in C++").

Answer 1

After a while, I found that functional programming […] encourages a "top down" design.

I'm not sure this is an accurate statement. I've been recently trying to teach myself functional programming, and I've found that a sort "bottom-up" style of programming really helps me. To use your example of merge sort:

• First look at the base case. How do you sort an array of 0/1 elements?
• Next, look at the base + 1, base + 2, … cases. Eventually, you should see a pattern (splitting into subproblems, solving subproblems, combining subsolutions) that allows you to write a general recursive case than eventually reaches the base case.
• Splitting into subproblems is easy, but combining the subsolutions is a bit harder. You need a way to merge two sorted arrays into one sorted array.
• Now put everything together. Congratulations, you've just written merge sort. :)

I could be misusing the term, but this feels like bottom-up design to me. Functional programming is different than object-oriented programming, but you shouldn't need to totally abandon existing design techniques when switched between the two.

Answer 2

An answer is that functional programming is to program using functions, as they are defined in mathematics (in short, side-effect free things that map values from the domain to the codomain). To actually translate that into "how to think" is the hand-waving part that is difficult to be exhaustive about, but I'll sample some of my thoughts:

1. The definition is more important than the efficiency. That is, an obviously correct implementation of a function that one can understand all of the behaviour of is better than a complex optimized one that is hard to reason about. (And should be preferred as long as possible; until there is evidence one must break this nice property.)
2. A mathematical function has no side-effects. A useful program must have side-effects. A functional programmer is aware of side effects, as a very dangerous and complicating thing, and designs the program as a bunch of functions that take output values from one side-effect and creates input values to the next side-effect.

Number one is associated with the vague: "elegant code". List comprehensions can present very succinct and mathematical-equations like definitions of functions. Just look at the quick-sort implemented with LCs. This is how I define elegance, succinct and makes all behaviours clear. Not that perl code-golf where you are most often terse and cryptic.

Number two is something that I use day to day in all programming. Divide code into functions (methods, routines, etc...) of current state that are side-effect free computations giving inputs to the next action to take (even which the next action to take is). When the value is returned, give it to a routine that performs the action that is described, then start over.

In my head I diagram an Erlang process as a state machine graph, where each vertex is a side-effect and a function whose output is which edge to chose out of the vertex. The high regard of side-effects is something the functional programming paradigm taught me. Especially in Erlang, since side-effects really matter in concurrency, and Erlang makes concurrency very available.

The same way some isolated tribes have only one word for numbers above 3, or no words for "mine"/"yours". It feels like popular languages do not have words for "this will cause a side-effect", but Functional Programming has it. It is forcing you to be aware of it all the time, and that is a good thing.

Answer 3

I found myself often getting lost in decisions such as "should I use a helper List for intermediate result storage?" and "should I create a helper function to do this?"

My advice for this: read The Little Schemer. You can follow it in Erlang. It's a good book to drill a sense of this into you.

Answer 4

After a while, I found that functional programming [...] encourages a "top down" design.

Well, it's not about "top down" or "bottom up" design really. It's about focusing on the "what" of the problem at hand, rather than the "how". When I started off with functional programming, I found that I kept recalling imperative constructs like the nested for loop in C. Then I quickly found out that trying to translate my imperative thinking to functional constructs was very difficult. I'll try to give you a more concrete example. I'll implement an equivalent program in C and Haskell and attempt to trace my thought process in both cases. Note that I've been explicitly verbose for the purpose of explanation.

In C:

#include <stdio.h>

int main(void)
{
  int i, inputNumber, primeFlag = 1;
  scanf("%d", &inputNumber);
  for(i = 2; i <= inputNumber / 2; i ++)
    {
      if (inputNumber % i == 0)
        {
          primeFlag = 0;
          break;
        }
    }
  if (primeFlag == 0) printf("False\n");
  else printf ("True\n");
  return 0;
}

Trace of my thought process:

1. Think in steps. First, accept a number from the user. Let this number be called inputNumber. scanf() written.
2. Basic algorithm: A number is prime unless otherwise proven. primeFlag declared and set equal to 1.
3. Check primeNumber against every number from 2 to primeNumber/2. for loop started. Declared a loop variable i to check primeNumber against.
4. To disprove our initial assertion that the number is prime, check primeNumber against each i. The moment we find even one i that divides primeNumber, set primeFlag to 0 and break. Loop body written.
5. After going through our rigorous checking process in the for loop, check the value of primeFlag and report it to the user. printf() written.

In Haskell:

assertPrime :: (Integral a) => a -> Bool
assertPrime x = null divisors
    where divisors = takeWhile (<= div x 2) [y | y <- [2..], mod x y == 0]

Trace of my thought process:

1. A number is prime if it has no divisors but one and itself. So, null divisors.
2. How do we build divisors? First, let's write down a list of possible candidates. Wrote down Texas range from 2 to number/2.
3. Now, filter the list, and pick out only items that are really divisors of the number. Wrote the filter mod x y == 0

I want to get advice about how to "think in functional language"

Ok, first and foremost, think "what", not "how". This can take a lot of practice to get used to. Also, if you were formerly a C/C++ programmer like me, stop worrying about memory! Modern languages have a garbage collector, and it's written for you to use- so don't even try to modify variables in place. Another thing that has personally helped me: write down English-like definitions in your program to abstract out the functions that do the heavy-lifting.

Answer 5

It’s import to get used to thinking that data can be used as code, and vice versa.

Usually you construct a program (data) using several primitive operations (folding, nesting, threading, distributing, ..., and some are generalized inner product, outer product, etc.), and use this program (data) to manipulate other data.

After a while, I found that functional programming […] encourages a "top down" design.

I agree.