SML syntax and functional programming concepts

Expression
All the expression from 1 and below must be used in a function.

0. Function
A function would take zero or more parameters and will always return a value.
fun foo () = 3
fun sqr (x, y, z) = x + y + z
A function always takes a parameter, either in the form of tuple or currying (discussed later).

1. let
A let expression lets extend the current environment by letting the creation of variables and functions. has to be used inside a function. example
fun foo (x) = let y = x * x in y end

2. if then else 
An if then else construct has to always return a value. the type of the value must be same from each of the branch. has to be used inside a function. example:
if x = 3 then true else false

3. pattern matching
Given a value, takes the branch that matches the data type of the value. example:
case exp of
    [] => NONE
   | Some x => do something

Environment
0. Extending environment
Any time a variable, function is declared, current environment is extended by a new binding.
| y = 3 | z = 5| x = 5  <=== current environment
val p = 3
| y = 3 | z = 5| x = 5| p =3  <=== updated environment
A new variable can be introduced from a pattern matching expression. Example:
case lst of
 x :: xs => do something (* :: is the append function which is declared as infix *)

1. Shadowing

introducing a new binding does not override a value in the environment, rather a new entry is created and from that scope new entry's value is used.
| y = 3 | z = 5| x = 5  <=== current environment
val y = 3
| y = 3 | z = 5| x = 5| y =3  <=== updated environment

2. Closure
Combination of a function and a pointer of the environment is closure.
Example:
val y =3
val z = 5
fun foo = z + 3
val z = 5
val y = 3
val closure = foo
closure has the instruction pointer of the function foo and the following pointer of the environment
| y = 3 | z = 5| z= 5| y =3  <=== updated environment

                    ^

  <======  | | to get a value of a variable, closure will start from the pointer and go left.

Datatype and Accessing data
0. Record, Tuple
Records are created dynamically. They can have any number of fields in them.
Example: {first="isaac", middle="buddha", last="christ"}
A type can be given a name. Example
type set = { insert : int -> set, member : int -> bool, size : unit -> int }

1. List
Lists are immutable. An insertion or deletion would always cause a new list to be created with desired elements.
Example:
[] is empty list
"a" :: [] (* insert an element at the head *)
["1, 2, 3, 4] @ [5, 6, 7, 8] (* append operator *)

2. Custom data type
datatype myType = StudentInfo of string * string | Grade of int

val myInfo = StudentInfo ("isaac", "christ").
Datatypes can be pattern matched.

Modular Programming
It can be think of like a Java package. Gives client visibility of enough information so that they can import the library in their code and use it. Best practice is to provide just enough information so that a client executes the given program with minimum risk.
Example:
signature MATHLIB =
sig
    val fact : int -> int
    val half_pi : real
    val doubler : int -> int
end

structure MyMathLib :> MATHLIB =struct
     fun fact x = if x=0 then 1 else x * fact (x - 1)
     val half_pi = Math.pi / 2.0
     fun doubler y = y + y
end

Mutability
Variables can be mutated through reference.
val x = ref 7 (* the memory location x points to holds the value 7 *)
val y = x (* y points to same memory location as x does *)
val z = ref 7 (* the memory location z points to holds 7 *)
val _ = x := 20 (* := operator is for assigning value, := operator returns unit *)
val p = !x (* retrieve content of x, p get 20*)
val q = !y (* q has 20 *)
val r = !z (* r has 7 *)

Misc

0. Higher order function

functions that can take another function and return a function as a return value.

1. Anonymous function
functions that does not have names.
fun foo bar x = bar x
val v = foo (fn (x) => x+1) 1

2. Currying
Curried functions always takes 1 argument and returns either a value or another function. Curried functions use closure to access variables it uses. Curried functions can be called with less arguments.

3. Tail recursion
A recursive call where the caller just returns the value the callee returns without applying any application on the callee's returned value. more can be seen [1].

4. Syntactic sugar
Certain language features that lets a programmer do a certain task with less amount of typing.
Example:
fun f = fn (x) => (fn (y) => (fn (z) => x + y + z))
f can be written using syntactic sugar fun x y z = x + y + z

5. map, filter, fold
these functions are applied on a list.
map => converts each item of the list to something else (* convert degree list to celcius list *)
filter => returns a list where every item meets a certain criteria (* get students who passed *)
fold => returns value that depicts certain attribute of a list (* get sum of the values of a list *)

6. value restriction
Because of mutability, it might be possible to assign value with wrong type on a variable. The value would not be shadowed rather overwritten. Initially, if we say we are able to say we would be storing a polymorphic data in a certain memory location, then later we might try to assign wrong type values in that memory location.
Example:
val r = ref NONE (* system does not which type will go where r is pointing to *)
(* type of r is given ?.X1 option ref type *)
r := SOME "abc" (* trying to assign string *)
r := SOME 1        (* trying to assign int *)
To prevent this, the variable declaration must have a concrete type, otherwise system will give r a type to make r not usable anymore.
That's why we cannot do the following
val funhandle =  map (fn (x) => (x, 1))

The following works, as it have concrete type
val r : int option ref = ref NONE;

Value restriction is introduced only for mutability or ref type. This restriction is generalized because many times the compiler cannot tell about a type. One case being types introduced through modular programs.

Reference:
[0] https://www.coursera.org/learn/programming-languages
[1] http://www.saifulabu.me/2017/11/tail-recursion.html