Chapter 03- Declarative Programming Paradigm

Introduction to Lambda Calculus, Functional

Programming Concepts, Evaluation order, Higher order
functions, I/O-Streams and Monads.
—------------------------------------------------------------------------------------------------------------------
Functional programming
Its main focus is on “what to solve”
• It uses expressions instead of statements.
• Functional programming is based on mathematical functions.
• Functional programming languages are categorized into two groups, i.e.

• Pure Functional Languages :

These types of functional languages support only the functional paradigms. For example
−Haskell.

• Impure Functional Languages:

These types of functional languages support the functional paradigms and imperative style
programming. For example − LISP.

Characteristics of Functional Programming

• Functional programming method focuses on results, not the process
• Emphasis is on what is to be computed
• Data is immutable
• Functional programming Decompose the problem into ‘functions
• It is built on the concept of mathematical functions which uses conditional
expressions and recursion to do perform the calculation

History of Functional programming

• The foundation for Functional Programming is Lambda Calculus.

• It was developed in the 1930s for the functional application, definition, and recursion
• LISP was the first functional programming language. McCarthy designed it in 1960

1
• In the late 70’s researchers at the University of Edinburgh defined the ML(Meta Language)
• In the early 80’s Hope language adds algebraic data types for recursion and equational reasoning
• In the year 2004 Innovation of Functional language ‘Scala.’

Functional Programming Languages

• Haskell
• SML
• Clojure
• Scala
• Erlang
• Clean
• F#
• ML/OCaml Lisp / Scheme
• XSLT
• SQL
• Mathematica

Introduction

Functional programming is a programming paradigm in which we try to bind everything in pure

mathematical functions style. It is a declarative type of programming style. Its main focus is on
“what to solve” in contrast to an imperative style where the main focus is “how to solve”. It uses
expressions instead of statements. An expression is evaluated to produce a value whereas a statement
is executed to assign variables. Those functions have some special features discussed below.

Functional Programming is based on Lambda Calculus:

Lambda calculus is a framework developed by Alonzo Church to study computations with functions.
It can be called the smallest programming language in the world. It gives the definition of what is
computable. Anything that can be computed by lambda calculus is computable. It is equivalent to the
Turing machine in its ability to compute. It provides a theoretical framework for describing functions
and their evaluation. It forms the basis of almost all current functional programming languages.

2
Fact: Alan Turing was a student of Alonzo Church who created Turing machine which laid the
foundation of imperative programming style.

Programming Languages that support functional programming: Haskell, JavaScript, Python,

Scala, Erlang, Lisp, ML, Clojure, OCaml, Common Lisp, Racket.

Concepts of functional programming:

● Pure functions
● Recursion
● Referential transparency
● Functions are First-Class and can be Higher-Order
● Variables are Immutable

Pure functions: These functions have two main properties. First, they always produce the same
output for the same arguments irrespective of anything else.

Secondly, they have no side-effects i.e. they do not modify any arguments or local/global variables
or input/output streams.
Later property is called immutability. The pure function’s only result is the value it returns. They
are deterministic.

Programs done using functional programming are easy to debug because pure functions have no side
effects or hidden I/O. Pure functions also make it easier to write parallel/concurrent applications.
When the code is written in this style, a smart compiler can do many things – it can parallelize the
instructions, wait to evaluate results when needing them, and memorize the results since the results
never change as long as the input doesn’t change.

example of the pure function:

sum(x, y) // sum is function taking x and y as arguments
return x + y // sum is returning sum of x and y without changing them

3
Recursion: There are no “for” or “while” loop in functional languages. Iteration in functional
languages is implemented through recursion. Recursive functions repeatedly call themselves, until it
reaches the base case.

example of the recursive function:

fib(n)
if (n <= 1)
return 1;
else
return fib(n - 1) + fib(n - 2);
Referential transparency: In functional programs variables once defined do not change their value
throughout the program. Functional programs do not have assignment statements. If we have to store
some value, we define new variables instead. This eliminates any chances of side effects because any
variable can be replaced with its actual value at any point of execution. State of any variable is
constant at any instant.
Example:
x = x + 1 // this changes the value assigned to the variable x.
// So the expression is not referentially transparent.

