Purely functional languages?

Question

what is purely functional language? And what is purely functional data structure? I'm kind of know what is the functional language, but I don's know what is the "pure" mean. Does anyone know about it? Can someone explain it to me?Thanks!

Answer 1

When functional programmers refer to the concept of a pure function, they are referring to the concept of referential transparency.

Referential transparency is actually about value substitution without changing the behaviour of the program.

Consider some function that adds 2 to a number:

let add2 x = x + 2

Any call to add2 2 in the program can be substituted with the value 4 without changing any behaviour.

Now consider we throw a print into the mix:

let add2 x =
    print x 
    x + 2

This function still returns the same result as the previous one but we can no longer do the value substitution without changing the program behaviour because add2 2 has the side-effect of printing 2 to the screen.

It is therefore not refentially transparent and thus an impure function.

Now we have a good definition of a pure function, we can define a purely functional language as a language where we work pretty much exclusively with pure functions.

Note: It is still possible to perform effects (such as printing to the console) in a purely functional language but this is done by treating the effect as a value that represents the action to be performed rather than as a side-effect within some function. These effect values are then composed into a larger set of program behaviour.

---

A purely functional data structure is then simply a data structure that is designed to be used from a purely functional language.

Since mutating a data structure with a function would break this referential transparency property, we need to return a new data structure each time we e.g. add or remove elements.

There are particular types of data structures where we can do this efficiently, sharing lots of memory from prior copies: singly-linked lists and various tree based structures are the most common examples but there are many others.