I am trying to understand dealing with immutable data in FP (specifically in F#, but other FP’s are ok as well) and break the old habit of state-full thinking (OOP style). A part of the selected answer to the question here reiterated my search for any write-ups around problems that are solved by stateful representations in OOP with immutable ones in FP (For ex: A queue with Producers & Consumer). Any thoughts or links are welcome? Thanks in advance.

Edit: To clarify the question a little more, how would immutable structures (ex: queue) be shared concurrently across multiple threads (ex: producer and consumer) in FP


4 Answers 4


Although it's sometimes expressed that way, functional programming¹ doesn't prevent stateful computations. What it does is force the programmer to make state explicit.

For example, let's take the basic structure of some program using an imperative queue (in some pseudolanguage):

q := Queue.new();
while (true) {
    if (Queue.is_empty(q)) {
        Queue.add(q, producer());
    } else {

The corresponding structure with a functional queue data structure (still in an imperative language, so as to tackle one difference at a time) would look like this:

q := Queue.empty;
while (true) {
    if (q = Queue.empty) {
        q := Queue.add(q, producer());
    } else {
        (tail, element) := Queue.take(q);
        q := tail;

Since the queue is now immutable, the object itself doesn't change. In this pseudo-code, q itself is a variable; the assignments q := Queue.add(…) and q := tail make it point to a different object. The interface of the queue functions has changed: each must return the new queue object that results from the operation.

In a purely functional language, i.e. in a language with no side effect, you need to make all state explicit. Since the producer and consumer are presumably doing something, their state must be in their caller's interface here as well.

main_loop(q, other_state) {
    if (q = Queue.empty) {
        let (new_state, element) = producer(other_state);
        main_loop(Queue.add(q, element), new_state);
    } else {
        let (tail, element) = Queue.take(q);
        let new_state = consumer(other_state, element);
        main_loop(tail, new_state);
main_loop(Queue.empty, initial_state)

Note how now every piece of state is explicitly managed. The queue manipulation functions take a queue as input and produce a new queue as output. The producer and consumer pass their state through as well.

Concurrent programming doesn't fit so well inside functional programming, but it fits very well around functional programming. The idea is to run a bunch of separate computation nodes and let them exchange messages. Each node runs a functional program, and its state changes as it sends and receives messages.

Continuing the example, since there's a single queue, it's managed by one particular node. Consumers send that node a message to obtain an element. Producers send that node a message to add an element.

main_loop(q) =
    consumer->consume(q->take()) || q->add(producer->produce());

The one “industrialized” language that gets concurrency right³ is Erlang. Learning Erlang is definitely the path to enlightenment⁴ about concurrent programming.

Everybody switch to side-effect-free languages now!

¹ This term has several meanings; here I think you're using it to mean programming without side effects, and that's the meaning I'm also using.
² Programming with implicit state is imperative programming; object orientation is a completely orthogonal concern.
³ Inflammatory, I know, but I mean it. Threads with shared memory is the assembly language of concurrent programming. Message passing is a lot easier to understand, and the lack of side effects really shines as soon as you introduce concurrency.
And this is coming from someone who's not a fan of Erlang, but for other reasons.

  • 2
    +1 Much more complete answer, although I suppose one could quibble that Erlang is not a pure FP language. May 18, 2011 at 23:02
  • 1
    @Rein Henrichs: Indeed. In fact, of all currently existing mainstream languages, Erlang is the one which most faithfully implements Object-Orientation. May 18, 2011 at 23:44
  • 2
    @Jörg Agreed. Although, again, one could quibble that pure FP and OO are orthogonal. May 19, 2011 at 0:52
  • So, for implementing an immutable queue in a concurrent software, messages need to be sent and received between nodes. Where are stored pending messages?
    – mouviciel
    Jan 23, 2013 at 8:49
  • @mouviciel Queue elements are stored in the node's incoming message queue. This message queue facility is a basic feature of a distributed infrastructure. An alternative infrastructure design which works well for local concurrency but not with distributed systems is to block the sender until the receiver is ready. I realize this doesn't explain everything, it would take a chapter or two of a book on concurrent programming to explain this fully. Jan 23, 2013 at 13:31

Stateful behavior in a FP langauge is implemented as a transformation from a prior state to a new state. For instance, enqueue would be a transformation from a queue and a value to a new queue with the value enqueued. Dequeue would be a transformation from a queue to a value and a new queue with the value removed. Constructs like monads have been devised to abstract this state transformation (and other results of computation) in useful ways

  • 3
    If it's a new queue for every add/remove operation, how would two (or more) async operations (threads) share the queue? Is it a pattern to abstract the new-ing of the queue?
    – venkram
    May 18, 2011 at 21:06
  • Concurrency is a completely different question. I can't provide an sufficient answer in a comment. May 18, 2011 at 21:13
  • 2
    @Rein Henrichs: "can't provide an sufficient answer in a comment". That usually means you should update the answer to address the comment-related issues.
    – S.Lott
    May 18, 2011 at 21:16
  • Concurrency can be monadic too, see haskells Control.Concurrency.STM. May 18, 2011 at 21:45
  • 1
    @S.Lott in this case it means that the OP should ask a new question. Concurrency is OT to this question, which is about immutable data structures. May 18, 2011 at 21:46

...problems that are solved by stateful representations in OOP with immutable ones in FP (For ex: A queue with Producers & Consumer)

Your question is what is called an "XY problem". Specifically, the concept you cite (queue with producers & consumer) is actually a solution and not a "problem" as you describe. This introduces a difficulty because you are asking for a purely functional implementation of something that is inherently impure. So my answer starts with a question: what is the problem you are trying to solve?

There are many ways for multiple producers to send their results to a single shared consumer. Perhaps the most obvious solution in F# is to make the consumer an agent (aka MailboxProcessor) and have the producers Post their results to the consumer agent. This uses a queue internally and it is not pure (sending messages in F# is an uncontrolled side effect, an impurity).

However, it is quite likely that the underlying problem is something more like the scatter-gather pattern from parallel programming. To solve this problem you might create an array of input values and then Array.Parallel.map over them and gather the results using a serial Array.reduce. Alternatively, you might use functions from the PSeq module to process the elements of sequences in parallel.

I should also stress that there is nothing wrong with stateful thinking. Purity has advantages but it is certainly not a panacea and you should make yourself aware of its shortcomings as well. Indeed, this is precisely why F# is not a pure functional language: so you can use impurities when they are preferable.


Clojure has a very well thought out concept of state and identity, which is closely related to concurrency. Immutability plays an important role, all values in Clojure are immutable, and can be accessed through references. References are more than just simple pointers. They manage access to value, and there are multiple types of them with different semantics. A reference can be modified to point to a new (immutable) value, and such a change is guaranteed to be atomic. However, after the modification all other threads still work on the original value, at least until they access the reference again.

I highly recommend you to read an excellent article about state and identity in Clojure, it explains the details much better then I could.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.