Functions are First-Class and can be Higher-Order: First-class functions are treated as first-class
variable. The first class variables can be passed to functions as parameter, can be returned from
functions or stored in data structures. Higher order functions are the functions that take other
functions as arguments and they can also return functions.
Example:
show_output(f) // function show_output is declared taking argument f
// which are another function
f(); // calling passed function
print_gfg() // declaring another function
print("hello gfg");
show_output(print_gfg) // passing function in another function

4
Variables are Immutable: In functional programming, we can’t modify a variable after it’s been
initialized. We can create new variables – but we can’t modify existing variables, and this really
helps to maintain state throughout the runtime of a program. Once we create a variable and set its
value, we can have full confidence knowing that the value of that variable will never change.

Advantages and Disadvantages of Functional programming

Advantages:
1. Pure functions are easier to understand because they don’t change any states and depend only
on the input given to them. Whatever output they produce is the return value they give. Their
function signature gives all the information about them i.e. their return type and their
arguments.
2. The ability of functional programming languages to treat functions as values and pass them
to functions as parameters make the code more readable and easily understandable.
3. Testing and debugging is easier. Since pure functions take only arguments and produce
output, they don’t produce any changes don’t take input or produce some hidden output.
They use immutable values, so it becomes easier to check some problems in programs
written uses pure functions.
4. It is used to implement concurrency/parallelism because pure functions don’t change
variables or any other data outside of it.
5. It adopts lazy evaluation which avoids repeated evaluation because the value is evaluated and
stored only when it is needed.
Disadvantages:
1. Sometimes writing pure functions can reduce the readability of code.
2. Writing programs in recursive style instead of using loops can be bit intimidating.
3. Writing pure functions are easy but combining them with the rest of the application and I/O
operations is a difficult task.
4. Immutable values and recursion can lead to decrease in performance.
Applications:
● It is used in mathematical computations.
● It is needed where concurrency or parallelism is required.

5
 Introduction to Lambda Calculus
1. History of the lambda calculus
2. Syntax
3. Function abstraction
4. Function application
5. Free and bound variables
6. Beta reductions
7. Evaluating a lambda expression
8. Currying
9. Renaming bound variables by alpha reduction
10. Eta conversion
11. Substitutions
12. Disambiguating lambda expressions

1. History of the lambda calculus

➔ The lambda calculus was introduced in the 1930s by the logician Alonzo Church at Princeton
University as a mathematical system for defining computable functions.
➔ Alan Turing (who was Church’s PhD student) showed that the lambda calculus is equivalent
in definitional power to Turing machines.
➔ The lambda calculus serves as the model of computation for functional programming
languages and has applications to artificial intelligence, proof systems, and logic.
➔ The programming language Lisp was developed by John McCarthy at MIT in 1958 around
the lambda calculus.
➔ Haskell, considered by many as one of the purest functional programming languages, was
developed by Simon Peyton Jones, Paul Houdak, Phil Wadler and others in the late 1980s
and early 90s.
➔ Many established languages such as C++ and Java and many more recent languages such as
Python and Ruby have adopted lambda expressions as anonymous functions from the lambda
calculus.
➔ Because of its simplicity, lambda calculus is a very useful tool for the study and analysis of
programming languages.

6
 The λ calculus can be called the smallest universal programming language of the world. The λ
calculus consists of a single transformation rule (variable substitution) and a single function
definition scheme.

Ex.
The Lambda Calculus: λx . ∗ 2 x
English: The function of x that returns the product of two and x.

2. Syntax of the Lambda Calculus

The lambda calculus derives its usefulness from having a sparse syntax and a simple semantics, and
yet it retains sufficient power to represent all computable functions. Lambda expressions come in
four varieties:
1. Variables, which are usually taken to be any lowercase letters.
2. Predefined constants, which act as values and operations are allowed in an impure or applied
lambda calculus .
Constant is a built-in function such as addition or multiplication, or a constant such as an integer or
boolean.
3. Function applications (combinations).
4. Lambda abstractions (function definitions). The simplicity of lambda calculus syntax is
apparent from a BNF specification of its concrete syntax:

