How do you design a functional program?

Question

From day 1 of my programming career, I started with object-oriented programming. However, I'm interested in learning other paradigms (something which I've said here on SO a number of times is a good thing, but I haven't had the time to do). I think I'm not only ready, but have the time, so I'll be starting functional programming with F#.

However, I'm not sure how to structure much less design applications. I'm used to the one-class-per-file and class-noun/function-verb ideas in OO programming. How do you design and structure functional applications?

Answer 1

Given that modern functional languages (i.e. not lisps) by default use early-bound polymorphic functions (efficiently), and that object-orientation is just a particular way of arranging to have polymorphic functions, it's not really very different, if you know how to design properly encapsulated classes.

Lisps use late-binding to achieve a similar effect. To be honest, there's not much difference, except that you don't explictly declare the structure of types.

If you've programmed extensively with C++ template functions, then you probably have an idea already.

In any case, the answer is small "classes" and instead of modifying internal state, you have to return a new version with different state.

Answer 2

Read the SICP.

Also, there is a PDF Version available.

Answer 3

Functional programming is a different paradigm for sure. Perhaps the easiest way to wrap your head around it is to insist that the design be laid out using a flow chart. Each function is distinct, no inheritance, no polymorphism, distinct. The data is passed around from function to function to make deletions, updates, insertion, and create new data.

Answer 4

You might want to check out a recent blog entry of mine: How does functional programming affect the structure of your code?

At a high level, an OO design methodology is still quite useful for structuring an F# program, but you'll find this breaking down (more exceptions to the rule) as you get down to lower levels. At a physical level, "one class per file" will not work in all cases, as mutually recursive types need to be defined in the same file (type Class1 = ... and Class2 = ...), and a bit of your code may reside in "free" functions not bound to a particular class (this is what F# "module"s are good for). The file-ordering constraints in F# will also force you to think critically about the dependencies among types in your program; this is a double-edged sword, as it may take more work/thought to untangle high-level dependencies, but will yield programs that are organized in a way that always makes them approachable (as the most primitive entities always come first and you can always read a program from 'top to bottom' and have new things introduced one-by-one, rather than just start looking a directory full of files of code and not know 'where to start').

Answer 5

How to Design Programs is all about this (at tiresome length, using Scheme instead of F#, but the principles carry over). Briefly, your code mirrors your datatypes; this idea goes back to old-fashioned "structured programming", only functional programming is more explicit about it, and with fancier datatypes.

Answer 6

F# provides the conventional OO approachs for large-scale structured programming (e.g. interfaces) and does not attempt to provide the experimental approaches pioneered in languages like OCaml (e.g. functors).

Consequently, the large-scale structuring of F# programs is essentially the same as that of C# programs.

Answer 7

On structuring functional programs:

While OO languages structure the code with classes, functional languages structure it with modules. Objects contain state and methods, modules contain data types and functions. In both cases the structural units group data types together with related behavior. Both paradigms have tools for building and enforcing abstraction barriers.

I would highly recommend picking a functional programming language you are comfortable with (F#, OCaml, Haskell, or Scheme) and taking a long look at how its standard library is structured.

Compare, for example, the OCaml Stack module with System.Collections.Generic.Stack from .NET or a similar collection in Java.