Two simple tasks on Haskell (for beginners)
Greetings to all users of Habrahabr!
I recently began to learn Haskell, and, having mastered it a little, I decided to share a little accumulated experience. Of course, Haskell’s knowledge is not at the same level as that of Darkus , so the two tasks described below are more focused on beginners, but experienced users will probably fix it and tell you how to do it better. This is not only my first article on Habrahabr, but in general my first tutorial that I have ever written.
In a city consisting of n districts, it is necessary to create customs points. But you need to put them in the busiest areas of the city. A loaded area is considered to be an area through which one must pass if one goes from part of city A to part B, that is, if there is no detour. If we imagine the city as a graph, and the districts as nodes, then we will search for all “bottlenecks” (= bottlenecks or also called “needle eye”) for a specific path. The following declarations are given:
In the end, the function should turn out:
')
Those. passing this CityMap function and two districts (beginning and end), we will get an array of all nodes through which we definitely need to go if we want to get from one point to another.
To begin, give an example. Suppose we have the next city
city ​​= CM (6, [(2,3), (1,2), (3,1), (4,3), (4,6), (5,6), (5,3)])
then the function call
To begin with, we write a function that returns all the neighbors of a particular node.
Since each element of the Route consists of only two elements, it is possible to simply check whether one of the elements of the pair (p, q) is the desired (b) element. If b is equal to p, then we add q and vice versa. You can use the mapMaybe function to do this.
Testing:
Works! Now, when you can find the neighbors of any node, it would be good to find a path between any two points. Or rather not just a path, but all possible paths:
We must not forget at every step of the algorithm to memorize the node that we have already visited (otherwise we will walk endlessly in circles). Algorithm for finding ways from start to goal:
1. if start == goal, then return [[start]]
2. if start is NOT present in the array of visited nodes (= visited), then for each element of the neighbors (= next) we look for a path from this neighbor to the goal.
3. otherwise return [] (i.e. if we have already visited start)
The problem is that our paths function does not “save” at each step an array of visited nodes. This can be done using the paths' sub-function:
Testing:
Having all the possible paths from A to B, it is quite easy to find a bottleneck - this is the node that is used in all the paths. It should be noted that nodes A and B will also be present in all paths, so they should be immediately excluded from the possible set of solutions:
In order to find the number that is used in all paths, we will use the intersect function, which returns only those elements that are found in both sets. Those. it is necessary to apply this function to the set of all possible solutions and the first element of the paths set, then apply the answer to the second element, etc. The answer can be written as follows:
Then, the function bottlenecks can be written in one line:
Remember to import the Data.Maybe (for mapMaybe) and Data.List (for intersect) modules.
Consider a very similar problem, namely the problem of the Erds Number . Briefly explain what it is: all those who wrote a scientific article with mathematician Paul Erdös receive the number 1, all those who have written a scientific article with co-authors Paul Erdos (but not with him) get the number 2, etc. That is, co-authors of people with Erd s number equal to n have Erdos number n + 1. The task is to find this number for a specific person (if the connection between this person and Erdös cannot be found, we display the number -1). So, to begin with, we will define the types of data with which we will work - these are scientists (the scientist consists of an initial and a surname), they are also authors, as well as a database each item that contains the name of the article (scientific work) and the names of the authors who published . We will also declare a database that we will use for tests:
As in the previous problem, we start by writing a function that defines all the neighbors (that is, those who are in direct connection with this author):
Unlike the previous task, each element of the database, we may contain more than two elements of type Author, so the function mapMaybe can not do. For each element of the database ([Author], PaperTitle) we will check whether the author whose neighbors we are trying to find is in the [Author] array, if so, take the entire [Author] array, if not, go to the next element Database. In the end, it will be necessary to remove the name of the author of which we were looking for from the resulting list (we are looking for its neighbors, therefore, we need nothing):
Do not forget to declare how we will compare our scientists:
Now we will look for all possible paths from the author of "start" to the scientist (Sc 'P' "Erdos"). The paths function is almost the same as the one we have already written:
Having an array of all possible paths from the author to Erdos, you can convert each of the paths into its length using the length function (that is, we obtain an array that contains the lengths of each path). From the resulting array, select the minimum number (= shortest path) and subtract one from this number, since Erdos himself has the number 0. We will not forget to check before that if there is any way at all that leads to Erdos (if not, then return -1):
Successes in programming!
I recently began to learn Haskell, and, having mastered it a little, I decided to share a little accumulated experience. Of course, Haskell’s knowledge is not at the same level as that of Darkus , so the two tasks described below are more focused on beginners, but experienced users will probably fix it and tell you how to do it better. This is not only my first article on Habrahabr, but in general my first tutorial that I have ever written.
Task 1
In a city consisting of n districts, it is necessary to create customs points. But you need to put them in the busiest areas of the city. A loaded area is considered to be an area through which one must pass if one goes from part of city A to part B, that is, if there is no detour. If we imagine the city as a graph, and the districts as nodes, then we will search for all “bottlenecks” (= bottlenecks or also called “needle eye”) for a specific path. The following declarations are given:
type District = Integer type NumOfDistricts = Integer type Route = (District, District) newtype CityMap = CM (NumOfDistricts, [Route]) -- : type Path = [District] type Bottleneck = District In the end, the function should turn out:
')
bottlenecks :: CityMap -> District -> District -> [Bottleneck] Those. passing this CityMap function and two districts (beginning and end), we will get an array of all nodes through which we definitely need to go if we want to get from one point to another.
To begin, give an example. Suppose we have the next city
city ​​= CM (6, [(2,3), (1,2), (3,1), (4,3), (4,6), (5,6), (5,3)])
then the function call
bottlenecks city 1 6 should return node number 3 (an array consisting of one node).To begin with, we write a function that returns all the neighbors of a particular node.
neighbours :: CityMap -> District -> [District] Since each element of the Route consists of only two elements, it is possible to simply check whether one of the elements of the pair (p, q) is the desired (b) element. If b is equal to p, then we add q and vice versa. You can use the mapMaybe function to do this.
neighbours (CM (_,rs)) b = mapMaybe neighbour rs where neighbour (p,q) | b == p = Just q | b == q = Just p | otherwise = Nothing Testing:
*Main Data.List> neighbours city 3[2,1,4,5]Works! Now, when you can find the neighbors of any node, it would be good to find a path between any two points. Or rather not just a path, but all possible paths:
paths :: CityMap -> District -> District -> [Path] We must not forget at every step of the algorithm to memorize the node that we have already visited (otherwise we will walk endlessly in circles). Algorithm for finding ways from start to goal:
1. if start == goal, then return [[start]]
2. if start is NOT present in the array of visited nodes (= visited), then for each element of the neighbors (= next) we look for a path from this neighbor to the goal.
3. otherwise return [] (i.e. if we have already visited start)
The problem is that our paths function does not “save” at each step an array of visited nodes. This can be done using the paths' sub-function:
paths :: CityMap -> District-> District -> [Path] paths cm start goal = paths' [] cm start goal where paths' visited cm start goal | start == goal = [[start]] | start `notElem` visited = [start:rest | next <- neighbours cm start, rest <- paths' (start:visited) cm next goal] | otherwise = [] Testing:
*Main Data.List> paths city 1 2[[1,2],[1,3,2]]Having all the possible paths from A to B, it is quite easy to find a bottleneck - this is the node that is used in all the paths. It should be noted that nodes A and B will also be present in all paths, so they should be immediately excluded from the possible set of solutions:
[1..n] \\ [start, goal] -- n - In order to find the number that is used in all paths, we will use the intersect function, which returns only those elements that are found in both sets. Those. it is necessary to apply this function to the set of all possible solutions and the first element of the paths set, then apply the answer to the second element, etc. The answer can be written as follows:
((((([1..n] \\ [start, goal]) intersect paths[0]) intersect paths[1]) intersect paths[2]) intersect...)Then, the function bottlenecks can be written in one line:
bottlenecks :: CityMap -> District -> District -> [Bottleneck] bottlenecks cm@(CM (n,_)) start goal = foldl intersect ([1..n] \\ [start, goal]) $ (paths cm start goal) Remember to import the Data.Maybe (for mapMaybe) and Data.List (for intersect) modules.
Task 2
Consider a very similar problem, namely the problem of the Erds Number . Briefly explain what it is: all those who wrote a scientific article with mathematician Paul Erdös receive the number 1, all those who have written a scientific article with co-authors Paul Erdos (but not with him) get the number 2, etc. That is, co-authors of people with Erd s number equal to n have Erdos number n + 1. The task is to find this number for a specific person (if the connection between this person and Erdös cannot be found, we display the number -1). So, to begin with, we will define the types of data with which we will work - these are scientists (the scientist consists of an initial and a surname), they are also authors, as well as a database each item that contains the name of the article (scientific work) and the names of the authors who published . We will also declare a database that we will use for tests:
type ErdosNumber = Int data Scientist = Sc Initial SurName type Initial = Char type SurName = String type Author = Scientist newtype Database = Db [([Author],PaperTitle)] type PaperTitle = String type Path = [Author] db = Db [([Sc 'M' "Smith",Sc 'G' "Martin",Sc 'P' "Erdos"],"Newtonian Forms of Prime Factors"), ([Sc 'P' "Erdos",Sc 'W' "Reisig"],"Stuttering in Petri Nets"), ([Sc 'M' "Smith",Sc 'X' "Chen"],"First Order Derivates in Structured Programming"), ([Sc 'T' "Jablonski",Sc 'Z' "Hsueh"],"Selfstabilizing Data Structures"), ([Sc 'X' "Chen",Sc 'L' "Li"],"Prime Numbers and Beyond")] As in the previous problem, we start by writing a function that defines all the neighbors (that is, those who are in direct connection with this author):
neighbours :: Database -> Author -> [Author] Unlike the previous task, each element of the database, we may contain more than two elements of type Author, so the function mapMaybe can not do. For each element of the database ([Author], PaperTitle) we will check whether the author whose neighbors we are trying to find is in the [Author] array, if so, take the entire [Author] array, if not, go to the next element Database. In the end, it will be necessary to remove the name of the author of which we were looking for from the resulting list (we are looking for its neighbors, therefore, we need nothing):
neighbours :: Database -> Author -> [Author] neighbours (Db []) _ = [] neighbours (Db ((a,_):xs)) (Sc is) = filter (/= (Sc is)) ((neighbour a) ++ (neighbours (Db xs) (Sc is))) where neighbour a | (Sc is) `elem` a = a | otherwise = [] Do not forget to declare how we will compare our scientists:
instance Eq Scientist where (Sc i1 s1) == (Sc i2 s2) = (i1 == i2) && (s1 == s2) Now we will look for all possible paths from the author of "start" to the scientist (Sc 'P' "Erdos"). The paths function is almost the same as the one we have already written:
paths :: Database -> Author -> [Path] paths db start = paths' [] db start where paths' visited db start | start == (Sc 'P' "Erdos") = [[start]] | start `notElem` visited = [start:rest | next <- neighbours db start, rest <- paths' (start:visited) db next] | otherwise = [] Having an array of all possible paths from the author to Erdos, you can convert each of the paths into its length using the length function (that is, we obtain an array that contains the lengths of each path). From the resulting array, select the minimum number (= shortest path) and subtract one from this number, since Erdos himself has the number 0. We will not forget to check before that if there is any way at all that leads to Erdos (if not, then return -1):
erdosNum :: Database -> Scientist -> ErdosNumber erdosNum db sc | length (paths db sc) == 0 = (-1) | otherwise = (-) (minimum (map length (paths db sc))) 1 Successes in programming!
Source: https://habr.com/ru/post/159127/
All Articles