7
3. Function Abstraction
● A function abstraction, often called a lambda abstraction, is a lambda expression that defines
a function.
● A function abstraction consists of four parts: a lambda followed by a variable, a period, and
then an expression as in λx.expr.
● In the function abstraction λx.expr the variable x is the formal parameter of the function and
expr is the body of the function.
● For example, the function abstraction λx. + x 1 defines a function of x that adds x to 1.
Parentheses can be added to lambda expressions for clarity. Thus, we could have written this
function abstraction as λx.(+ x 1) or even as (λx. (+ x 1)).
● In C this function definition might be written as

int addOne (int x)

{
return (x + 1);
}
● Note that unlike C the lambda abstraction does not give a name to the function. The lambda
expression itself is the function.
● We say that λx.expr binds the variable x in expr and that expr is the scope of the variable.

8
4. Function Application
● A function application, often called a lambda application, consists of an expression followed
by an expression: expr expr. The first expression is a function abstraction and the second
expression is the argument to which the function is applied. All functions in lambda calculus
have exactly one argument. Multiple-argument functions are represented by currying, which
we shall explain below.
● For example, the lambda expression λx. (+ x 1) 2 is an application of the function λx. (+ x 1)
to the argument 2.
● This function application λx. (+ x 1) 2 can be evaluated by substituting the argument 2 for the
formal parameter x in the body (+ x 1). Doing this we get (+ 2 1). This substitution is called a
beta reduction.
● Beta reductions are like macro substitutions in C. To do beta reductions correctly we may
need to rename bound variables in lambda expressions to avoid name clashes.
● Function application associates left-to-right; thus, f g h = (f g)h.
● Function application binds more tightly than λ; thus, λx. f g x = (λx. (f g)x).
● Functions in the lambda calculus are first-class citizens; that is to say, functions can be used
as arguments to functions and functions can return functions as results.

5. Free and Bound Variables

● In the function definition λx.x the variable x in the body of the definition (the second x) is
bound because its first occurrence in the definition is λx.
● A variable that is not bound in expr is said to be free in expr. In the function (λx.xy), the
variable x in the body of the function is bound and the variable y is free.
● Every variable in a lambda expression is either bound or free. Bound and free variables have
quite a different status in functions.

● In the expression (λx.x)(λy.yx):

9
 ○ The variable x in the body of the leftmost expression is bound to the first lambda.
○ The variable y in the body of the second expression is bound to the second lambda.
○ The variable x in the body of the second expression is free.
○ Note that x in second expression is independent of the x in the first expression.
● In the expression (λx.xy)(λy.y):
○ The variable y in the body of the leftmost expression is free.
○ The variable y in the body of the second expression is bound to the second lambda.
● Given an expression e, the following rules define FV(e), the set of free variables in e:
○ If e is a variable x, then FV(e) = {x}.
○ If e is of the form λx.y, then FV(e) = FV(y) − {x}.
○ If e is of the form xy, then FV(e) = FV(x) ∪ FV(y).
● An expression with no free variables is said to be closed.

6. Beta Reductions
● A function application λx.e f is evaluated by substituting the argument f for all free
occurrences of the formal parameter x in the body e of the function definition λx.e.
● We will use the notation [f/x]e to indicate that f is to be substituted for all free occurrences of
x in the expression e.
● Examples:
1. (λx.x)y → [y/x]x = y.
2. (λx.xzx)y → [y/x]xzx = yzy.
3. (λx.z)y → [y/x]z = z since the formal parameter x does not appear in the body z.
● This substitution in a function application is called a beta reduction and we use a right arrow
to indicate it.
● If expr1 → expr2, we say expr1 reduces to expr2 in one step.
● In general, (λx.e)f → [f/x]e means that applying the function (λx.e) to the argument
expression f reduces to the expression [f/x]e where the argument expression f is substituted
for the function's formal parameter x in the function body e.
● A lambda calculus expression (aka a "program") is "run" by computing a final result by
repeatly applying beta reductions. We use →* to denote the reflexive and transitive closure
of →; that is, zero or more applications of beta reductions.
● Examples:

10
 1. (λx.x)y → y (illustrating that λx.x is the identity function).
2. (λx.xx)(λy.y) → (λy.y)(λy.y) → (λy.y); thus, we can write (λx.xx)(λy.y) →* (λy.y).
Note that here we have applied a function to a function as an argument and the result
is a function.

