How can I write an app that doesn't change state (in functional language)?

Question

I want to learn functional programming one day but I don't understand how I could use it for anything other than simple math.

For example: A simple web browser add bookmark function needs to cause some sort of mutation so that next time the user clicks bookmarks the new bookmark is there in the list.

Answer 1

Even in pure functional languages like Haskell, you will have to manipulate state. This is done via monads.

Answer 2

A useful application as a whole will often have to change state of several things, but that doesn't mean that all or your functions need to change state to be useful.

Monads in functional programming are to express input/output (I/O) operations and changes in state without using language features that introduce side effects.

I think you are thinking only in terms of object oriented. Just because a function always gives the same output given the same input, doesn't mean that it can't take in different types of input (possibly infinite possibilities of input) and produce different types of output.

With functional programming you are dealing with immutable objects instead of mutable ones. If you get input of an object, you can create a new modified object and return that.

Take a look at this article about MapReduce by Joel on software. It contains a pretty good example about why a function that does not change state can be completely useful.

Answer 3

Good example how you deal with "mutability". Suppose you implement some data structure, let's say AVL tree, in a functional language. In functions you implement (insert, delete, etc.), as well as internal functions (rotate, etc.) you don't actually mutate data, but return mutated data.

The underlying runtime system ensures your program will use memory efficiently (for example, it does copy-on-write and garbage collection).

In parts of the program when you really change the world state (I/O, GUI), there are two approaches.

• pure functional languages, like Haskell, encapsulate such operations in monads (warning: your head might explode when reading about them, but don't worry too much)
• other functional languages, like OCaml, permit mutability and side-effects in your programs.

Answer 4

You don't need mutable state for your example. For 'add bookmark', a new bookmark list can be created that has the same contents as the old list but with one new entry. This is the way most immutable programming works; rather than make changes to an existing object graph, you just create a new object graph that reflects the new state of the world. When everything is immutable, it is easy to share large portions of the object graph between 'old' and 'new' versions.

One level deeper in your example, suppose a 'browser' is an data structure object with the following information: current web page, user's homepage, and list of bookmarks. This may be represented in memory as a tree that looks something like this:

browser = {
 curPage --> "http://current"
 homePage --> "http://home"
 favorites --> { data --> "http://firstFav"
                 next --> { data --> "http://secondFav"
                            next --> null } }
}

Now the 'AddFavorite' function would take as input such a data structure and return a new data structure like so

browser = *{
 curPage --> "http://current"
 homePage --> "http://home"
 favorites --> *{ data --> *"http://newFav"*
                 next --> { data --> "http://firstFav"
                            next --> { data --> "http://secondFav"
                                       next --> null } } }*
}*

The bits marked with a '*' are new objects - there's a new linked list node at the front of favorites, containing a new string, and the browser structure itself is new (it must be since it has a new 'favorites' pointer).

You can model all 'stateful' computation like this, as functions that take in a 'previous world' as input and return a 'next world' as output; this is the essence of state monads in a language like Haskell.

Answer 5

Many other answers will have you rushing off to use monads or some other exotic techniques to program using mutable state. While I have heard with my own ears the editor of the Haskell 98 Report call Haskell "the world's finest imperative language", you don't need nearly as much mutable state as other answers are suggesting. In a functional program, you keep your state in function parameters.

For example, I've just finished writing a Haskell program that decides how to back up my music to DVDs such that songs from the same album go on the same DVD, and every DVD (except the last) is at least 99.9% full. The list of DVDs and the list of which album goes on which DVD are continually changing, but no references, monads, or other exotic features are involved. These values are simply parameters to a recursive function.

To see some more examples and explanations, read John Hughes's very nice tutorial paper Why Functional Programming Matters.

Answer 6

Also, in practice, many apps written in functional programming languages do in fact make use of side-effect functions like (set! ) to actually change state. It isn't theoretically pure but it certainly gets the job done.

(In particular I'm thinking of a popular piece of consumer software that was written in a LISP derivative but had to run in constant memory, so things like garbage collection had to go out the window.)