How do you design a functional program?

Read the SICP.

Also, there is a PDF Version available.

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').

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.

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.

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.

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.