7. Evaluating a Lambda Expression

● A lambda calculus expression can be thought of as a program which can be executed by
evaluating it. Evaluation is done by repeatedly finding a reducible expression (called a redex)
and reducing it by a function evaluation until there are no more redexes.
● Example 1: The lambda expression (λx.x)y in its entirety is a redex that reduces to y.
● Example 2: The lambda expression (+ (* 1 2) (− 4 3)) has two redexes: (* 1 2) and (− 4 3). If
we choose to reduce the first redex, we get (+ 2 (− 4 3)). We can then reduce (+ 2 (− 4 3)) to
get (+ 2 1). Finally we can reduce (+ 2 1) to get 3.
● Note that if we had chosen the second redex to evaluate first, we would have ended up with
the same result:
(+ (* 1 2) (− 4 3)) → (+ (* 1 2) 1) → (+ 2 1) → 3.

11
8. Currying
● All functions in lambda calculus are prefix and take exactly one argument.
● If we want to apply a function to more than one argument, we can use a technique called
currying that treats a function applied to more than one argument to a sequence of
applications of one-argument functions. For example, to express the sum of 1 and 2 we can
write (+ 1 2) as ((+ 1) 2) where the expression (+ 1) denotes the function that adds 1 to its
argument. Thus ((+ 1) 2) means the function + is applied to the argument 1 and the result is a
function (+ 1) that adds 1 to its argument: (+ 1 2) = ((+ 1) 2) → 3.

12
9. Renaming Bound Variables by Alpha Reduction
● The name of a formal parameter in a function definition is arbitrary. We can use any variable
to name a parameter, so that the function λx.x is equivalent to λy.y and λz.z. This kind of
renaming is called alpha reduction.
● Note that we cannot rename free variables in expressions.
● Also note that we cannot change the name of a bound variable in an expression to conflict
with the name of a free variable in that expression.
10. Eta Conversion
● The two lambda expressions (λx.+ 1 x) and (+ 1) are equivalent in the sense that these
expressions behave in exactly the same way when they are applied to an argument — they
add 1 to it. η-conversion is a rule that expresses this equivalence.
● In general, if x does not occur free in the function F, then (λx.F x) is η-convertible to F.
11. Substitutions
● For a beta reduction, we introduced the notation [f/x]e to indicate that the expression f is to
be substituted for all free occurrences of the formal parameter x in the expression e:
● (λx.e) f → [f/x]eTo avoid name clashes in a substitution [f/x]e, first rename the bound
variables in e and f so they become distinct. Then perform the textual substituion of f for x in
e.
1. For example, consider the substitution [y(λx.x)/x] λy.(λx.x)yx.

13
 2. After renaming all the bound variables to make them all distinct we get [y(λu.u)/x]
λv.(λw.w)vx.
3. Then doing the substitution we get λv.(λw.w)v(y(λu.u)).
● The rules for substitution are as follows. We assume x and y are distinct variables, and e, f
and g are expressions.
1. For variables
2. [e/x]x = e
[e/x]y = yFor function applications
3. [e/x](f g) = ([e/x]f) ([e/x]g)For function abstractions
● [e/x](λx.f) = λx.f
[e/x](λy.f) = λy.[e/x]f, provided y is not free in e (this is called the "freshness"
condition).Examples:
1. [y/y](λx.x) = λx.x
2. [y/x]((λx.y) x) = ([y/x](λx.y)) ([y/x]x) = (λx.y)y
3. Note that the freshness condition does not allow us to make the substitution
[y/x](λy.x) = λy.([y/x]x) = λy.y because y is free in the expression y.
12. Disambiguating Lambda Expressions
● The grammar we gave in section 4 for lambda expressions is ambiguous. A few simple rules
will remove the ambiguities.
● Function application is left associative: f g h = ((f g) h)
● Function application binds more tightly than lambda: λx.f g x = (λx.(f g) x)
● The body in a function abstraction extends as far to the right as possible: λx. + x 1 = λx. (+ x
1).
● We can always use parentheses to remove any ambiguities.
13. Practice Problems
1. Evaluate (λx. λy. + x y)1 2.
2. Evaluate (λf. f 2)(λx. + x 1).
3. Evaluate (λx. (λx. + (* x 1)) x 2) 3.
4. Evaluate (λx. λy. + x((λx. * x 1) y))2 3.
5. Is (λx. + x x) η-convertible to (+ x)?
6. Show how all bound variables in a lambda expression can be given distinct names.
7. Construct an unambiguous grammar for lambda calculus.

