Functional Programming for the Object Oriented
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 96 | |
| Author | ||
| License | CC Attribution - NonCommercial - ShareAlike 3.0 Unported: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this | |
| Identifiers | 10.5446/51818 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
00:00
Object-oriented programmingFunctional programmingComputer programmingOpen setSoftware developerQuicksortVisualization (computer graphics)Multiplication signSpeech synthesisProcess (computing)Object (grammar)Universe (mathematics)Functional programmingSubsetProgramming languageFunctional programmingMetropolitan area networkSystem callTerm (mathematics)CodeDomain nameXML
02:40
CodeComputer programmingPerformance appraisalFunctional programmingObject-oriented programmingExecution unitAbstractionFunction (mathematics)Data modelMereologyCASE <Informatik>Presentation of a groupInternetworkingProgramming languageComputer programmingCausalityObservational studyExecution unitProcedural programmingFunctional programmingRight angleObject (grammar)Multiplication signMereologyState of matterFunctional programmingFunction (mathematics)Cross section (physics)Basis <Mathematik>Data structureCodePerformance appraisalType theoryDifferent (Kate Ryan album)Programming paradigmObject-oriented programmingView (database)Presentation of a groupNumber1 (number)Form (programming)AbstractionQuicksortCASE <Informatik>NeuroinformatikComputer animation
04:43
Functional programmingFunction (mathematics)Electronic mailing listString (computer science)Element (mathematics)Template (C++)Pattern languageProtein foldingProduct (business)Polymorphism (materials science)EmailDigital filterIterationLevel (video gaming)Reduction of orderStreaming mediaSoftware frameworkWeightOrder (biology)Parameter (computer programming)Element (mathematics)Functional programmingoutputSummierbarkeitPolymorphism (materials science)Type theoryElectronic mailing listProduct (business)Lambda calculusCASE <Informatik>Interior (topology)Operator (mathematics)RecursionMilitary baseString (computer science)Variable (mathematics)Term (mathematics)Different (Kate Ryan album)ImplementationPattern languageProtein foldingResultantInformationElectronic signaturePattern matchingSet (mathematics)Level (video gaming)Streaming mediaPredicate (grammar).NET FrameworkProcess (computing)CuboidBoolean algebraQuicksortPoisson-KlammerInfinityLink (knot theory)Right angleSound effectMatching (graph theory)Point (geometry)Axiom of choiceMultiplicationTraverse (surveying)Programming languageLogicSpring (hydrology)Moment (mathematics)Prisoner's dilemmaForm (programming)Dirac delta functionBit rateHoaxAreaMultiplication signExpressionPhysical systemSystem callMultilaterationMappingConcordance (publishing)WritingInstance (computer science)Similarity (geometry)XMLComputer animation
13:54
Level (video gaming)Reduction of orderIterationStreaming mediaSoftware frameworkWeightDigital filterOrder (biology)Function (mathematics)Performance appraisalData structureoutputElectronic mailing listImplementationElement (mathematics)Fluid staticsAlgorithmMathematicianSieve of EratosthenesPrime idealEquals signNumberPrimality testIntegerLengthFunction (mathematics)Programming languageLine (geometry)Interior (topology)IterationType theoryNumberFunctional programmingSieve of EratosthenesSet (mathematics)Similarity (geometry)Java appletMultiplicationString (computer science)MathematicianAlgorithmDeclarative programmingPrime idealElectronic mailing listExpressionInsertion lossInfinityAbstractionElement (mathematics)QuicksortCASE <Informatik>Operator (mathematics)Binary codeLoop (music)Data structureRun-time systemPattern matchingCartesian coordinate systemDivision (mathematics)Sound effectCircleLetterpress printingFilter <Stochastik>Right angleMultiplication signPoint (geometry)Physical systemOffice suiteObservational studyProcess (computing)Binary treeMatching (graph theory)Sampling (statistics)Computer clusterSystem callPlanningGraph coloringParameter (computer programming)Bit rateKey (cryptography)Field (computer science)Computer-assisted translationNumeral (linguistics)Computer animation
23:02
Sieve of EratosthenesEmpennageElectronic signatureGreedy algorithmStrategy gameFunction (mathematics)Partial derivativeExtension (kinesiology)Personal digital assistantConvex hullImplementationNumberPairwise comparisonDiagonalPattern languageIterationCASE <Informatik>Observational studyProgramming languageComputer chessWhiteboardQuicksortPattern languageEnumerated typeInterior (topology)Pairwise comparisonView (database)Greedy algorithmDiagonalFunctional programmingRow (database)Point (geometry)Position operatorLevel (video gaming)Social classEndliche ModelltheorieSlide ruleElectronic mailing listHeegaard splittingMatrix (mathematics)MereologyArray data structureRight angleExtension (kinesiology)Electronic signatureMultiplication signObject-oriented programmingGreatest elementFigurate numberProcess (computing)Focus (optics)Quantum stateSystem callComputer clusterBit rateInsertion lossGoogolRational numberDivisorDirection (geometry)Different (Kate Ryan album)WritingInternet forumVideo gameXMLComputer animation
31:25
Electronic signatureDiagonalPairwise comparisonIterationPattern languageImplementationRevision controlFunction (mathematics)Element (mathematics)Partial derivativeData typeExtension (kinesiology)Functional programmingOrder (biology)Different (Kate Ryan album)Point (geometry)Direction (geometry)Parameter (computer programming)Multiplication signPosition operatorSatelliteImplementationLevel (video gaming)CASE <Informatik>Musical ensembleIterationOrbitLatent heatCombinational logicEvent horizonMereologyElectronic mailing listExtension (kinesiology)Identity managementPredicate (grammar)Declarative programmingPattern languageLambda calculusField (computer science)Element (mathematics)Operator (mathematics)PredictabilityCartesian coordinate systemSession Initiation ProtocolSign (mathematics)Moment (mathematics)Letterpress printingRight angleQuicksortMathematicsSystem callRow (database)Interior (topology)Boolean algebraPairwise comparisonDiagonalComputer animation
39:24
Extension (kinesiology)Electronic signatureDigital filterPattern languageElectronic mailing listLattice (order)ImplementationRecursionPartial derivativeRevision controlFunction (mathematics)IterationEmpennageType theoryPattern languageElectronic mailing listQuicksortDirection (geometry)Functional programmingPosition operatorMultiplication signCASE <Informatik>Computer programmingParameter (computer programming)Level (video gaming)Goodness of fitRevision controlFactory (trading post)Operator (mathematics)Positional notationAlgorithmSoftware developerSoftware design patternLink (knot theory)MereologyPartial derivativeNumberRow (database)Extension (kinesiology)Interior (topology)System callIterationContent (media)Dependent and independent variablesBit rateMatching (graph theory)Reading (process)2 (number)Number theoryRight angleDesign by contractProgrammer (hardware)Special unitary groupComputer animation
47:23
IterationEmpennageExtension (kinesiology)Duality (mathematics)Normed vector spaceComputer chessWell-formed formulaConstructor (object-oriented programming)MereologyDistribution (mathematics)QuicksortCASE <Informatik>PlanningFunctional programmingTransformation (genetics)NeuroinformatikLevel (video gaming)Point (geometry)Query languageNumberMoment (mathematics)Electronic mailing listMathematical optimizationProcess (computing)Different (Kate Ryan album)ExpressionPattern languageMultiplication signProgramming languageRoutingType theoryRootCodeDomain nameLengthFunctional programmingHand fanParameter (computer programming)1 (number)Core dumpDisk read-and-write headComputer programmingMaxima and minimaSoftware testingMetric systemNetwork topologyTable (information)Workstation <Musikinstrument>Form (programming)BitReading (process)View (database)Self-organization
55:22
Computer animation
Transcript: English(auto-generated)
00:05
All right, I think we're ready to start. So welcome everybody, last session of NDC. Thank you for coming everybody, it's good to see that many of you here actually. So my name is Einstein Kolschud, I work for a company called Klik, and I'm based down in a city called Lund in Sweden, just across the street from Copenhagen.
00:23
And Klik works in the business intelligence industry, so we develop tools for doing data visualizations, and I spend my time being a developer using C sharp as my primary language. I have a background from the functional programming domain though, actually my first job coming out of university was doing full-time
00:42
development in Haskell. How many of you here are familiar or comfortable with using functional languages? For a couple of you, how many of you have never used the functional language? Okay, quite a few of you, excellent. So this speech is basically about what functional program is all about and how it differs
01:02
from object-oriented development, because when I was doing my first job there working with Haskell, I learned the practice of using Haskell as functional language for doing the job. The next job I got was doing development in C++, which obviously is very heavily object-oriented in a very
01:21
different world. I was doing that for quite a while, and then I got the job with Klik, and I got to do C sharp. And I was thrilled, because I realized that a lot of the things that I had learned in Haskell in functional programming, I could reuse in C sharp. So how many of you do development in C sharp? That's a lot of you, excellent. How many of you are familiar
01:43
with LINC and comfortable with that? A lot of you, excellent. So that was what made me happy. And this talk is a little about why that made me happy. So I'm going to just, another thing was that I noticed that when I started developing there, my colleagues would quickly become sort of surprised by the way I wrote my code. I used LINC quite heavily.
02:05
And I was sort of surprised that they were surprised, because this was sort of their language, and I was coming there and doing work inside their domain and starting to learn this, so I just found it natural to use these tools. And after a while, I thought, hey, perhaps I should explain where I'm coming from and why I write my code the way I do.
02:23
So this talk here basically comes out of that. It was an attempt to sort of introduce them to Haskell and functional programming, and hopefully that will give them a more clear understanding or more acceptance to why I develop my code the way I do. So I'm going to start by back up a little and talk a little about what functional
02:44
programming actually is. And if you go to Wikipedia, you will see some definitions like this. So this is for object oriented programming. It's a paradigm based on the concept of objects with the data structures that contain data and code in the form of procedures often known as methods, right? Nothing strange about that. Function programming is
03:03
a paradigm that treats computation as the evaluation of mathematical functions and avoids changing state immutable data. All right, so what does that all mean? Well, I found another talk on the internet at once, which is made by a guy named Daniel Spiewak. Not sure who he is, but I saw this talk and I liked it, so I can
03:21
recommend everybody who's here to see that if you haven't. It's called Living in a Post-Functional World. And he talks a lot about this concept of functional versus object oriented and what would happen in sort of the cross sections between those two worlds if you had a language that were working in between there. And he was very curious to see what those languages would be all about. But he takes a very pragmatic view on all this. He basically says like
03:42
this, object oriented programming, when I do that, I use objects as my primary unit of abstraction. And in functional programming, obviously functions is a primary unit of abstraction. And he goes on to say that in functional programming, functions are the primary tools you reach for when you want to model a problem. So obviously, as
04:05
I all know, functional programming and languages and all this, it doesn't strictly go together. You can do functional programming in any language. You can do object oriented programming in the language. The basis is how you reason about how to solve the problems you're working on.
04:21
So this presentation is split into two parts. First, I'll give a brief introduction to Haskell and talk a little about what that language is. Just syntax and just give you a feel for how it works. And then part two is a small case study where I will show how to solve a non-trivial but quite small problem using
04:40
functional programming. Okay, here we go. Introduction to Haskell. Well, first of all, we have some primitives, of course. Boolean, characters, float, ints, a number of others. What's interesting to note here is that all types are written with a capital letter in Haskell. That will make a difference later on, so I'll get back to that.
05:01
Lists is used a lot. And a list is denoted using square brackets. So what you see here is a list of integers, this list of characters, also a string. A string is just a list of characters. So anything you can do with lists, you can also do with strings. This is a list of lists of integers, so you can use anything in here, right? Functions are written like this.
05:25
So this is the signature for a Boolean function, not, which takes a Boolean as an argument and evaluates to a Boolean as well. This is an operator and it takes two values, two Booleans, and returns a Boolean. Pretty straightforward. This is
05:41
a higher-order function. So map takes a function as an argument and a list of values and applies that function to every value of the list. What's interesting to note here is that these types here are written with a lowercase letter. They're not really types, they're type variables.
06:01
And the effect of this is that you can use this function to any type. So we don't care what the types A and B are, the only thing that is important is that they match up. So this list has to have values of types that match the input value to this function. It's a polymorphic higher-order
06:20
function. All right. So no type parameters here, we're just given these type variables instead. Okay, so let's implement our first function in Haskell. So this is a very simple function for summarizing the values of a list. So a function called SumInts that takes a list of ints as arguments and returns the sum of all of them. In Haskell, you will
06:42
typically do pattern matching for doing these type of definitions. Anybody here who are familiar with pattern matching? Who have not used a functional language? None. Okay. So pattern matching is a way of defining your function in terms of different cases, basically. So I will do
07:01
this recursively. I will split my definition of SumInts into two parts. First, I will pattern match on the case where I have an empty list. So the sum of an empty list is zero, right? No elements, sum is zero. Second case is a list that has at least one element. So this is a list that
07:24
contains an element n in front of SumListns that I don't care about at this point, what it is. And what I will do is take that first element and I will summarize that with what I get when I summarize the rest of the list. Okay?
07:41
I also write the function called concatenate, which takes a list of strings and combines them into one string. And I will do that more or less the same way. Start off with a base case, empty list, concatenation of all the strings of no strings is the empty string.
08:01
And the recursive case, I'll pattern match on the list with at least one element and I will do X, which is the first string I have here, and I will concatenate that, this is the Haskell operator for string concatenation, with what I get when I do concatenation on the rest of the list. Okay. So as you can see, these two definitions are
08:22
very similar to each other. Actually, we can try to enumerate what are the common bases for these two functions. And the first thing you can see is that there is a function that combines two values into one. In the first one we have the add operation, second one
08:41
we have the concatenation operator. Second thing we have is a base case. We have something that we fall back on when we have an empty list. It's zero up here, and it's the empty string down here, right? And finally we have a list of values that we apply this form. So why don't we use this information to try
09:04
to capture the pattern we have been using in these two functions? I will call that fold. It should be a name that is very familiar to those who have seen Haskell before. So I'm going to implement a function that looks like this. It takes a binary function as input,
09:21
which is the function that is used to combine two elements, and it takes a base case as input, and it takes a list of values. So how would I implement this? Well, it's virtually identical to what I've already done. So concatenate takes a function, in this case I don't
09:42
care what it is, I'm pattern matching on the empty list, in that case I don't need a function, but I have the base case, and for the empty list I will simply return that base case. Next case, now I have my function, I need that function because I want to combine that,
10:00
I want to apply that to the first element of the list, which is x, and what I get when I fold the rest of the list. The idea is that this will traverse across the list and fold everything up into one single element, and that will be the final result. Any questions on that? No?
10:21
So now we can use this function instead. For instance, we can use this to define concatenate. So concatenate is just doing fold using the concatenation operator and the empty string as the base case. Or we can define sum and product by using plus, the multiplication, and the base case of our choice, or we can use it on other types
10:42
like Booleans. So these are functions to doing and and or on all the elements of a list. So and here takes the and operation, logical and, and true as the base case, and this will turn true if all the elements of this list are true. So what do we just do here?
11:02
This function fold, it captures one pattern of traversing across a list of values. This is one way we will typically iterate across a set of values to get some job done. This is one of the tools that we will reach for
11:20
when we process data in Haskell. And in Haskell there are a lot of these functions. Fold is one example. Here is a list of some of those common functions that are provided out of the box with Haskell. So at the top here we have map, which we have already seen. Takes a function, applies it to a list. We have concatMap, which is virtually the same.
11:41
It's just function returns a list. We will just apply that to everything and concatenate everything at the end. We have things like filter, takes a predicate or a function that returns a Boolean, and takes out those members of a list that satisfies that predicate. We have takeWhile, which will take elements as long as a predicate is true.
12:01
All and any takes a predicate and returns true if everything in that list satisfies a predicate or if at least one of them. sipWith takes a binary argument, a binary function, and two lists, and then applies these functions to pairwise on the different elements of the list.
12:20
We have iterate. This is sort of an interesting function. It takes a function as an argument and a seed or a start value, and what it produces is a list where the first element is this value, next element is this value with this function applied once, value after that is this value
12:41
with the function applied twice, and so on. What's interesting about this is that this is an infinite list. It doesn't stop. In Haskell, you can work with infinite lists like this. I'll come back to this function quite a lot later on. And we have folds. If you have a sharp eye, so you can see that it's a little different signature, actually, than what I wrote,
13:01
and if you think about it a little more, that can be a homework exercise. You can actually generalize that a little. But this is the way to fold. You can actually fold in two different ways, basically from the left or from the right in the list. So this is actually a very, very powerful tool, and this is what we have been seeing being lifted into other languages.
13:20
So C-Sharp introduced the link in the .NET framework back in 2007, from what I understand. In Java, they introduced a concept called stream back in 2014, if I'm right, so it's a little later. And actually, one of the things that is required for this to be efficient is the notion of a lambda expression, because if you don't have lambda expressions,
13:40
it's very hard to use this in a satisfying way. And that was introduced quite late in Java, for some reason. But in C-Sharp, you will have functions for most of these. So map is called select, concatMap, selectMany, you have filter, takeWhile, all, any, zip, zipWith, aggregate is the name for this fold operation, and you have similar functions in Java.
14:05
Iterate doesn't exist in C-Sharp, but I'll show you quite soon how to define that. Java has most of it, it also has its iterate function. All right. So let's look at list one. So one of the things that was interesting about this is that it's infinite.
14:20
The list it produces doesn't stop. So if I apply this function, which is basically plus one, and I start off with zero, well, then I'm going to get all the integers. Zero, one, two, three, et cetera. That is okay, as long as I don't consume all the elements in that list. If I just take the first 10 of this,
14:41
first seven here, I will get this list here. That's fine, because it won't compute what comes after that if I don't actually need them. But if I try to compute the length of that list, then I'll be in trouble. Or if I try to take the loss value, that wouldn't work. We need to be a little careful, but it's actually pretty useful because it abstracts away some of those behaviors
15:00
that I often don't need. So in Haskell, there's a syntactic circle for this, so you can basically just write like this, zero dot dot. This will produce a list that starts off with zero and just counts. So I give you one example how to use this, the fact that it's infinite.
15:20
So this is, I want to create a numbered list based on a list of strings. So in this example, I have a list containing four strings. This is my list. And I want to produce the output you see here. So I just want to append a number to each line. So how would I define this? Well, I'll start with a small helper function,
15:43
print entry, which just creates a string that matches one of these lines. It will take an int as argument, which is the line number, and the string I want to append this line to, this number to. And I will define like this. So it takes an n and a string,
16:00
and I turn the number into a string using show, which is a function in Haskell, concatenate with that with the colon and the string. So now I want to produce that output. And the way I do that is using, I want to have a string, a function with this declaration
16:20
so it takes a list of strings and produce this final string. And I can do that with this expression. So here I take my strings, and I use this infinite list here, and I merge them together using this zip with operation that takes a binary operator as argument,
16:41
binary function, which is the one I just wrote here. It takes ints from this and strings from this one and combines them and builds the lines. And it's okay to do this, even though this one is infinite because when it gets to the end of the shortest one, it will stop. So now I can do that,
17:00
and I can just use this function unlines, which is a sort of a community function in Haskell that takes a list of strings and just concatenates them together and depends on a new line at the end of each string. So that's it. So that's one example of how to use that infinite data structure or concept.
17:23
So in C-Sharp, they introduced something called deferred execution, which is actually a pretty interesting concept. I haven't seen that in the same way in any other languages. I don't know how Java does that, but I was also sort of surprised when I come to C-Sharp and saw this one. So it's been available quite a while, and what they did was they introduced
17:40
a keyword called yield that allows a caller to request values from a function, and when the runtime system gets to this yield operation, it will return that value and stop until you request the next value, then it will continue and produce the next one. And this allows you to actually produce
18:01
infinite data structures in C-Sharp as well. So this is one way of implementing iterate in C-Sharp. So I will use the IEnumerable clause, which is the one used to model this behavior there. It takes a type parameter, t, and I will use iterate, which takes a function from t to t,
18:22
and a seed, the starting value, and what I do is I will just, while true, loop forever. I will yield return this one. So that's the value I had, and once I've done that, I will just assign to x application or the function to it and continue.
18:41
So this will have the effect that if I just ask for the first value of this list, then the runtime system will run here, down to this point, return it. It will stop. If I ask for the next one, then it will take the next loop until it gets the yield return again. It's actually a sort of fascinating construct, but this will produce the same effect.
19:00
You can reason about this IEnumerable being returned here as being an infinite structure. So, let me show you another example how to use this. So this is, anybody familiar with the Sieve of Eratosthenes? None of you? Oh, a couple of you, all right. So it's an ancient algorithm finding primes.
19:21
Eratosthenes was a mathematician, a Greek mathematician and philosopher, living in Cyrene, which is now in modern day Libya, but he produced an algorithm for finding all primes. And it basically works like this. So we start off with a set of all integers greater than or equal to two. So that's two, three, four, et cetera.
19:42
The first number in that set is a prime. Two is a prime, right? Next step we do is that from the set of integers we have, we remove all those numbers that are a multiple of the prime you had from the previous step. So we remove all multiples of two. So remove two, of course, remove four, six, all even numbers.
20:04
Then we go to step two. And the first element in that set now is three. It's also a prime. We take that, we remove all the elements that are divisible by three. So six is already gone because that's divisible by two.
20:20
But we remove nine, we remove 15, et cetera. And then we loop again. Next one is five, that's also a prime, and so on. All right. So let's implement this. So in Haskell, we would do something like this. So primes is now an infinite list of integers. And I will start off by giving it this seed,
20:41
which is basically the first step. Start off with all integers greater than or equal to two. I can do that like this. So I feed this set into a function called sieve, and that I can implement like this. And I explain what this means now. So first of all, a pattern match here on an un-empty list.
21:00
I know that this case, that the first element's always a prime, so I want to return that. So I return that here. I'm going to return a list where this is the first element on the list, and then the rest is what I get when I do this filtering. And what is the filtering I do? Well, here I do a filter, so I remove all the elements
21:22
from a set of values that are multiples of p, basically. The reminder of n divided by p is different from zero. Those are not multiples, for those I keep. Everything else, I remove. And then I recursively pass that on. Notice also that this has no terminating recursive case.
21:43
It will produce an infinite list. So we can just keep going. Any questions on that? No? So let's look at this in C sharp. Well, we can do something that is very, very similar.
22:01
We already implemented the iterate function, so I'm not going to go through that again. Well, we can define a function called primes, which returns an i enumerable wins. And I start off with the seed value, so I just produce this infinite list of values, starting from two, iterate, and I provide the function that increments one, m plus one, starting with two.
22:22
And then the actual sieve can be implemented like this. So I want to take the first value and yield return it, so that I return that one, and then I just keep going. So I reset the ints that I got here with what I get when I do this filtering,
22:42
which is the same expression written in C sharp that I have here in Haskell. There you have an infinite list of primes in C sharp. It's not a very inefficient algorithm, but it's possible and it's nice, and I kind of like the historical aspect of all that. Any questions?
23:01
Okay. So that was the introduction to Haskell. I'm going now to the case study. So the case that I'm going to use is the eight queens problem. How many here are familiar with that problem? A couple of you, okay. How many have solved that problem? One. What language did you use? Java, okay.
23:22
Could be interesting to hear your comments on this solution instead. So the eight queens problem is this. So you have a chess board, and you want to place eight queens on that chess board so that no two of those queens threaten each other. It's actually pretty hard. So if you want to go home afterwards and try that, figure it out. There's not that many solutions for that.
23:43
And the reason why I chose this problem when I was going to explain Haskell was that when I was doing that job where I was doing C++ development, one of my colleagues was curious on functional programming, so he wanted to try out Haskell a little, and he chose this problem. He wanted to start getting his hands dirty writing, solving this problem in Haskell.
24:02
And if you approach this from an object-oriented point of view, you will quite quickly, or it's very likely that you start thinking about, okay, how would I model this chess board? What classes would I need for that? And that was exactly what he did. First thing he started thinking about, how do I model efficiently a eight by eight grid,
24:21
a matrix representing the chess board? And we were starting to talk about arrays. How do you model arrays in Haskell, and how would you use them, that? And I was like, this doesn't feel right. I think you're moving in the right direction, but I couldn't really put my finger on what it was. And when the day was over, I went home
24:41
and I was thinking about this and said, I probably wouldn't have done that like that at all. So I wrote a solution that is more or less what I'm going to show you here now. And it was so obvious to me that we were thinking about this problem in very different ways. So this is the way I would solve it in a functional language. It's very interesting to hear how you solve it in Java,
25:01
if you have time to explain that later. So, first thing I was thinking about was what should a solution look like? And as I already said, the first thing we were thinking from the C++ point of view was like a two-dimensional array, a chess board, right? It's a two-dimensional array, eight by eight.
25:20
How hard can it be? But actually, there are some things you can see, and you can immediately realize about that solution. One thing is that there will never be two queens in the same column, right? So I was thinking, why don't we just accept that and say that a solution will just be the list
25:40
of row positions for each queen? So I would say that the solution for this, this is a real solution, is just this list of values here where we have a queen at position three, one, six, two, four, seven, four, no, that's two, four, and zero, right?
26:00
That's the solution. So the positions of the list represents the position of a queen in that given row. Next thing is, how should we implement this? Well, I will do a greedy algorithm. So basically, I will create all solutions and take the first one. My starting position would be the empty solution.
26:21
So I will start off in a case where I have added no queens to the chess board, and then I will gradually extend that until I get to a point where I have a solution with eight queens. Then I'm done, I have a solution. So what functions will I need to solve this problem? Well, I will need a way to take a partial solution
26:41
and extend that with a new queen. So how would that look? Well, this is a partial solution from the solution you saw earlier. So we have three queens positioned here, seven, four, zero, and we want to find all those solutions that are possible extensions to that.
27:01
So the way I will do this, I will just try all of them. I'll produce those eight queen positions that I can have in this next column, and then I will see which one I can use. So I start off from the bottom. Is it okay to add a queen to row zero? Then I will check, well, it doesn't hit anything here. It's okay to add up, but it hits this one.
27:22
So it's not okay to add level. So I remove that. Next one, is it okay to add at row one? Well, it's okay to add up, it's okay to add level, and it's okay to add down. Fine, I'll keep that one. Now I'll continue like this. So I'll get this one, no, it hits that queen.
27:41
This one hits the one down in the corner, and when I keep doing this, I end up with just these two solutions. So there are just two extensions to this initial partial solutions. So the extensions for seven, four, zero is one, seven, four, zero, and five, seven, four, zero.
28:01
Any questions? Okay, so let's look at this okay to add function. It's going to have this signature. It takes a row position for a queen that I'm attempting to add, and a partial solution. So it's an int, and a list of ints.
28:21
And it will have this behavior. So okay to add zero will not be, will be false, because that will collide with this one. Okay to add one will be true, as we saw in the previous slide. And what we can also see is we can split this into three different sub-problems. So imagine that we have these three functions.
28:41
Which is basically what we already tried to see. Is it hitting anything here? Is it hitting anything here? Is it hitting anything here? So you have okay to add up, okay to add down, and okay to add level, which will have the same signature. Takes a queen position, and just focusing on that single problem. Will it hit any queen in this direction? And if you have these three functions,
29:02
then we can express our okay to add like this. So you're basically going to divide and conquer, split it into three parts. So it's okay to add a queen at a certain position. If it's okay to add up, it's okay to add down, and it's okay to add level. All right.
29:20
So let's focus on okay to add up. So how would we implement this? Well, the way I would do is, is that I will start by finding that diagonal, starting from the position that the queen has right now. So here I'm trying to check if it's okay to add a queen to position one, or to row one in that column.
29:43
So I'll start by finding this diagonal by moving one step up. So I'm adding one, will give me a list with the value two. Then I will add one again, which will give me a list two, three. And I will add one again, two, three, four, and so on. Now I'm done, I've reached the end of the chessboard.
30:02
So I know I won't hit anything more. Because now that I have that diagonal, what I need to do is simply do a pairwise comparison of that diagonal with the potshot solution I already have. So now I've reduced this to a case
30:20
where I can simply do a comparison between two, three, four, and seven, four, zero, and pairwise comparing these positions here. So if this one is different from this, then it's okay in that column. If this one is different from this, it's okay in that column. And if this one is different from that, then so can the last column as well, and I'm done.
30:44
So let's look at those tools that we use for this. Well, implementing that diagonal is basically iterate. I'm adding one all the time. So I'm moving up across the chessboard with the function plus one. So I will use this function, suck, which is successor,
31:04
short for successor. It's basically a fancy name for plus one in this case, but you can use it in enumeration type in Haskell. So if I do iterate successor on one, I will get this value here. One, two, three, four, five, six, seven, et cetera. Next function I will use is pairwise comparison.
31:23
What pattern is that? What function? Any suggestions? A zipwith. Zipwith takes a binary function and applies it pairwise on the elements taken from two lists. So if I do zipwith and this differs from operator,
31:45
and I use this value here, two, three, four, five, six, and et cetera, I don't care how long it is, with seven, four, zero, which happens to be my partial solution, I will get true, true, true, which is what I'm looking for.
32:01
So if I use these two patterns, I can write my okay to add up like this. Okay to add up is basically a zipwith with the difference from operator on what I get when I produce the diagonal. Iterate successor on the queen position I'm starting from.
32:21
Notice I didn't use tail here. Tail drops the first element of a list because I don't want the one that I got here. That's the position I started from. I know that there's no queen in my column I'm inserting in. And this produces basically a Boolean list and I want to check that all of them are true, which is and. And takes a list of Booleans
32:41
and turns true if all those elements are true. This dollar sign here is, well it's actually a function application. It's a function that takes a function and argument and applies that function to the argument. It's sort of a weird function, but it's mostly used for avoiding a lot of parenthesis. It's a very low precedent, so that means that this here
33:01
is applied to whatever comes after it. All of us have had parenthesis everywhere. It's quite common to use that in Haskell, just like this. All right. So now that's okay to add up. Let's continue to okay to add down.
33:20
So what would that look like? Any suggestions? Well, it's almost identical, right? The only difference is I'm using another function here. So here I'm counting up. Here I'm counting down.
33:41
So the only difference between these two implementations is a function. And of course, when you have two identical implementation that just differ in some single point, you will create a function that does that. Let's create a higher order function that takes this math function here that indicates how to traverse the chessboard as an argument.
34:01
Now we'll call that okay to add given direction. So it takes a queen position, a row that I'm trying to add a queen to, and a portrait solution, and then it takes this function here that indicates how to traverse the chessboard and returns true, or it returns bool. Implementation will be almost identical
34:20
to what we've already seen. Only difference is that we have this f here, which is the function I use, and I use that when I do the iteration. Because if I have this function, then I can write my two okay to add up and okay to add down like this. So I take okay to add given direction q, qs,
34:41
and the successor function, and the predecessor function. And I can also write okay to add level using this higher order method. And what will the function be here? Yes, the identity function. The identity function is,
35:01
first time you see it, that's sort of a weird function. It's a function that doesn't do anything. It just takes an argument and returns that. But when you start working with higher order functions, it often becomes very, very useful. It's like adding with zero, you never do that. You can easily have a function that returns zero, right?
35:23
So now we can return to our okay to add method. So this function was basically a combination of these three okay to add up, down, and level. We now no longer need those specific implementations for different directions. We can have one single function to do that. So we can write it like this instead.
35:45
Now, however, we can see that this function is actually using another pattern that is already available. So what we are doing here is we take an okay to add given direction, and the queen, and the portrait solution, and applying it to three different values. Successor, predecessor, and ID.
36:04
We're just doing add on them. So what if we just extract those function to a list? You can do that, that's okay. So we have a list containing three functions, successor, the predecessor, and the identity function. Because if we have that, what we need to do
36:22
is to check if all elements of this list satisfies the predicate that is okay to add this queen to this portrait solutions given that direction. So now we can use this pattern here, all. All takes a predicate and returns true
36:42
if all the values of a list satisfies that predicate. So if I do all even on two, four, six, I get true. And if I use that, I can write okay to add like this. So my predicate is okay to add given direction,
37:00
and the queen, and the portrait solution, notice that the last argument is missing, which is the one I'll be feeding to this predicate from this list. And I just want to check that all of these elements here satisfies this predicate.
37:22
So here I use something that I very much miss in C sharp, which is partial application. It's a very nice concept in Haskell that basically in Haskell you can look at any function like as if it's taking only one argument. And if you have a function that takes two arguments, what you get when you supply the first argument
37:40
is the function that takes the next argument. It's called currying. It's very useful, especially for cases like this. So it allows me to not have to write lambda expressions all over the place. I can just feed it those arguments that I have at the moment, and I can apply that. So now we have come this far. We have two functions.
38:00
We have okay to add and okay to add given direction. So let's continue and see what the next step would be. Well, let's go back to this extend solution, which is actually what we want to do. So we want to write a function that takes a partial solution and produces all the possible extensions
38:22
to that partial solution. So it will have this declaration, list of ints, and returns a list of lists of ints. And the steps for doing this is basically that we would create all those eight possible queen positions for the new column, zero through seven.
38:41
We want to take only those queens that are okay to add. Here we see where we're going to use that predicate we just wrote. And then finally we want to create extensions based on those queens that are okay to add. So for each of those queens, we want to create a new partial solution. So what patterns will we use here?
39:00
Well, creating all eight possible queen positions is very easy, zero dot dot seven. That gives us that list in Haskell. Take only the queens that are okay to add. What pattern is that? Any suggestions? Filter. Someone said filter.
39:21
Excellent. Filter. Filter takes a predicate and returns only those values from a list that satisfies that predicate. So filter even on zero dot dot seven will be zero, two, four, six. And finally we want to create extensions based on those queens that are okay to add. And that is actually map.
39:42
Because what we want to do is we want to use filter to get that list of positions that are okay to add. And for each one of those lists, we want to append that value to the original partial solution. In this case here I show map takes a list one, two, three and produces two, four, six by applying the times two operational algorithm.
40:03
So using these patterns, I can write that extend solutions like this. So reading from the right, here I produce those eight values, zero through seven. Then I filter using okay to add with the partial solution I have. So this back take thing here
40:22
is a convenient way of producing something that is, taking a function, making an infix function basically. So this means that I'm supplying this as a second argument to okay to add. It's also a nice syntactic thing in Haskell. But this basically gives me a list where I only have those numbers that are okay to add given this partial solution.
40:43
The next step is I take the map on that. So for each of those queens that are okay to add, I produce a new list where I append that queen position to the partial solution I started with. Then I have all those extensions.
41:02
So now I want to use this function to produce all solutions. So step one here would be that we will apply extend solutions to an empty list. Doing that will produce the list that you see here. So these are all the possible solutions
41:21
to the queens problem that have exactly one queen placed in the first row. Of course it can be in any row. First column, it can be in any row, right? Zero, one, two, three, et cetera. Next step would be to, for each of those partial solutions, I want to extend them. So I want to apply extend solutions to the list where I have a queen in position zero.
41:44
That will produce this list. So two is the first position I can add something here. Zero won't match, one won't match, but two is okay, and up. I will do this for each of those partial solutions that I've already produced. And then when I've done that,
42:02
I just want to join all of those partial solutions to one big list because that will be the list containing all partial solutions that have queens in the first two rows. And then I will go back and continue. And I will do this until I have eight queens placed.
42:22
Then I have my solution, right? So now I'm going to write this function, allSolutions, which takes an int, which is the number of queens I want to place, and it produces all those solutions for that many queens.
42:45
And I'll start with the base case. We'll do a recursive version here. So allSolutions zero, that's easy. There's only one way to place no queens on a chessboard, and that is to not place anyone, so that's an empty solution. And then the recursive case,
43:00
what I want to do is that I want to create all solutions with n minus one queens, and then I want to extend all of them. So create all solutions with n minus one queens. Well, that's a recursive call. And to extend all solutions is this map. So a map extends solutions to all of those partial solutions I got from the previous step.
43:21
And then finally, I want to concatenate all of those lists of partial solutions into one big list. Or I can use concatMap, which is a short for doing concat and map after each other. This takes a function that produces a list and concatenates results into one.
43:42
So then the full version will look like this. allSolutions takes this int and produces a set of partial solutions. But actually what I'm doing here is I'm applying the same function over and over again. I'm doing concatMap, extendSolutions. I'm going to do that eight times
44:01
until I reach the position where I have all my queens. I'm going to take a value there. So what pattern is it where you apply a function over and over again? That's iterate. Iterate takes a function and a seed and produces an infinite list
44:20
where I apply that function over and over again. And in this case, what I can do is I can iterate on the function concatMap, extendSolutions. Which is this first part here. And the seed will be my base case, which is basically a list of one partial solution,
44:41
which is the empty partial solution. And now I want to get the nth value. Well, I can just use this operator. This takes the nth value from a list. So this is the same. This is functionally the exact same thing
45:00
as what I had over here. It's just that I've reused that pattern that is already there for doing this type of iteration. Okay, so now we just need to wrap this up. So we have a function that returns all solutions for n queens. Now what we want to do is we want to generate
45:20
all solutions for eight queens and then take the first. And that's simply this. So you provide eight as an argument and then we take the first value we get. And then we have a solution. And we're done. And the full program looks like this.
45:42
How many are surprised at how short that is? Good. Excellent. So one question I got once when I gave this talk was, is it important that it is short? And I was sort of taken aback because, hey, isn't it cool that it's short? But I was thinking about that
46:01
quite a lot afterwards and actually, I think a better question is why is it short? And the reason why this is short, the way I see it, is that I have been reusing those functional patterns that have already been predefined. And I'm using them quite heavily here in many different directions. And the reason why I would go for a solution like this
46:23
is because I am very, very familiar with all these functions, iterate, zipwith, and, all, map, filter. All of this is sort of part of my vocabulary when I think about functions. And it's there because I have experience doing development in Haskell. And this is what I picked up when I started doing development in C sharp.
46:42
Link is there. Link gives more or less exactly this type of possibilities. And I would use that and it would be very natural for me to do select, to do where, use all of these functions that are already there in link, to perform this type of operations. But one thing that is a little problematic is that if I write a solution to this, like this,
47:03
to someone who is not familiar with that type of operations, this will be quite hard to read. And that can actually be a problem. But I look at this a little like this, that this is similar to what you talk about like design patterns in the object-oriented world. If I say that I'm going to implement a factory pattern,
47:22
I'm sure almost everybody in this room will know what I'm talking about. Or a visitor pattern. Probably you'll know what that is. This is similar. These are sort of small functional patterns that is used heavily in the functional domain. It's very useful to learn these and become familiar with it because this can be a part of your vocabulary, something you can use to solve problems.
47:42
For some problems, it's very, very efficient. You can get very small chunks of code that does the job for you. Any questions on this? Yes? How does it perform? Well, that's the next question.
48:00
So I'm very much a fan of the, there's a quote, I don't remember who said it, but premature optimization is the root of all evil, right? Yeah. If I were to do something very efficient for this, I probably, I'm not sure if I would do this, I might have done it this way and then started analyzing, is this really the way to do it, to get the best performance?
48:21
But in my experience, it's very, very rare that I actually have performance issues. And if I do, it's usually a very small part of the work I'm doing. When I was developing in C++, I was working at a company doing optimizations for distribution of personnel on plane routes. It was a very, very computationally heavy,
48:43
doing that optimization problem, but in my daily work, I almost never saw that part. There was a core of the program doing that very critical part that was doing the optimization work, but most of my daily work was doing sort of data transformations and working with the problem
49:01
to build whatever I gave to the optimization engine. So even there, it was very rare that performance was really an issue. If it were an issue, and I knew that I'm going to solve the eight queries problem for not an eight-by-eight chess board, but a thousand-by-thousand chess board, am I going to do it over and over again,
49:21
thousands of times a second, then I probably would have gone a different route, right? But that's rarely the case. Any other questions? Yes? No, it doesn't. So actually, I can give a little demo, if you like.
49:41
So here's the solution written in Emacs. Actually, I've done a little difference. There's a little difference in the solution here compared to what I showed you earlier. So instead of giving an argument here to this one, I'm just extracting number eight from here. So this will now produce an infinite list of all the parts and solutions for or, number, or queens.
50:03
So if I bring up this, let's see here, and I can just run solution, I will get solution there. So this is the one I showed you earlier.
50:21
And what happens now is it will start computing, and for every step it will be doing this lazily, and as I asked it to get the head here, at the moment it reaches a case where it actually has a solution, then it will stop. It won't produce everything else. So no, it will stop at the first possible moment in this case.
50:42
Everything else will be a long chain of sort of computational expressions available there for it to do, but it will never do it because it won't reach it. And I can now do things like, I can ask how many solutions are there.
51:07
So there are 92 different ways of placing eight queens on a chessboard. Quite a lot of number. And actually, it's very symmetric, right? The chessboard is very symmetric, so you can just start filtering down to find the ones that are really unique.
51:21
Could be a very interesting exercise. Or I can do something like this. So I can say, map length. No, sorry. So what I did now was that map the length.
51:40
So how many portrait solutions are there for the different number of queens added to the table? And as you can see, it rises suddenly one, which is just the empty solution. It quickly rises up to this point here and then goes down again. And this is how many possible ways you can add nine queens to the chessboard. Of course, there's zero. And I can do things like this.
52:00
So if I want to see what numbers there are, I can do like this. This will give me now the column. So you can see it rises to get to the point where it's five and then starts going down again. You can see these type of numbers here. Anyone who is mathematically savvy here might produce a formula for that, I don't know.
52:24
All right, any other questions? Well, I will say that, go back to the performance issue. If that was a problem, I would start digging into it and see what were the bottlenecks.
52:48
It very much depends on what you do with it, right? But if you had something that was very, again, if it is important that it's lightweight and fast,
53:02
then you might want to think about that from the beginning and find those parts that are important to optimize. But in my experience, it's not very often that that's the case. So this is a way to quickly get solutions for the problems. Not necessarily most optimal, but it's a solution. And that's usually what I need.
53:24
Yes? Yes, I have some other Haskellers.
53:45
Would you have written it like this? Yeah, somewhat like this. Yeah? Yes, so I think this is quite idiomatic Haskell, actually. You might have used some other constructs on BOTCH, some list comprehensions and things like that. I might be incorrect. Okay, yeah.
54:03
Any other questions? Okay, that's all I had. What I hope you will take away from this is that not necessarily that Haskell is the best language in the world, because everyone knows it is, right? Yes.
54:20
No, it's the fact that this experience that I had working with a functional programming gave me a different way of looking at a problem. And it's available, that type of work process is available now in most of those modern language, like C Sharp, like Java, and other languages as well. And it's a very useful tool. And getting familiar with those
54:40
and getting comfortable with using those functions can be a very valuable thing to learn. So your old used link, I hope you go home and look at it with new eyes and think about, hey, this is actually something that is more than just a useful tool. It's actually something that might enable me, if I want to, to solve my problems and approach them in a different way. Okay, thank you very much.