This section just consists of one lecture split across two videos. The lecturer Erik Meijer introduces the course and discusses the content.
Introduction - Part 1
This video covers Functional Programming in general and introduces Haskell.
He stresses the fact that the course is not directly about Haskell but more Functional Programming in general and Haskell is just the chosen language for teaching purposes. In order to produce complex software all modern programming languages have features that enable abstractions to be made and help to make software clear and concise.
Functional programming is based on concepts from the Lambda calculus and Haskell as a pure functional programming language is a good choice for learning these concepts. The concepts can be applied to how you program in any language though.
Definitions of functional programming
He talks about different ways of defining functional programming. In a situation where you are talking about a purely functional programming language such as Haskell it is possible to use a more purist definition such as:
Purist definition: Functional programming is a style of programming in which the basic method of computation is the application of functions to arguments.More generally speaking though if you working in a language that is not a specifically functional one you can use a looser definition.
General definition: Functional programming is a style of programming in which expressions are more important than statements.A functional languages is one that supports or encourages the functional style. Many modern programming languages support this style of programming. A key feature of a programming language that makes it more amenable to programming in a functional style is if it has support for lambda expressions.
Example of Functional programming
Functional programming is contrasted with programming in an imperative style by using the example of summing the integers 1 to 10.
In Java the code would look like this:
The corresponding program written in Haskell is much simpler:
It was mentioned that a similar effect can be achieved in Java from versions 8 inwards using the streams feature of the language.
This code is an implementation of the quicksort algorithm. The program defines two cases.
In the first case:
In the second case:
So for a non-empty list (x:xs), that list is sorted by taking the head of the list x , then combining three lists in sequence:
The where clause:
Since the definition of the algorithm makes use of itself calling the function again on the sub-lists of ys and zs the algorithm is said to be recursive in nature.
This program illustrates the algorithmic structure of Quicksort and works by creating new lists. It differs from typical imperative implementations of the Quicksort work by modifying elements of the list in place.
int total = 0;
for (int i = 1; i<10; ++i) {
total = total+i;
}
Here the emphasis is on statements and the computation method is variable assignment. The program relies on mutable program state, in this case a variable called 'total', which is repeatedly updated.The corresponding program written in Haskell is much simpler:
In the Haskell version there are no statements, only two expressions. The expression [1..10] defines a list of the integers from 1 to 10. The function sum takes this list as an argument.sum [1..10]
It was mentioned that a similar effect can be achieved in Java from versions 8 inwards using the streams feature of the language.
Introduction - Part 2
The second video in the Introduction section focuses more on the history of Haskell.
1930s
- Alonzo Church developed the lambda calculus a simple but powerful theory of functions.
1950s
- John McCarthy developed Lisp which is the first functional language. Lisp is influenced by lambda calculus yet also includes variable assignment.
1960s
- Peter Landin developed ISWIM which was the first pure functional programming language. ISWIM was influenced strongly by lambda calculus and has no variable assignment.
1970s
- John Backus developed the functional programming language FP which was designed to support higher-order functions and reasoning about the correctness of the program.
- Robin Milner along with others developed the functional programming language ML. Considered to be the first modern functional language, ML introduced type inference and parametric polymorphism. ML is a hybrid programming language that includes functional programming ideas as well as variable assignment. It was originally conceived as a scripting language.
1970s - 1980s
- David Turner developed several functional languages including SASL which exhibited lazy evaluation. This eventually led to the development of the Miranda.
1987
- An international committee of researchers started Haskell with the intention of creating a standard platform for experimenting with functional language ideas.
2003
- The committee published the Haskell 98 report defining a stable version of the language.
2003 - present (2016)
- The Haskell Platform provides a standard implementation of Haskell GHC as well as the standard libraries, build system and other commonly used development tools.
A Taste of Haskell
To illustrate how Haskell works the later part of the video goes through an example program.
f [] = []
f (x:xs) = f ys ++ [x] ++ f zs
where
ys = [a | a ← xs, a ≤ x]
zs = [b | b ← xs, b > x]
In the first case:
the list [] to be sorted is empty and so, trivially, it is already sorted so that the result is just the empty list.f [] = []
In the second case:
The list (x:xs) is not empty but consists of a head element x and a tail list xs (which may be empty).f (x:xs) = f ys ++ [x] ++ f zs
So for a non-empty list (x:xs), that list is sorted by taking the head of the list x , then combining three lists in sequence:
- the list that results from applying the sorting function to all those elements from the tail list xs that are less than or equal to the head element: f ys , followed by,
- a list that contains just the head element [x], followed by,
- the list that results from applying the sorting function to all those elements from the tail of the list that are greater than the head element f zs .
The where clause:
where
ys = [a | a ← xs, a ≤ x]
zs = [b | b ← xs, b > x]
defines the two lists: ys, which is all the elements from xs which are less than or equal to x; and zs which is all the elements from xs which are greater than x.Since the definition of the algorithm makes use of itself calling the function again on the sub-lists of ys and zs the algorithm is said to be recursive in nature.
This program illustrates the algorithmic structure of Quicksort and works by creating new lists. It differs from typical imperative implementations of the Quicksort work by modifying elements of the list in place.
No comments:
Post a Comment