14
—------------------------------------------------------------------------------------------------------------------
Evaluation order
(Q. Explain the difference between applicative and normal order evaluation of expressions
with examples?)

Evaluation Strategy:
The different execution order of program codes is defined as evaluation strategy.
The stress is given to the functions (expressions contained within the function) and their arguments.
Different evaluation strategies have differences in their order of evaluation of arguments and their
substitution.
It is in terms of their evaluation and their substitution that take place.
In general, there are two evaluation strategies: strict evaluation and non-strict evaluation.
1. Strict evaluation (or eager evaluation)
- Applicative-order evaluation falls under strict and

2. non-strict evaluation
-Normal-order evaluation falls under non-strict strategy.
Strictness and Lazy Evaluation
• A function is said to be non strict —that is, if it is sometimes defined even when one of its
arguments is not.

15
 • A language is said to be strict if it is defined in such a way that functions are always strict.
• A language is said to be nonstrict if it permits the definition of nonstrict functions.
• If a language always evaluates expressions in applicative order, then every function is guaranteed to
be strict, because whenever an argument is undefined its evaluation will fail and so will the function
to which it is being passed.
• A nonstrict language cannot use applicative order; it must use normal order to avoid evaluating
unneeded arguments.
—-------------------------------------------------------------------------------------------------------------------
• An evaluation order - is a set of rules for evaluating expressions.
Types:
• Applicative Order
• Normal Order
1. Applicative order
• Always reduce the leftmost innermost redex.
• means to evaluate the arguments of a function application in left-to-right order.
• When we compute a function we usually assume that all arguments have a value before
the function evaluation begins.
• means to evaluate all the arguments to a function before evaluating the function.
2. Normal order
• Always reduce the leftmost outermost redex.
• means to evaluate the arguments of a function only when needed.
• Normal order reduction always chooses to reduce first the leftmost expression.
• In non-strict evaluation arguments need not be evaluated until they are actually required.
• Lazy evaluation is a form of non-strict evaluation in which arguments are not evaluated
until required.
Evaluating the expression (double (* X Y) 3 4)
in applicative order (Scheme)
(double (* 3 4))
=⇒ (double 12)
=⇒ (+ 12 12)
=⇒ 24
normal-order evaluation

16
 (double (* 3 4))
=⇒ (+ (* 3 4) (* 3 4))
=⇒ (+ 12 (* 3 4))
=⇒ (+ 12 12)
=⇒ 24
Here we end up doing extra work: normal order causes us to evaluate (* 3 4)
twice.

Sr.No. Applicative Order Normal Order

01 Always reduce the leftmost innermost Always reduce the leftmost

redex. outermost redex.

02 means to evaluate the arguments of a means to evaluate the arguments of a

function application in left-to-right order. function only when needed.

03 When we compute a function we usually Normal order reduction always

17
 assume that all arguments have a value chooses to reduce first the leftmost
before the function evaluation begins. expression.

04 (double (* 3 4)) (double (* 3 4))

=⇒ (double 12) =⇒ (+ (* 3 4) (* 3 4))
=⇒ (+ 12 12) =⇒ (+ 12 (* 3 4))
=⇒ 24 =⇒ (+ 12 12)
=⇒ 24

05 Applicative-order evaluation falls under Lazy evaluation is a form of non-strict

strict . evaluation in which arguments are not
• A language is said to be strict if it evaluated until required.
defined in such a way that functions a
always strict.

06 Evaluate the arguments before the Evaluate function before its arguments
function itself

—------------------------------------------------------------------------------------------------------------------

18
Q.Explain the TYPE and TYPE classes in Haskell
Haskell is a functional language and it is strictly typed, which means the data type used in the entire
application will be known to the compiler at compile time.

Inbuilt Type Class

