Haskell From First Principles

Resources

What is a function

The input set (domain) is {1,2,3} and the output set (codomain) is {A,B,C}.

In our function, an input of 1 will ALWAYS return A, no exceptions.

Lambda termd

Lambda calculus has three basic components:

The word expression refers to a superset of those things. It can be a variable name, an abstraction or a combination of those things.

An abstraction is a function. It is a lambda term that has a head (a lambda) and a body and is applied to an argument. An argument is an input value.

Abstractions consist of the head and the body. The head of the function is a lambda followed by a variable name. The body of the function is another expression.

A simple function might look like this:

The variable named in the head is the parameter and binds all instances of that same variable in the body of the function. In laymen terms, when we apply this function to an argument, each x in the body of the function will have the value of that argument.

In the above, we were reference functions called f, but in the previous section the lambda astraction has no name and is an anonymous function.

A named function can be called by name by another function, a lambda cannot.

Breakdown of the lambda

The extent of the lambda:

The first x is the single parameter of the function. This binds an variables:

The second x is part of the body, the expression the lambda returns when applied. This is a bound variable.

The . separates the parameters of the lambda from the function body.

Alpha Equivalence

In the above expression, the variable x is not semantically meaningful except in its role in that single expression. Because of this, there's a form of equivalence between lambda terms called alpha equivalence. This is a way of saying:

Beta reduction

When we apply a function to an argument, we substitute the input expression for all instances of the bound variables within the body of the abstraction. You also eliminate the head of the abstraction, since its only purpose was to bind the variable. This is called beta reduction.

We can do one using a number. We apply the function above to 2, substitude 2 for each bound variable in the body of the function and eliminate the head:

The only bound variable is a single x, so applying this function to 2 returns 2. This function is the identity function.

Free variables

In this example, x is a bound variable, y is a free variable.

Multiple arguments

Evaluation is simplication

There are multiple normal forms in lambda calculus, but here when we refer to normal form we mean beta normal form. This corresponds to a fully evaluated expression (or a fully executed program). For example, do you say 2000/1000 or do you say 2? You say 2. The normal form of the evaluated expression is therefore 2.

Note: if we had function (x,y) => x/y and apply x = 2000 and y = 1000, we call the the body with all arguments applied saturated.

Combinators

A combinator is a lambda term with no free variables. Combinators, as the name suggests, serve only to combine the arguments that they are given.

Divergence

Not all reducible lambda terms reduce neatly to a beta normal form. Reducing the following repeats itself:

Hello, Haskell!

-- Say Hello
sayHello :: String -> IO ()
sayHello x =
  putStrLn ("Hello, " ++ x ++ "!")
copy

If in the stack ghci REPL, you can unload the file using :m and reload updated files using :r.

Normal Form Reminder

Haskell reduces until we reach the normal form. Remember, 1 + 1 can be evaluated to 2, thus Haskell returns the normal form.

Redexes

Reducibles expressions such as 1 + 1 are also known as redexes. While we generally refer to this process as evaluation or reduction, you may also hear of it as normalizing or executing an expression (though somewhat imprecise).

Functions

Functions are a specific type of expression. Functions in Haskell relate to functions in mathematics - they map an input or set of inputs to an output.

Because they are built purely of expressions, they will always evaluate to the same result when given the same values.

-- in GHCi REPL
let triple x = x * 3
-- in source file
triple :: Number -> Number
triple x = x * 3
copy

Evaluation

When we talk about evaluating an expression, we're talking about reducing the terms until it is in the simplest form. We say it is irreducible or finished evaluating.

Haskell uses nonstrict evaluation (sometimes called lazy evaluation) stategy which defers evaluations of terms until they're forced by other terms referring so them.

Here is the reduction of our triple function:

triple 2
-- [triple x = x * 3; x:= 2]
2 * 3
6
copy

The above is reduced to its normal form, however Haskell only evalutes is weak head normal form (WHNF) but default. This means things are not always reduced to its irreducible form straight away.

(\f -> (1, 2 + f)) 2 reduces to the following in WHNF (1, 2 + 2) before it is evaluated further.

Infix Operators

Functions in Haskell default to prefix syntax (like the triple func above).

Operators for example are functions that can be used in the infix style.

You can sometimes use functions infix style with a small change in syntax:

10 `div` 4
div 10 4
(/) 10 4
2.5
copy

If the function is alphanumeric, it is prefix by default. If it is a symbol, it is infix by default.

Associativity and precedence

This BODMAS (from Mathematics) for precedence.

We can use :info to get more info about an operator.

Prelude> :i (/) (+) (-)
class Num a => Fractional a where
  (/) :: a -> a -> a
  ...
        -- Defined in ‘GHC.Real’
infixl 7 /
class Num a where
  (+) :: a -> a -> a
  ...
        -- Defined in ‘GHC.Num’
infixl 6 +
class Num a where
  ...
  (-) :: a -> a -> a
  ...
        -- Defined in ‘GHC.Num’
infixl 6 -
copy

An example of a right-associative infix operator is the power operator ^.

Declaring values

-- in the REPL
Prelude> let y = 10
Prelude> let x = 10 * 5 + y
Prelude> let myResult = x * 5
-- in a file
-- learn.hs
module Learn where
x = 10 * 5 + y
myResult = x * 5
y = 10
copy

\$ Operator

The (\$) operator is a convenience for when you want to express something with fewer pairs of parentheses:

-- Remember ($)'s definition
f $ a = f a
-- in use
Prelude> (2^) (2 + 2)
16
-- can replace those parentheses
 Prelude> (2^) $ 2 + 2
16
-- without either parentheses or $
 Prelude> (2^) 2 + 2
 6
copy

The (\$) will allow everything to the right of it to be evaluated first and can be used to delay function application.

Let and where

The contrast here is that let introduces an expression, so it can be used wherever you can have an expression, but where is a declaration and is bound to a surrounding syntactic construct.

-- FunctionWithWhere.hs
module FunctionWithWhere where

printInc n = print plusTwo
  where plusTwo = n + 2


printInc2 n = let plusTwo = n + 2
  in print plusTwo
copy

Strings

Prelude> :type 'a'
'a' :: Char
Prelude> :type "Hello!"
"Hello!" :: [Char]
copy

To print strings we can use print in the REPL or putStrLn and putStr for our Haskell modules.

Mutliline "do" can be done like so:

-- print2.hs
module Print2 where
main :: IO () main = do
  putStrLn "Count to four for me:"
  putStr   "one, two"
  putStr   ", three, and"
  putStrLn " four!"
copy

String concatenation:

-- print3.hs
module Print3 where

myGreeting :: String
myGreeting = "hello" ++ " world!" hello :: String

hello = "hello" world :: String
world = "world!"

main :: IO () main = do
  putStrLn myGreeting
  putStrLn secondGreeting
  where secondGreeting =
    concat [hello, " ", world]
copy

Top-level versus local definitions

module TopOrLocal where

topLevelFunction :: Integer -> Integer topLevelFunction x =
  x + woot + topLevelValue
  where woot :: Integer
        woot = 10

topLevelValue :: Integer
topLevelValue = 5
copy

Basic Datatypes

The type constructor is the name of the type and is capitalized. When you are reading or writing type signatures (the type level of your code), the type names or type constructors are what you use.