How to write an application that does not change state (in a 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 adding a bookmark function should cause some mutation, so the next time the user clicks the bookmark, the new bookmark is in the list.

Answer 1

A useful application as a whole often has to change the state of several things, but this does not mean that all or your functions must change state in order to be useful.

Monads in functional programming should express I / O (I / O) operations and state changes without using language functions that introduce side effects.

I think you only think about object oriented. Just because a function always gives the same output with the same input does not mean that it cannot accept different types of input (possibly endless input possibilities) and produce different types of output.

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

Check out Joel's MapReduce article on software for an article . It contains a pretty good example of why a function that does not change state can be completely useful.

Answer 2

You do not need to change the state of your example. To “add a bookmark”, you can create a new bookmark list that has the same contents as the old list, but with one new entry. This is how most immutable programs work; instead of making changes to an existing object graph, you simply create a new object graph that reflects the new state of the world. When everything is unchanged, it is easy to distribute large portions of object plots between the "old" and "new" versions.

At one level deeper in your example, suppose a “browser” is a data structure object with the following information: current web page, user home page, and bookmark list. This can 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 will accept such a data structure as input and return a new data structure, for example,

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

Bits marked with the '*' sign are new objects - there is a new linked node list in front of the favorites containing a new line, and the browser structure itself is new (this should be because it has a new “Favorites”).

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

Answer 3

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

Answer 4

A good example of how you deal with volatility. Suppose you implement some data structure, let’s say, the AVL tree, in a functional language. In the functions that you implement (insert, delete, etc.), as well as internal functions (rotation, etc.), you do not actually mutate the data, but return the mutated data.

The basic runtime system ensures that your program uses memory efficiently (for example, copy-to-write and garbage collection).

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

• pure functional languages ​​like Haskell encapsulate such operations in monads (warning: your head may explode when reading about them, but don't worry too much).
• Other functional languages, such as OCaml, allow for variability and side effects in your programs.

Answer 5

Many other answers will make you rush to use monads or some other exotic methods for programming using mutable state. While I heard with my own ears, the Haskell 98 Report editor called on Haskell "the world of the highest imperative language," you do not need almost the same mutable state as the other answers. In a functional program, you save your state in the function parameters .

For example, I just finished writing a Haskell program that decides how to back up my music to DVD so that songs from one album go to the same DVD and every DVD (except the last) is at least 99.9 % complete. The list of DVDs and the list of the album on which the DVD is constantly changing, but does not contain links, monads or other exotic functions. These values ​​are just parameters for a recursive function.

To see a few more examples and explanations, read John Hughes a very good training paper Why functional programming issues .

Answer 6

In addition, in practice, many applications written in functional programming languages ​​actually use side-effect functions such as (set!) To actually change state. This is not theoretically pure, but it certainly does its job.

(In particular, I think of the popular piece of consumer software that was written in the LISP derivative, but was supposed to work in read-only memory, so things like garbage collection should go out of the window.)