In Haskell, every statement is considered as a mathematical expression and the category of this
expression is called as a Type. You can say that "Type" is the data type of the expression used at
compile time.

To learn more about the Type, we will use the ":t" command. In a generic way, Type can be
considered as a value, whereas Type Class can be the considered as a set of similar kind of Types. In
this chapter, we will learn about different Inbuilt Types.

A type is a kind of label that every expression has. It tells us in which category of things that
expression fits. The expression True is a boolean, "hello" is a string, etc.

Now we'll use GHCI to examine the types of some expressions. We'll do that by using the :t
command which, followed by any valid expression, tells us its type. Let's give it a whirl.

ghci> :t 'a'
'a' :: Char
ghci> :t True
True :: Bool
ghci> :t "HELLO!"
"HELLO!" :: [Char]
ghci> :t (True, 'a')
(True, 'a') :: (Bool, Char)
ghci> :t 4 == 5
4 == 5 :: Bool

19
Int
Int is a type class representing the Integer types data. Every whole number within the range of
2147483647 to -2147483647 comes under the Int type class. In the following example, the function
fType() will behave according to its type defined.

Float
Take a look at the following piece of code. It shows how Float type works in Haskell

Double
Double is a floating point number with double precision at the end. Take a look at the following
example −

Char
Char represent Characters. Anything within a single quote is considered as a Character. In the
following code, we have modified our previous fType() function to accept Char value and return
Char value as output.

20
The above piece of code will call fType() function with a char value of 'v' but it returns another char
value, that is, 'K'.

EQ Type Class
EQ type class is an interface which provides the functionality to test the equality of an expression.
Any Type class that wants to check the equality of an expression should be a part of this EQ Type
Class.

All standard Type classes mentioned above is a part of this EQ class. Whenever we are checking any
equality using any of the types mentioned above, we are actually making a call to EQ type class.

In the following example, we are using the EQ Type internally using the "==" or "/=" operation.

Ord Type Class

Ord is another interface class which gives us the functionality of ordering. All the types that we have
used so far are a part of this Ord interface. Like EQ interface, Ord interface can be called using ">",
"<", "<=", ">=", "compare".

21
Show
Show has a functionality to print its argument as a String. Whatever may be its argument, it always
prints the result as a String. In the following example, we will print the entire list using this interface.
"show" can be used to call this interface.

It will produce the following output on the console. Here, the double quotes indicate that it is a
String type value.

Read
Read interface does the same thing as Show, but it won’t print the result in String format. In the
following code, we have used the read interface to read a string value and convert the same into an
Int value.

Here, we are passing a String variable ("12") to the readInt method which in turn returns 12 (an Int
value) after conversion.

22
Functions:
Functions play a major role in Haskell, as it is a functional programming language. Like other
languages, Haskell does have its own functional definition and declaration.
​ Function declaration consists of the function name and its argument list along with its
output.
​ Function definition is where you actually define a function.
Let us take a small example of an add function to understand this concept in detail.
add :: Integer -> Integer -> Integer --function declaration
add x y = x + y --function definition

main = do
putStrLn "The addition of the two numbers is:"
print(add 2 5) --calling a function

Here, we have declared our function in the first line and in the second line, we have written our
actual function that will take two arguments and produce one integer type output.
Like most other languages, Haskell starts compiling the code from the main method. Our code will
generate the following output −
The addition of the two numbers is:
7

Recursion Function
Recursion is a situation where a function calls itself repeatedly. Haskell does not provide any facility
of looping any expression for more than once. Instead, Haskell wants you to break your entire
functionality into a collection of different functions and use recursion technique to implement your
functionality.
Let us consider example again, where we have calculated the factorial of a number. Finding the
factorial of a number is a classic case of using Recursion. Here, you might, "How is pattern
matching any different from recursion?” The difference between these two lie in the way they are

23
used. Pattern matching works on setting up the terminal constrain, whereas recursion is a function
call.
In the following example, we have used both pattern matching and recursion to calculate the
factorial of 5.

Example:
fact :: Int -> Int
fact 0 = 1 Fact 3
fact n = n * fact ( n - 1 ) =3*(3-1)
main = do =3*fact(2)
putStrLn "The factorial of 3 is:" =3*2*fact(2-1) =3*2*f(1)
print (fact 3) =3*2*1*f(1-1) =3*2*1*f(0) =3*2*1*1
=6

