welcome everybody to this
episode of functional programming 101
and this lecture we're going to do something slightly different
we're not going to introduce Neil concepts
what we're going to do is we're going to show you
how 8 temple Kol an
developments transformational development
of programs in Haskell works an
so the general pattern as that
you start red and obviously correct solution
that usually uses a lot of brute force
and is cheaper and efficient and then
usury factoring to make it more efficient
right the first goal is a ride is simplest program
that works no matter how inefficient it is
and then you start re factoring it so
there's many similarities with you know extreme programming and things like that
you know
just do the men all things to make it work and then later
we welcome have tried to optimize it and maybe it's not necessary to optimize
because even if something is spread Reddick maybe you never use it on big &
Boch
a or all the inputs that you get can rerun in reasonable time
and you can spend your time other on other things show
no premature optimization make sure
that things are correct first and then optimize
later month Inc we won't show here
is that you again also take your hat school code
use it as a prototype once you're happy with it
you and emblem and the same
algorithm in another language that this may be more efficient but
ya and depending
on that particular program it mites the
Haskell Compiler might already good do a good job
but sometimes is not just about speech that you want to use a different
language
but it is because
and in your company at they're not using haskell but say at Php
K and remember one of the models of this course
is think like a fundamentalist
but gold like a hacker I'd so
and this is what we will see here we start it very fundamentalist saying it
has to be correct
and then we gonna be a lil HEC on the code
to make it more efficient and abroad the
problem we're going to look at is a show called
Condon problem and come down problem
is based on a quest program on British TV that has been there for a while
as originally based on a French TV show
an and in that show
there's a a game that a.m. recall here
take on time problem and if you
Google for should go crucial for an ass call or
if you read and have Richard birch papers you will
see very similar development this is
a.m. very idiomatic a Haskell development
let's look at what this goddamn problem is first in an informal way
we need to do is given
a set of numbers and the standards
operators addition the getting
and subtraction and multiplication and division
we need to create an expression who is
value is some given values in this case we say
we have too great an expression whose value is 6
a 765 now for humans
this can be hard because the search space
as rather bake so we have to go to dry all possible combinations right brain
disease
and whatever to find the answer so this is fun in a quiz show
an and some people are really good at it can do it fast other people
got bail an but this is something computers are good at
right because computers have infinite patience
show they can charger dish am church-based
and find a solution and if we can restrict the search page enough
it might even be able to find the solutions
very quickly and that will be the case
for this example K there's a couple more rows
I'm is that all numbers including
intermediate results must be natural numbers they must be positive
each of the numbers in the original Sat
can be used only once an
and then there's another show the brawls but you know
we keep things simple i right here so
in particular that should get a possible solution
am in our case I'm using the numbers
25 1050 and long we can create
7-under 65 as follows: and notice that
ya 25 -10 is a positive number
fifty plus one is a positive number and
when you multiply to positive numbers they are
an positive as well alright
so for this particular example the search space
consist of 780 possible solutions
and but if we should lightly change
the a result value then
generally we can find no solution okay
so we go from 780 possible solutions
to notion ish okay
that start to build this a solution to this program
bottom-up as they were going to start
by building the pieces and then we glue everything together to solve the problem
up iraq
on make a mess
okay every cup so what we're going to do
sure it will be fine are
an operators as an algebraic data type so we have addition
subtraction multiplication and division and what we're going to do is we're
going to define
a evaluation function that takes to
numbers and applies
the operator okay and its
straightforward whenever you want to add two numbers
you add two numbers whenever wherever you want to ship struck them you should
check them
et cetera and the region where using
this representation and not immediately evaluating them
is because we want to build and
and symbolic representation of the expression
an because we we don't want to find the number
765 we want to find an expression that when you evaluate it
well a.m. return this number
so we want to do symbolic processing of
a.m. expressions and then once you have an expression we can
evaluated reddish function knowledge and goat
and the rules of the game so one of the rules loss
that an every operator
must be applied to positive numbers
so let's check whether when we
apply an operator that its FL
application of that operate show every at two numbers
well we don't have to check egos
if we add to positive numbers the result will be positive
every ship tracks two numbers we must make sure
that the first number is bigger than the second number
because otherwise the result would be negative and that there's not a lot
multiplying to positive numbers
is always positive and when we divide two numbers
we have to check that they are actually
die visible because otherwise we don't get
a natural number
okay and now we can define the data type
of expressions just ever as we have seen
be four so we have an slightly different instead of having like
have separate operate as a separate constructor for each operator we have
Wong application that takes these operators
good so how can we evaluate an expression
well we evaluate an expression
and we either return a single din list
that contains the value or
when the expression is not valid
anywhere inside we return the anti listed
and you will recognize this trick
from our partners right are bars is also
returned either and MD lest when they failed
are singled unless to read the results Monday succeeded
we don't know we don't use the maybe type
were using last because it much more convenient
a ride so if you are has school programmer
and you're using it may be dyed please reconsider to use lists
because as you see here an
its its little bit and nicer because you can use
list comprehension like this okay
show that see how devaluation works again
is defined recursively over expressions
we either have a value well in that case it succeeds
if the expression
is the value is greater than 0 and every
have an expression that is the application oven operator to to ship
expressions
what do we do we evaluated the left hand side
we've evaluate the right and shiet recheck
that the application of this operator dude East numbers is that let
and if that's the case be return
that application there
gays or really what you see here is dead engine
evaluation intermixed with a filter
for only valid sup expressions I
to now lets them but they had to formalize the problem there's a
a few more help for French is that we need and these helper functions I will
just issue that they exist
but I am you now you will get them
in your exercises so an Hannah
I can make sure that they exist but you will have to define them
that's the yeah the advantage of teaching a course
so the first function here that we're going to use is Joyce's
so joyce's takes a list of values of Taipei
and readers a list of lists that
issue all possible ways of choosing zero or more
elements from this a.m. input list
thank it's not as
complicated Shasha sugar at a concrete example
so I want to have all the choices on the list want to
these are all the possible ways of choosing zero or more elements from that
list so
I can choose 0 Allemands I could use one al amanecer that can be one or two
and then I can choose want to
Oregon jewish tu wong biggest at
those are two possible ways to choose to values
from that list alright so you see
that thing here and again I will issue
that this function exists you will have to define that
in the exercises now we can define a new function
that given an expression returns
a list of all the values and
show all the value show while our dollar stores are all the values and beliefs
so if I ever value I returned a single the last
if I have the publication of whatever operator
I take the value shoved a left
expression and combine them redevelop use
up
right self-expression so now we can
decides if some expression is a solution
for a given list of numbers by
more or less directly translating the rules the game
in tunis haskell program show given an expression
this is our list of initial numbers and
this is our target number now we have to check
whether dish expression here is a solution
to the problem okay so what this says is dead
first of all the expression must evaluate
to the number that were looking for a show that was a number that we're
required to find show
I'm evaluate the expression it must
and use that number and then
when we take all the values in that expression
everyday call the possible choices
for the input numbers
that thing deadliest
must be a member of that list
right so if you go back
to the English description of the comedown problem
you will see that this is a very nice
direct translation of that definition nah lets
a.m. look at a brute-force solution that sure church
for all a.m. possible solutions
and to do that we will use another function
that you will have to be fine in the exercises
and ish is a function split and split
take Celeste and readers a pair of lists
inside another lest
and it will if you all the possible ways
did you can split deadliest into a pair of lists
roger is on display at 1234
I get splendid into Wong
234 again split and 1234
ago
split and 123 and for and
notes that we don't take into account the empty list
so splitting 1234 en tu wong
and 1234 doesn't really make sense because then I have not
really split the list I'm just gonna yeah split of the anti list
which is gonna nonsensical okay so again
this is a function that you will have to ride in the exercise
alright
show now began am define a function
that given a list of integers well return
a list expressions whose values that are in that expression are exist
exactly that list of given numbers
so if we're given an empty list of numbers
well then we can build no expression if we are given
a single to left well the only expression we can build
that contains that value is the expression
that on they said Kelly now
if we are given day lest of numbers
how can be built all the expressions well we split the list
and then recursively use the left side
too great an expression the right side too great an expression
and then we're using are combine function
to combine the two right so this is a brute-force
way of enumerating
all possible expressions that are built
out of these numbers okay and the combine function here
just tries to combine these two expressions
using any of the operators and I'm what they can do
as we can right less comprehension that says
if we all the choices for niche an
the input list brute force create all the expressions
and make sure that's the value that i'm looking for
ish the the required value
okay so this
solution here is a more or less
121 translation of the original problem
it's super brute force but it works
okay so it works every run this on
I get I A an very very
am slow laptop an every
look for dissolution storage in a problem it finds the first solution
and under half a second and under a minute
it finds all solutions a show even for dish
very simple abroad for solution
an this is gonna be a fast
an and God takes like an hour about two minutes to find
all the solutions the question is
can we do better and we definitely can
since we are brute forcing all possible
expressions there will be many expressions that are invalid
and that we're gonna have to filter out later show if Megan
make sure that we're not generating any invalid expressions that my
that it's definitely a win am and
just let's do a back-of-the-envelope calculation here
there's possible all expressions that we can build are
33 million and only 5 a million of them
are actually sell it K and then
what we will do is we will combine
the generation function with the evaluation function so we will fuse the
SDO
to make sure that things are rejected
earlier but before we do that this
sequence loss rather long
show let's take a well-deserved break and then see you
in a bit thank you