Virtual Reality in Education: How VR is Used in Immersive Learning
We explore what virtual reality is, how it works, ways that it can be used …
Home / IT & Computer Science / Coding & Programming / Functional Programming in Haskell: Supercharge Your Coding / Key Constructs and Functions in Haskell
Key Constructs and Functions in Haskell
In this video, Wim Vanderbauwhede explains how key constructs in a functional language are really just syntactic sugar over lambda functions.
WIM: Hello, everyone. In this optional video, I want to explain that, really, in functional languages there are only functions. What I want to do is give you a quick intuition how we can remove all the syntactic sugar from a functional language and reduce it to only lambda functions. So the full elaboration of how you can do this is explained in the article on the site. We will just cover the basic ideas. So let’s start with the let construct. Suppose we have something like– so we a let block, where we have n is assigned to 10, and we define the function f of x being x plus 1. And we apply f to n.
So basically the whole thing should return 11. So, we want to rewrite this so that there will only be lambda functions left. So the obvious first rewrite we can do is rewrite this function definition of the lambda. So, very simply.
OK. So then the next thing we will do is, we have a let that contains two variables, and we will essentially do the equivalent of currying in the let blocks. So we will transform this let block in a nest of let blocks. So what we’re doing is–
OK. So now we have a nested let. Now we have this let expression, with just a single variable here, and we can rewrite this as a lambda expression as follows. So I’ll just put it on this side here.
So this whole let block here is actually entirely equivalent to a lambda function applied to the function that defines f. So we bind f to this function, and apply it to n. So all we have to do is do the same for other let. And that’s quite simple. So we take the other let and transform it into a lambda expression, which says, basically, we have n applied to this construct here. And apply to 10. So if we just straighten it out a bit, we get–
So we have transformed the whole nested let into a series of lambdas. This you can see, it’s entirely equivalent, but it’s a lot less easy to type, which is why the let syntax is available in the language of course.
So the next thing we want to do is see if we can define conditional expressions, and so on. And for that we need to define the values of true and false. You might wonder, how can we define the values of true and false without having any numbers, because remember we’re going to use only functions, so even numbers are not defined yet. So it’s actually quite easy. We define true and false as functions. So we say true is defined as a function of two elements, which returns the first element. And false is a function of two elements which returns the second elements. And that’s all there is to it.
This is our– this is by definition, in our system, true and false. And now we can use these values of true and false, these definitions to define things like if then else constructs, or– Let’s do that next. So, in if then else– so that in Haskell it looks if condition then if true else if false. So condition, if true and if false are expressions in their own right, condition evaluates to true or false. So the first thing is this if then else, we know it’s an expression. And it’s actually just syntactic sugar for a function, and we will call this function if then else. So we have if then else condition if true if false.
So this is our first step in removing some syntactic sugar. So now with these definitions for true and false, it turns out that the definition of this if then else is actually quite simple. It is very simply– because remember, condition evaluates to true or false. So it must return one of these two functions. These are functions of two elements, that return either the first or the second. So if it’s this one, then condition will return this. If that one, condition will return that. So this way, we have defined if then else.
Neat, huh?
Finally, I want to show how to define lists. So let’s say we have a list which is just 1, 2, 3. We already know from what we’ve seen earlier that this bracket syntax for list is actually syntactic sugar for a combination of the cons operation and the empty list. So we know that this is entirely equivalent to saying 1, 2, 3 empty list. Or written out more explicitly using the cons function.
So what we have to do now is define cons and the empty list using lambda functions and nothing else. And we will use the same trick again of using– defining a function that returns a function, because we have nothing else, remember? So we define cons as a lambda function of x and xs, which returns, in its own right, a function that operates on x and xs.
So this is– because we don’t want any syntactic sugar, so normally cons is of course a function of x and y. We’ve rewritten it as a variable binding to a lambda expression. And this lambda expression in x and xs returns this particular function. So all we need now is the empty list. And this is again very simple. So we define the empty list as a function of anything to true. And the reason for this, why it has to be true, is because we will work on from this and define things like test for emptiness of the list, and length of the list, and so on. And with this definition the whole system is consistent.
So in the same fashion you can define tuples and then you can go on to define list operations, recursions, folds, maps. And then you can go on to define numbers simply by saying that you have a 0, of some arbitrary starting point, and then a function that always defines the next number, and so on. All that is explained in the article in more detail. But in this way, we can define our complete language in terms of nothing else than lambda functions. So really, there are only functions. OK.
In a Functional Language, There are Only Functions
Although it might seems that a language like Haskell has a lot of different objects and constructs, we can express all of them in terms of functions. Watch the video to get a little insight, then read on to find out more …Variables and let
letn = 10f x = x+1inf n-- One variable per let => letn = 10inletf x = x+1inf n-- Rewrite f as lambda =>letn = 10inletf = \x -> x+1inf n-- Rewrite inner let as lambda =>letn = 10in(\f -> f n) (\x -> x+1)-- Rewrite outer let as lambda =>( \n -> ((\f -> f n) ( \x -> x+1 )) ) 10Tuples
tp = (1,"2",[3])4.8
28 Reviews
-
FP with Haskell
Is a course that has the foundations for any begginer is clear and good for introduce to the fp world in a beautiful a lang as Haskell
Anderson S. -
Functional Programming in Haskell
I think this was a great course. I am working in Elixir, but have always wondered what Haskell “was all about”? This course was a great introduction. And it answered ...ExpandMark S. -
Very productive course
Excellent course. Covers fundamentals and easy to follow online. I like the overall course outline and the mixture of videos, text, exercises and quizzes, Also the comments sections with feedback ...ExpandArthur A. -
Great introduction to Haskell and functional programming
It was a quite comprehensive introduction to Haskell and functional programming in general
Neo M. -
excellent course
It is a excellent course to introduce FP, the content is good with short video combining with articles. It would be nice if there are more exercises in each lesson....ExpandTortoise T.
tp = mkTup 1 "2" [3] mkTup = \x y z -> \t -> t x y z fst tp = tp (\x y z -> x)snd tp = tp (\x y z -> y)Lists
Lists can be defined in terms of the empty lists[] and the cons operation (:).
ls = [1,2,3]Rewrite using : and [] =>ls = 1 : 2 : 3 : [] ls = cons 1 (cons 2 (cons 3 []))Defining cons
We can define cons using only lambda functions as
cons = \x xs ->\c -> c x xs ls = cons 1 (...)= \c -> c 1 (...)head and tail using only lambdas:
head ls = ls (\x y -> x)tail ls = ls (\x y -> y)The empty list
We can define the empty list as follows: [] = \f -> truetrue and false are given below under Booleans.
Then we can check if a list is empty or not:
isEmpty lst = lst (\x xs -> false) lst = x:xs(:) is
lst = (\x xs -> \c -> c x xs) x xs= \c -> c x xs isEmpty lst= isEmpty (\c -> c x xs)= (\c -> c x xs) (\x xs -> false)= falseisEmpty []= isEmpty (\f -> true)= (\f->true) (\x xs -> false)= trueRecursion on lists
Now that we can test for the empty list we can define recursions on lists such asfoldl, map etc.:
foldl f acc lst =if isEmpty lstthen accelse foldl f (f (head lst) acc) (tail lst) map f lst =letmap' f lst lst' = if isEmpty lst then (reverse lst') else map' f (tail lst) (head lst: lst')inmap' f lst [] reverse lst = (foldl (\acc elt -> (elt:acc)) [] lstfoldl and map use an if-then-else expression which is defined below under Conditionals.
List concatenation
(++) lst1 lst2 = foldl (\acc elt -> (elt:acc)) lst2 (reverse lst1)The length of a list
To compute the length of a list we need integers, they are defined below. length lst = foldl calc_length 0 lstwherecalc_length _ len = inc lenConditionals
We have used conditionals in the above expressions: if cond then if_true_exp else if_false_expcond is an expression returning either true or false, these are defined below.
We can write the if-then-else clause as a pure function:
ifthenelse cond if_true_exp if_false_expBooleans
To evaluate the condition we need to define booleans: true = \x y -> xfalse = \x y -> y ifthenelse cond if_true_exp if_false_exp = cond if_true_exp if_false_expBasic Boolean operations: and, or and not
Using ifthenelse we can define and, or and not:
and x y = ifthenelse x (ifthenelse y true) falseor x y = ifthenelse x true (ifthenelse y true false)not x = ifthenelse x false trueBoolean equality: xnor
We note that to test equality of Booleans we can use xnor, and we can of course define xor in terms of and, or and not:
xor x y = (x or y) and (not x or not y) xnor x y = not (xor x y)Signed Integers
We define an integer as a list of booleans, in thermometer encoding, and with the following definitions: We define usigned 0 as a 1-element list containingfalse. To get signed integers we simply define the first bit of the list as the sign bit. We define unsigned and signed versions of 0:
u0 = false:[]0 = +0 = true:u0-0 = false:u0 isPos n = head nisNeg n = not (head n)isZero n = not (head (tail n))sign n = head nInteger equality
The definition of0 makes the integer equality (==) easier:
(==) n1 n2 = lets1 = head n1s2 = head n2b1 = head (tail n1)b2 = head (tail n2)if (xnor s1 s2) thenif (and (not b1) (not b2))then trueelseif (and b1 b2)then (==) (s1:(tail n1)) (s2:(tail n2))else falseelse falseNegation
We can also easily define negation: neg n = (not (head n)):(tail n)Increment and Decrement
For convenience we define also define increment and decrement operations: inc n = if isPos n then true:true:(tail n) else if isZero n then 1 else false:(tail (tail n))dec n = if isZero n then -1 else if isNeg n then false:true:(tail n) n else true:(tail (tail n))Addition and Subtraction
General addition is quite easy: add n1 n2 = foldl add_if_true n1 n2whereadd_if_true elt n1 = if elt then true:n1 else n1 sub n1 n2 = foldl sub_if_true n1 n2wheresub_if_true elt n1 = of elt then (tail n1) else n1Multiplication
An easy way to define multiplication is by defining thereplicate and sum operations:
replicate n m =letrepl n m lst = if n==0 then lst else repl (dec n) m (m:lst)inrepl n m []sum lst = foldl add 0 lst mult n m = sum (replicate n m)Floats, Characters and Strings
We note that floats and chars use an integer representation, and strings are simply lists of chars. So we now have a language that can manipulate lists and tuples of integers, floats, chars and strings.This article is from the online course:
Functional Programming in Haskell: Supercharge Your Coding
Created by
-
-
An introduction to project management – How to manage projects effectively
Learn the basics of project management, why it’s such a valuable skill, and the tools … -
The importance of exercise for health and wellbeing
Just how important is exercise to our wellbeing? In this article, we explore the connection … -
An introduction to web analytics
We take a deep dive into the world of web analytics, and the importance of …
This article is from the free online
Functional Programming in Haskell: Supercharge Your Coding
Our purpose is to transform access to education.
We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.
We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.
Learn more about how FutureLearn is transforming access to education