Ex-
3!= 3*2*1=6
5!=5*4*3*2*1=120

Higher order functions

In mathematics and computer science, a higher-order function (HOF) is a function that does at
least one of the following:
● takes one or more functions as arguments (i.e. a procedural parameter, which is a
parameter of a procedure that is itself a procedure),
● returns a function as its result.
Definition- A function is called higher-order if it takes a function as an argument or returns a function
as a result.
twice :: (a → a) → a → a
twice f x = f (f x)
- twice is higher-order because it takes a function as its first argument.

24
Inbuilt higher order function
Map Function:
The higher-order library function called map applies a function to every element of a list.
map :: (a → b) → [a] → [b]
- it maps one list of type [a] to another list of type [b] using the function (a->b).
For example:
> map (+1) [1,3,5,7]
[2,4,6,8]
> map (*2) [1,3,5,7]
[2,6,10,14]

• The map function can be defined in a particularly simple manner using a list comprehension
map f xs = [f x | x ← xs]

The Filter Function

•The higher-order library function filter selects every element from a list that satisfies a predicate.
filter :: (a → Bool) → [a] → [a]
:: symbol stands for “is of the type”.
For example:
> filter even [1..10]
[2,4,6,8,10]
Filter can be defined using a list comprehension: filter p xs = [x | x ← xs, p x]
•Alternatively, it can be defined using recursion: filter p [] = []
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xs

The Foldr Function

• A number of functions on lists can be defined using the following simple pattern of recursion:
f [] = v

25
 f (x:xs) = x ⊕ f xs
f maps the empty list to some value v, and any non-empty list to some function ⊕ applied to its head
and f of its tail
For example:
sum [] = 0
sum (x:xs) = x + sum xs v=0 ⊕=+
product [] = 1
product (x:xs) = x * product xs v=1, ⊕=*

and [] = True
and (x:xs) = x && and xs v = true ⊕ = &&

The higher order library function folder (fold right) encapsulates this simple pattern of recursion with
the function ⊕ and the value v as argument.

• For example: Ex: sum [1,2,3]

sum = foldr (+) 0 =foldr (+) 0 [1,2,3]
product = foldr (*) 1 = foldr (+) 0 (1:(2:(3:[])))
or = foldr (||) False = 1+(2+(3+0))
and = foldr (&&) True =6

Foldr itself can be defined using recursion:

foldr :: (a → b → b) → b → [a] → b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)
• The library function (.) returns the composition of two functions as a single function.
(.) :: (b → c) → (a → b) → (a → c)
f . g = λx → f (g x)
For example:
odd :: Int → Bool

26
 odd = not . Even

The library function all decides if every element of a list satisfies a given predicate.
all :: (a → Bool) → [a] → Bool
all p xs = and [p x | x ← xs]
For example:
> all even [2,4,6,8,10]
True
• The library function any decides if at least one element of a list satisfies a predicate.

any :: (a → Bool) → [a] → Bool

any p xs = or [p x | x ← xs]

For example:
> any isSpace "abc def“
True
• The map function takes another function and a list as arguments and applies that function to
each element in the list:

GHCi> map reverse ["dog","cat", "moose"]

["god","tac","esoom"]
GHCi> map head ["dog","cat", "moose"]
"dcm"
GHCi> map (take 4) ["pumpkin","pie","peanut butter"]
["pump","pie","pean"]

Lambda Expression

We sometimes have to write a function that is going to be used only once, throughout the entire
lifespan of an application. To deal with this kind of situations, Haskell developers use another
anonymous block known as lambda expression or lambda function.

27
A function without having a definition is called a lambda function. A lambda function is denoted
by "\" character. Let us take the following example where we will increase the input value by 1
without creating any function.
main = do
putStrLn "The successor of 4 is:"
print ((\x -> x + 1) 4)
Here, we have created an anonymous function which does not have a name. It takes the integer 4
as an argument and prints the output value. We are basically operating one function without even
declaring it properly. That's the beauty of lambda expressions.
Our lambda expression will produce the following output −
sh-4.3$ main
The successor of 4 is:
5
—----------------------------------------------------------------------------------------------------------------

