What is the bare minimum needed to implement a functional language?
A Lambda. That's all. (See the lambda calculus.)
From there, you can construct functions to perform every task and represent many values. You can define new (named) functions with the Y-combinator form (PDF), and represent several values (like true and false) as functions. (Taking the idea to the extreme, you can represent all integral values as Church numerals.)
You don't even really need a special if
form. It can be constructed as a collection of functions. JavaScript example:
true = function(x,y){ return x; }
false = function(x,y){ return y; }
ifelse = function(x,a,b){ x(a,b)() }
not = function(x){ return x(false,true) }
and = function(x,y){ return x(y,false) }
or = function(x,y){ return x(true,y) }
bool = and(not(true),or(true,false))
ifelse(bool,
function(){ alert("true!") },
function(){ alert("false!") }
)
Unlambda is a real language that takes this idea to the logical extreme. It has only one type (lambda functions), and a handful of special convenience forms such as the identity function, K- and S-combinators, and a print function (which, except for print, can all be expressed as a collection of lambdas).
Exactly. See case class method copy
, or the general concept of lenses.
In particular, if state needs changing, you'd use a State monad. Changes to that state monad can be made through lenses, which makes extracting information from "state" and changing it easy.
See also this question about the general problem that comes from a deep structure like "state" and making changes to it. The answers have good links on both lenses and zippers if you want to get deeper into that.
Best Answer
Pure = deterministic + without side effects
A function is pure only, if both criteria are met. If it meets only one of them, it's not pure.
Deterministic but with sideeffects:
As pointed out by @Caleth
Without sideeffects but not deterministic
Note that side effects are only "outbound". If a function modifies the state of the containing code (global variable or field in a class) or if it performs some I/O-operations, it has side effects.
Another very simple function that is not deterministic would be:
Pure: