How should the paradigm shift associated with functional programming be approached?

Question

As a student primarily experienced with imperative and object-oriented languages, my first few hours learning Haskell at university were a bit of a struggle. There's a real shift involved in terms of how you approach problem solving and concepts like pure functions, side effects, currying, higher order functions etc. were very new to me and took me a while to properly grasp and begin using.

I did eventually get the hang of it, and now happily write production code in Scala that uses a lot of these techniques. I think it can result in incredibly elegant code.

But I'm curious: is there is a way to make the initial struggle easier? I've seen some suggestions that students should start with a functional language - but I don't think it's reasonable to assume all of the students won't have prior knowledge of working in an imperative language.

Answer 1

Any true paradigm shift requires literally re-wiring the brain. Thinking functionally is not the same as thinking procedurally (for example). The neural pathways of the brain need to be connected appropriately for the new paradigm to become natural. When you were a kid you were, if typical, used to walking and running. Then you probably got a bicycle (or a skateboard if you are young enough). You tried, you fell down, you tried again. Your brain got used to the subtle balancing required. Swimming - same deal. Differentiation - same deal. Haskell - same deal.

As an instructor, the above implies that you should provide guided practice at the beginning - a skateboard park for the mind. If your students solve a lot of simple problems (not syntactical, but logical) they will skin their knees on these but if they are well chosen will get the skills. In scheme, reversing a list with only head and tail is simple enough. Doing it in linear time takes a bit more skill, but the technique is both cool and satisfying. Writing the code wires the brain. And, like riding a bicycle, it is hard to un-learn it once you get it, since the brain is now different.

So, make it possible for the students to fall a lot, but to get up without getting discouraged.

To add a bit of specificity to this. Assuming you know the paradigm well yourself, what are its 100 most important techniques? Can you come up with a 10-30 minute exercise for each of them? Try to have each exercise focus on just one thing (mostly anyway). These are your Etudes. Can you come up with 10 exercises for each of the 100 techniques, even if they vary only slightly?

Acknowledgement: At SIGCSE 2004, Owen Astrachan (of Duke) convinced Microsoft Research, through Jane Prey, to give every attendee the book The Art of Changing the Brain by James E Zull.

Answer 2

In response to comments on the other answer, I'll take a C running example:
To detect whether an unsigned number x is a power of 2.

• Using ideas from FP to move from one version to next
• Entirely staying within C as coding language

The Base C version

#define even(x) (((x) & 0x1) == 0)
int ip2(unsigned x)
{
  if (x==0) return false;
  while (even(x) && x > 1)
    x >>= 1;
  if (x == 1)
    return true;
  else
    return false;
}

a. Recursive Version

int ip2a(unsigned x)
{
  if (x==0) return false;
  if (x==1) return true;
  if (even(x))
    return ip2a(x>>1);
  else
    return false;
}

b. Eliding the zero check

The zero case is odd and special; we'll come back to it later

int ip2b(unsigned x)
{
  if (x==1) return true;
  if (even(x))
    return ip2b(x>>1);
  else
    return false;
}

c. Transforming if-else to ?:

Identity

if C
  return a;
else
  return b;

is equivalent to

  return C ? a : b;

int ip2c(unsigned x)
{
  if (x==1) return true;
  return even(x) ? ip2c(x>>1) : false;
}

d. Using identity connecting ?: to &&

Identity
For boolean a, b, a ? b : false $\equiv$ a && b

int ip2d(unsigned x)
{
  if (x==1) return true;
  return even(x) && ip2d(x>>1);
}

e. Remove C 'laziness'

Can we functionalize this further?
Notice that I've done the C programmer's typical laziness of avoiding writing an else clause
Reintroducing

int ip2e(unsigned x)
{
  if (x==1)
    return true;
  else
    return even(x) && ip2e(x>>1);
}

f. Re-apply if to ?: transformation