Haskell List:
The basic datastructure in Haskell is the list. Lists are used to store multiple values of the
same type
Example:
[0,3,4,7]
A list type is written as [Element], where Element is the type of the list elements. Here
are some more
list expressions and their types:
[True,True,False] :: [Bool]
["Moi","Hei"] :: [String]
[] :: [a] -- more about this later
[[1,2],[3,4]] :: [[Int]] -- a list of lists
[1..7] :: [Int] -- range syntax, value [1,2,3,4,5,6,7]

List Operations:
head :: [a] -> a -- returns the first element

28
 tail :: [a] -> [a] -- returns everything except the first element
init :: [a] -> [a] -- returns everything except the last element
take :: Int -> [a] -> [a] -- returns the n first elements
drop :: Int -> [a] -> [a] -- returns everything except the n first
elements
(++) :: [a] -> [a] -> [a] -- lists are catenated with the ++ operator
(!!) :: [a] -> Int -> a -- lists are indexed with the !! operator
reverse :: [a] -> [a] -- reverse a list
null :: [a] -> Bool -- is this list empty?
length :: [a] -> Int -- the length of a list

Program:Implement Haskell code to represent an infinite list.

main = do
putStrLn "Simple list operations in Haskell !!"
let list1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
putStrLn "The list Elements are"
print list1
putStrLn "The head of the list is"
print (head list1)
putStrLn "Reverse of a list is"
print (reverse list1)
putStrLn "Length of the list is"
print (length list1)
putStrLn "After dropping 3 elements:"
print (drop 3 list1)
putStrLn "First 3 elements:"
print (take 3 list1)

29
 putStrLn "All elements except the last one:"
print (init list1)

Output:

—-------------------------------------------------------------------------------------------------
I/O Streams and Monads
• Batch programs that take all their inputs at the start and give all their outputs at the end
• Interactive programs that read from the keyboard and write to the screen, as they are running
• Haskell programs are pure mathematical functions
–no side effects
• Interactive programs have side effects.
• Interactive programs can be written in Haskell by using types to distinguish pure expressions from
impure actions that may involve side effects
• One way to avoid these side effects is to model input and output as streams.
• Haskell it is used to describe computations as sequences of steps, and to handle side effects such as
state and IO.
• Monads are abstract, and they have many useful concrete instances. Monads provide a way to

30
structure a program.
• IO Char - The type of actions that return a character
• IO () - The type of purely side effecting actions that return no result value. Three primitives:
1. getChar :: IO Char
The action getChar reads a character from the keyboard and returns the character as its result value
2. putChar :: Char → IO ()
The action putChar c writes the character c to the screen, and returns no result value
3. return :: a → IO a
The action return a simply returns the value a, without performing any interaction
Sequencing:
A sequence of actions can be combined as a single composite action using the keyword do.
For example:
Sequencing a :: IO (Char,Char)
a = do
x ← getChar
y ← getChar
return (x,y)
Reading a string from the keyboard
getLine :: IO String
getLine = do
x ← getChar
if x == '\n' then
return []
else
do xs ← getLine
return (x:xs)
Writing a string to the screen
putStr :: String → IO ()
putStr [] = return ()
putStr (x:xs) = do putChar x
putStr xs

31
Writing a string and moving to a new line: putStrLn :: String → IO ()
putStrLn xs = do putStr xs
putChar '\n’
• We can now define an action that prompts for a string to be entered and displays its length
strlen :: IO ()
strlen = do putStr "Enter a string: "
xs ← getLine
putStr "The string has “
putStr (show (length xs))
putStrLn " characters"
Output:
Enter a string: college
The string has 7 characters

32
33
Reference:
http://www.cs.columbia.edu/~aho/cs3261/Lectures/L23-Lambda_Calculus_I.html#:~:text=A%20
function%20application%2C%20often%20called,calculus%20have%20exactly%20one%20argu
ment.

http://www.cs.columbia.edu/~sedwards/classes/2010/w4115-summer/functional.pdf

https://www.tutorialspoint.com/haskell/haskell_functions.htm
https://www.tutorialspoint.com/haskell/haskell_more_on_functions.htm

34