Projects

The Basics of Haskell

Following the system of lambda calculus, as defined by Alonzo Church and later refined, Haskell attempts to work as a function-based programming langauge, rather than a sequentially-ordered one. Because of this attempt to increase functionality (speaking of functions, not performance) of the language, definitions are split into two groups.

  • Pure functions do not change a state, depend on a temporal variable, or deal with user input/output.
  • Impure functions include one of those things mentioned above.

Composition:

Consider two functions, f and g, as defined

f x = 5 * x

g = do
putStrLn "Hello"
putStrLn "How are you?"

In this case, f would be considered a pure function. All it does is provide a value that is five times its input. Therefor, it does not change a state or do anything requiring outside input.

g, however, would be considered an impure function. It prints two statements to the standard output, thereby providing a value to the user, rather than returning a value useable by other functions.

Haskell works better when pure functions are used as often as possible. This is because function composition can be used effectively in Haskell. This is almost exactly like function composition in basic algebra. For example:

f x = 5 * x

h o = o . o

In the above example, both f and g are pure haskell functions. f takes a parameter x and returns a value that is five times that input. g takes a function o and composes it onto itself. If these functions were used at some point such as below,

(h f) 5

The return value would be 125. First, f is passed as a parameter to h, which returns a function that can be understood as meaning (5 * (5 * x)). Then, the value of 5 is passed to this result and x assumes that value, creating a multiplication of 5.

Control:

Haskell implements some control operators, which help functions decide what to do.

The equivalent of an if statement in Haskell is implemented by guards, which look like the following:

f x =
| x == 0 = 1
| otherwise = x * f (x – 1)

The above shows not only the use of guards, but also a recursive statement. Almost all functions that are useful in Haskell and other functional programming languages are recursive to an extent.

To help with all the recursive functions, list comprehension is optimized. The below gives an example of a list containing all the even numbers and a list containing all the multiples of 3 and 5:

e = [2, 4..]

t = [x | x <- [1..], x `mod` 3 == 0 || x `mod` 5 == 0]

 

Functional Programming & Lambda Calculus

In the 1930s, Alonzo Church created Lambda Calculus as a universal model of computation. This means that this model is capable of computing anything that can be computed algorithmically. This is typically used as the basis model of computation for functional programming, which utilizes recursion above all else.

λ-Calculus is based on the use of lambda terms and functions to represent natural numbers and operations.

  • x is a variable
  • (λx.M) is an abstraction, with M being a lambda term
  • (M N) is an application, with both M and N being lambda terms
  • (λxy.(λz.(λx.z x) (λy.z y)) (x y)) is an example expression that Wikipedia gives

There are two reduction operations that can take place in λ-Calculus expressions: α-conversion and β-reduction. Renaming bound variables is α-conversion. β-reduction is substituting bound variables in an expression for their applications. An example of reduction:
(λx.λy.(x (λx.y x))) (λz.z)
(λx.λy.(x (λw.y w))) (λz.z) : α-conversion (renamed x -> w)
(λy.((λz.z) (λw.y w))) : β-reduction
(λy.λw.y w) : β-reduction
(λx.λy.x y) : α-conversion
(λxy.x y) : alternate notation

So functions can be reduced. This of course doesn’t mean anything unless we create meanings for these functions. Numbers are defined:

0 := λfx.x
1 := λfx.f x
2 := λfx.f (f x)
3 := λfx.f (f (f x))
… and so on

Because numbers are defined as functions, they can be applied to other functions and have other functions applied to them. It takes a long time to work out the applications of these numbers on one another, but eventually it becomes obvious that (M N), where M and N are numbers in that form, evaluates to NM. Other operations can be computed using certain functions (such as repeated use of the successor function).

Because λ-Calculus is a universal model of computation, it is equivalent to a Turing machine. Various programming languages are based on λ-Calculus, including Haskell and Lisp. Most programming languages also have anonymous functions (lambda functions) based on these principles. Because all variables are bound in lambda expressions, these languages and functions must rely primarily on recursion, rather than structures such as loops. I’ll be studying recursion and functional programming languages.