How do you design programs in Haskell or other functional programming languages?

Question

I have some experience in object oriented programming languages like c# or ruby. I know how to design a program in object oriented style, how to create classes and objects, and how to define relations between them. I also know some design patterns.

How do people write functional programs? How do they start? Are there design patterns for functional languages? Are methodologies like extreme programming or agile development applicable for functional languages?

Answer 1

I write my answer mainly with Haskell in mind, though many concepts apply equally well to other functional languages like Erlang, Lisp(s), and ML. Some even apply (to some extent) to Ruby, Python, Perl and Javascript.

How do people write functional programs? How do they start?

By writing functions. When you are doing functional programming, you either are writing main, or you are writing a helper function. Sometimes your main goal might be to write a data type with various relevant functions that operate on it.

Functional programming is very well suited to both top-down and bottom-up approaches. Haskell strongly encourages writing your programs in high-level language, and then simply defining the details of your high-level design. See minimum, for example:

minimum    :: (Ord a) => [a] -> a
minimum xs =  foldl1 min xs

The function to find the smallest element in a list is written simply as a traversal over the list, using the min function to compare each element with the "accumulator", or current minimum value.

Are there design patterns for functional languages?

There are two things that could be equated to "design patterns", imho, higher-order functions and monads. Let's talk about the former. Higher-order functions are functions that either take other functions as input, or produce functions as output. Any functional language generally makes heavy use of map, filter, and fold (fold is often also called "reduce"): three very basic higher-order functions that apply a function to a list in different ways. These replace boilerplate for loops in a beautiful way. Passing functions around as parameters is an extremely powerful boon to programming; lots of "design patterns" can be accomplished simpler by using higher-order functions, being able to create your own, and being able to leverage the powerful standard library, which is full of useful functions.

Monads are the "scarier" topic. But they're not really that scary. My favorite way to think of monads is to think of them as enveloping a function in a bubble and giving that function superpowers (that only work inside the bubble). I could elaborate, but the world doesn't really need yet another monad analogy. So I'll move to quick examples. Suppose I want to use a nondeterministic "design pattern". I want to run the same computation for various different inputs at the same time. I don't want to choose just one input, I want to choose them all. That would be the list monad:

allPlus2 :: [Int] -> [Int]
allPlus2 xs = do x <- xs
                 return (x + 2)

Now, the idiomatic way to perform this is actually map, but for illustration's sake, can you see how the list monad allowed me to write a function that looks like it operates on one value, but endowed it with the superpower to work on every element in a list? Other superpowers include failure, state, interacting with the "outside world", and parallel execution. These superpowers are very potent, and most programming languages allow functions with superpowers to rampage all around. Most people say Haskell doesn't allow these superpowers at all, but really, Haskell just contains them in monads so their effect can be limited and observed.

tl;dr Grokking higher-order functions and monads is the Haskell equivalent to grokking design patterns. Once you learn these Haskell concepts, you start thinking "design patterns" are mostly cheap workarounds to simulate the power of Haskell.

Are methodologies like extreme programming or agile development applicable for functional languages?

I don't see anything that ties these management strategies down to any one programming paradigm. As phynfo stated, functional programming practically forces you to do function decomposition, breaking a large problem into subproblems, so mini-milestones should be a piece of cake. There are tools like QuickCheck and Zeno to test or even prove properties about the functions you write.

Answer 2

There are some people stating, that the OO-design-patterns are in fact solutions to problems in the OO-Paradigm which the functional programming paradigm doesnt show.

I would say: the way to design functional programs is a very natural way to think about a problem: Functional decomposition. You first think about the input-output-Parameters to the problem and you have (stated in Haskell):

problem :: Input -> Output

... and then you decompose this into "smaller" functions which can be glued together by the excellent glue, functional programming language provide (like higher-order functions, (.), currying, ...).

Answer 3

When designing a program in Haskell, it is usually good to start by thinking about the types. In particular, pay attention to what side-effects you want your program to perform and how you can separate the pure pieces from the side effecting pieces. This is also a good time to think about what constraints you want on your operations, and how to use the type system to enforce these constraints.

Once you have nailed down the types, it is usually just a matter of filling in the right code to make it compile.

When it comes to extreme programming/agile development, I think pure functional programming is very well suited to techniques like test driven development. Testing pure code is simply a matter of checking that you get the expected output given some input, while testing imperative code requires you to set up the state of the world before calling your code, and then carefully inspecting the world afterwards to make sure it changed in the way you expected.

Answer 4

After doing professional software development in OO languages for a number of years I came to believe that the mother of all design patterns is Don't Repeat Yourself (DRY). As code changes over time, programs with lots of repeated code tend be more susceptible to bugs because inevitably the developer will change something and forget about another place where that same pattern occurs and needs to be changed. This pattern stayed the same when I started programming in Haskell professionally. I break my programs up into small functions in ways that reduce repetition and seem to naturally fit the domain. Often I get it wrong. Just yesterday I discovered one function that sticks out in my mind that was doing two things that I discovered would be better split into separate functions. If I had not split them, I would have had to create a new function that duplicated some of the existing functionality. Functional programming languages (most obviously because of first-class functions) give you more tools to do this easily than procedural/OO languages.

Minimizing the scope of things a function can affect is another design principle that comes to mind. In a pure language like Haskell one way of doing this is to separate pure and impure code. But in my mind this is still just a specific instance of the DRY principle. Making a function pure instead of impure (say a part of a larger application monad) means that to test it you won't have to initialize as much of the environment--one less thing you have to repeat.

Answer 5

Well, there is How to Design Programs, which is a full course on how to design programs with Scheme, in itself a functional programming language. It is a good text.