Monads

A monad is an algebraic structure in category theory, and in Haskell it’s used to describe computations as a sequece of steps, and to handle side effects such as state and IO. It is used to allow actions(e.g. mutable variables) to be implemented safely.

hello :: String -> IO String
hello x =
  do
    putStrLn ("Hello, " ++ x)
    putStrLn "What's your name?"
    name <- getLine
    return name

A monad in Haskell consists of a 

1

do
keyword and a sequence of commands. To extract information from a monad, use 
1

<-
. Monad is the way to implement IO operations. Note the return type of the hello function is 
1

IO String
, not 
1

String
.

In fact a 

1

do
block is just a syntactic sugar. Won’t go over too much, see more Here.

Lazy

Haskell is lazy, meaning that the evaluation of expressions is delayed until actually needed.

-- given definitions:
f x y = y
bot = bot

-- eval:
f bot 3
3

-- given definition:
ones = 1 :: ones

-- eval:
ones
[1,1,1,.....]

head(ones)
1

1

bot
is the simplest infinite function defined. Because of the laziness, if we evaluate 
1

f bot 3
we get 
1

3
, but if we evaluate 
1

f 3 bot
we get an infinite loop.

For another example, we can define the fibonacci sequence lazily:

fibs = 1:1:(zipWith (+) fibs (tail fibs))

lambda calculus

Lambda calculus is the theory behind functional programming. We can view lambda calculus as a minimum language:

exp
    = const
    | var
    | exp exp
    | \ var -> exp

variables

Variables are either 

1

bound
or 
1

free
.

  • In 
    1

    \x -> x + y
    , the variable 
    1

    x
    is bound and 
    1

    y
    is free. In
  • In 
    1

    a + (\ a -> 2^a) 3
    , the first 
    1

    a
    is free and the other 
    1

    a
    ’s are bound.

Alpha conversion

Alpha conversion means you can change the bound variables freely without affecting the value of the expression. e.g.:

(\x -> x + 1) 3
-- rename x to y, the expression stays the same.
(\y -> y + 1) 3

Beta conversion

Beta conversion is just 

1

applying
the lambda expression. It is done by substuting value for the parameters, i.e. the expression 
1

(\x -> exp1) exp2
is converted to 
1

exp1[exp2|x]
.

Eta conversion

Eta conversion says that a function is equivalent to a lambda expression that takes an argument and applies the function to the argument, i.e.: 

1

(\x -> f x)
is equal to 
1

f
. As another example, 
1

f x y = g y
is equivalent to 
1

f x = g
.

everything is a lambda

In fact, everything (variables, constants, lists, functions, etc.) is just syntactic sugar for a lambda expression. see Link for details.