This seemingly more complex as in nested version is again amenable to the transformation above. [There's a lesson here!]

int ip2f(unsigned x)
{
   return x==1 ? true : even(x) && ip2f(x>>1);
}

g. Using identity connecting ?: to ||

Identity
Analogous to the ?: to && we have for ||
For boolean a, b, a ? true: b $\equiv$ a || b

int ip2g(unsigned x)
{
   return x==1 || even(x) && ip2g(x>>1);
}

Verbalization

Notice how smoothly this verbalizes: For x to be a power of 2

• Either x is 1 (trivial case)... Or...
• x is even and its half is also a power of 2

h. Stop??

At this stage we could stop...
But this is an infinite loop for x==0!!
(We removed the zero check earlier remember??)

int ip2h(unsigned x)
{
  return x == 0 ? false : (x==1 || even(x) && ip2h(x>>1));
}

i. Again ?: to &&

int ip2i(unsigned x)
{
  return x == 0 && (x == 1 || even(x) && ip2i(x>>1));
}

So...???

Q: So are you SERIOUSLY suggesting this way of writing ip2?!?

A: No this is not a serious suggestion of ip2.
Nor is it a serious suggestion of recursion. It is a serious suggestion of

• how to use algebraic identities to transform programs into other equivalent programs
• And of giving the boolean type a more first class status. [O how I miss Pascal!]

All of which is about the possibility that whatever the language one needs to use, functional thinking is applicable.

¿Efficiency?

Yeah efficiency: This is classic KaR C No recursion; no loop;
Not just constant time; but just 3 operations!!!

int ip2KaR(unsigned x)
{
  return (x & (x-1)) == 0;
}

If you enjoy that look at the Henry Warren's book Hacker's Delight
Which is the above multiplied thousand-fold!!

But believe me: For the beginning student worrying about efficiency before basics of semantics is invariably a wrong priority!
[My minority opinion of course!]

Answer 3

Execution? Or Evaluation?

One of the most pervasive metaphors that dominates programming is the idea of execution. Programs execute, as do functions, as do the tiniest of assignment statements.

One purpose of FP is to defeat — or at least deflate — this metaphor.

The alternate metaphor that obtains in FP is evaluation. FP programs are basically calculators except that they are not over mere numbers but over arbitrarily complex data structures.

To do FP is to replace execution by evaluation.

Abstract? or Concrete?

The related flip is that whereas OOP-ers like their data structures to be abstract data types FP-ers try to keep all their data as concrete as possible.

ie the Java embarrassment that int is not a proper class is flipped into a positive and pervades the language/paradigm. If we can keep all types concrete its a Good Thing!

Lets see a session

? 1 + 3
4 : ℤ

Simple calc model like python; though notice the type

? [1,2] ++ [3,4]
[1, 2, 3, 4] : ℒ.ℤ

So the calc model applies to list data structures as to nos uniformly

? [("Eggs", 12), ("Bread", 2)]
[("Eggs",12), ("Bread",2)] : ℒ.⦇ℒ.Char, ℤ⦈

More complex; notice that strings are just lists of Char No spurious excess ontologies here!

? [("Eggs", 12), ("Bread", 2)] ++ [("PeanutButter", 1)]
[("Eggs",12), ("Bread",2), ("PeanutButter",1)] : ℒ.⦇ℒ.Char, ℤ⦈

And these more sophisticated data structures are as easily handled as the simplest; So far looks just like python

? [("Eggs", 12), ("Bread", 2)] ++ ["PeanutButter"]
ERROR: Type error in application
*** expression     : [("Eggs",12),("Bread",2)] ++ ["PeanutButter"]
*** term           : [("Eggs",12),("Bread",2)]
*** type           : ℒ.⦇ℒ.Char, ℤ⦈]
*** does not match : ℒ.(ℒ.Char)

Whoops! Type error Python etc will give the error but at a later inconvenient point

Now we move on

Expression trees

ctype Expr where
  Plus, Mul : Expr → Expr → Expr
  Lf        : ℤ → Expr

Whats the ctype?? A concrete type.
They (trees) can be constructed

• trivially as an Lf (leaf) wrapping an ℤ to give a trivial tree
• Or take two trees l and r and make Plus.l.r; Likewise Mul.l.r

What does it mean that the type is concrete?

? Plus.(Lf.2).(Lf.3)
Plus.(Lf.2).(Lf.3) : Expr

This is trivial looking but actually deep
Just as 3:ℤ SELF-EVALUATES to 3:ℤ (the trivial case of evaluation) Plus.(Lf.2).(Lf.3) : Expr self-evaluates to itself

Further just as 2+3 (non-trivially) evaluates to 5

Similarly for expression trees If we want to say that the "2+3" tree is the l-subtree of the "(2+3)*5" tree we could do

t1 = Plus.(Lf.2).(Lf.3)
t2 = Mul.t1.(Lf.5)
? t2
Mul.(Plus.(Lf.2).(Lf.3)).(Lf.5) : Expr

Finally an expression evaluator

eval.(Lf.x)     = x
eval.(Plus.l.r) = eval.l + eval.r
eval.(Mul.l.r)  = eval.l * eval.r
 
? eval.(Plus.(Lf.2).(Lf.3))
5 : ℤ
? eval.t2
25 : ℤ

In short a tree data structure in 3 lines — NO IO NO MEMORY MGMT
And the exp-evaluator (or tree-interpreter) another 3 lines!

Answer 4

Functional programming is mostly about unlearning bad habits. The best was it to not be taught them in the first place.

You don't need to teach the more advanced bits to beginners. However also don't teach mutation.

I teach python, but the examples that I give to the students have a functional style. I just avoid the bits of procedural, that should be tough much later. MUCH LATER after the student has learnt all of functional techniques.

In structure and interpretation of computer programs, we are introduced to mutation in hour 20. After lists, inheritance, lambdas, etc, …