Приветствую всех пользователей Хабрахабр!
Я недавно начал изучать Haskell, и, немного освоив его, решил поделиться небольшим накопленным опытом. Конечно же, знания Haskell у меня не на таком уровне как у Darkus, поэтому две задачи, которые описаны ниже, ориентированны больше на новичков, но опытные пользователи возможно и поправят, и подскажут как лучше сделать. Эта не только моя первая статья на Хабрахабр, но и вообще мой первый туториал, который я когда-либо писал.
В городе состоящем из n районов надо создать пункты таможни. Но ставить их надо в самых загруженных районах города. Загруженным считается район, через который обязательно надо проехать, если ехать из части города А в часть В, т.е. если нет объездного пути. Если представить город как граф, а районы как узлы, то мы будем искать все «бутылочные горла» (=bottlenecks или еще называют «игольное ушко») для конкретного пути. Даны следующие декларации:
В конечном итоге должна получиться функция:
Т.е. передав этой функции CityMap и два района (начало и конец), мы получим массив всех узлов через которые обязательно надо пройти если хотим попасть из одно пунка в другой.
Для начала приведу пример. Допустим есть у нас следующий город
city = CM (6, [(2,3), (1,2), (3,1), (4,3), (4,6), (5,6), (5,3)])
то вызов функции
Начнем с того, что напишем функцию, которая возвращает всех соседей определённого узла.
Так как каждый элемент Route состоит всего из двух элементов, то можно просто проверять является ли один из элементов пары (p, q) искомому (b) элементу. Если b равен p, то добавляем q и наоборот. Для этого можно использовать функцию mapMaybe.
Тестируем:
Работает! Теперь когда можно найти соседей любого узла, хорошо было бы найти путь между любыми двумя точками. А точнее не просто путь, а все возможные пути:
Надо не забывать на каждом шаге алгоритма запоминать тот узел, который мы уже посетили (иначе будем бесконечно кругами ходить). Алгоритм для поиска путей от start к goal:
1. если start == goal, то возвращаем [[start]]
2. если start НЕ присутствует в массиве посещённых узлов (=visited), то для каждого элемента соседей (=next) ищем путь от этого соседа к goal.
3. иначе возвращаем [] (т.е. если мы уже посещали start)
Проблема в том, что наша функция paths не «сохраняет» на каждом шаге массив посещённых узлов. Это можно реализовать с помощью под-функции paths':
Тестируем:
Имея все возможные пути от А до В, довольно легко найти bottleneck — это тот узел который используется во всех путях. Надо заметить, что узлы А и В тоже будут присутствовать во всех путях, поэтому их надо сразу исключить из возможного множества решений:
Для того чтобы найти то число которое используется во всех paths, будем использовать функцию intersect, которая выдаёт только те элементы, которые встречаются в обоих множествах. Т.е. надо применить эту функцию ко множеству всех возможных решений и первому элементу множества paths, потом ответ применить ко второму элементу, и т.д. Ответ можно записать следующим образом:
Тогда, функцию bottlenecks можно записать в одну строчку:
Не забудьте импортировать модули Data.Maybe (для mapMaybe) и Data.List (для intersect).
Рассмотрим очень похожую задачу, а именно задачу про Число Эрдёша. Вкратце объясню что это такое: все те, кто написал научную статью с математиком Полом Эрдёшом получают число 1, все те кто написал какую-либо научную статью с соавторами Пола Эрдёша (но не с ним самим) получают число 2, и т.д. То есть соавторы людей с числом Эрдёша, равным n, имеют число Эрдёша n+1. Задача заключается в том, чтобы для конкретного человека найти это число (если связь между этим человеком и Эрдёшом найти не удаётся, выводим число -1). Итак, для начала определим типы данных с которыми будем работать — это учёные (учёный состоит из инициала и фамилии), они же являются авторами, а также база данных каждый элемент который, содержит название статьи (научной работы) и имена авторов, которые её опубликовали. Еще задекларируем базу данных, которую мы будем использовать для тестов:
Начнем как и в предыдущей задаче с написания функции, которая определяет всех соседей (т.е. тех, кто находится в непосредственной связи с этим автором):
В отличие от предыдущей задачи, каждый элемент базы данных у нас может содержать более двух элементов типа Author, поэтому функцией mapMaybe не обойтись. Для каждого элемента базы данных ([Author],PaperTitle) мы будем проверять, входит ли автор, соседей которого мы пытаемся найти, в массив [Author], если да, то берем весь массив [Author], если нет, переходим к следующему элементу базы данных. В конце надо будет убрать имя автора которого мы искали из получившегося списка (мы же ищем его соседей, поэтому он нам ни к чему):
Не забудем задекларировать то, как мы будем сравнивать наших учёных:
Теперь будем искать все возможные пути от автора «start» до учёного (Sc 'P' «Erdos»). Функция paths практически не чем не отличается от той, что мы уже написали:
Имея массив всех возможных путей от автора к Эрдёшу, можно преобразовать каждый из путей в его длину с помощью функции length (т.е. получим массив, который содержит длины каждого из путей). Из получившегося массива, выбирем минимальное число (=кратчайший путь) и отнимем единицу от этого числа, т.к. сам Эрдёш имеет число 0. Незабудем перед этим проверить, есть ли вообще какой-либо путь, который ведет к Эрдёшу (если нет, то вернем -1):
Успехов в программировании!
Я недавно начал изучать Haskell, и, немного освоив его, решил поделиться небольшим накопленным опытом. Конечно же, знания Haskell у меня не на таком уровне как у Darkus, поэтому две задачи, которые описаны ниже, ориентированны больше на новичков, но опытные пользователи возможно и поправят, и подскажут как лучше сделать. Эта не только моя первая статья на Хабрахабр, но и вообще мой первый туториал, который я когда-либо писал.
Задача 1
В городе состоящем из n районов надо создать пункты таможни. Но ставить их надо в самых загруженных районах города. Загруженным считается район, через который обязательно надо проехать, если ехать из части города А в часть В, т.е. если нет объездного пути. Если представить город как граф, а районы как узлы, то мы будем искать все «бутылочные горла» (=bottlenecks или еще называют «игольное ушко») для конкретного пути. Даны следующие декларации:
type District = Integer
type NumOfDistricts = Integer
type Route = (District, District)
newtype CityMap = CM (NumOfDistricts, [Route])
-- Вспомогательные типы:
type Path = [District]
type Bottleneck = DistrictВ конечном итоге должна получиться функция:
bottlenecks :: CityMap -> District -> District -> [Bottleneck]Т.е. передав этой функции CityMap и два района (начало и конец), мы получим массив всех узлов через которые обязательно надо пройти если хотим попасть из одно пунка в другой.
Для начала приведу пример. Допустим есть у нас следующий город
city = CM (6, [(2,3), (1,2), (3,1), (4,3), (4,6), (5,6), (5,3)])
то вызов функции
bottlenecks city 1 6Начнем с того, что напишем функцию, которая возвращает всех соседей определённого узла.
neighbours :: CityMap -> District -> [District]Так как каждый элемент Route состоит всего из двух элементов, то можно просто проверять является ли один из элементов пары (p, q) искомому (b) элементу. Если b равен p, то добавляем q и наоборот. Для этого можно использовать функцию mapMaybe.
neighbours (CM (_,rs)) b = mapMaybe neighbour rs
where neighbour (p,q)
| b == p = Just q
| b == q = Just p
| otherwise = NothingТестируем:
*Main Data.List> neighbours city 3[2,1,4,5]Работает! Теперь когда можно найти соседей любого узла, хорошо было бы найти путь между любыми двумя точками. А точнее не просто путь, а все возможные пути:
paths :: CityMap -> District -> District -> [Path]Надо не забывать на каждом шаге алгоритма запоминать тот узел, который мы уже посетили (иначе будем бесконечно кругами ходить). Алгоритм для поиска путей от start к goal:
1. если start == goal, то возвращаем [[start]]
2. если start НЕ присутствует в массиве посещённых узлов (=visited), то для каждого элемента соседей (=next) ищем путь от этого соседа к goal.
3. иначе возвращаем [] (т.е. если мы уже посещали start)
Проблема в том, что наша функция paths не «сохраняет» на каждом шаге массив посещённых узлов. Это можно реализовать с помощью под-функции paths':
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 = []Тестируем:
*Main Data.List> paths city 1 2[[1,2],[1,3,2]]Имея все возможные пути от А до В, довольно легко найти bottleneck — это тот узел который используется во всех путях. Надо заметить, что узлы А и В тоже будут присутствовать во всех путях, поэтому их надо сразу исключить из возможного множества решений:
[1..n] \\ [start, goal] -- где n кол-во узловДля того чтобы найти то число которое используется во всех paths, будем использовать функцию intersect, которая выдаёт только те элементы, которые встречаются в обоих множествах. Т.е. надо применить эту функцию ко множеству всех возможных решений и первому элементу множества paths, потом ответ применить ко второму элементу, и т.д. Ответ можно записать следующим образом:
((((([1..n] \\ [start, goal]) intersect paths[0]) intersect paths[1]) intersect paths[2]) intersect...)Тогда, функцию bottlenecks можно записать в одну строчку:
bottlenecks :: CityMap -> District -> District -> [Bottleneck]
bottlenecks cm@(CM (n,_)) start goal = foldl intersect ([1..n] \\ [start, goal]) $ (paths cm start goal)Не забудьте импортировать модули Data.Maybe (для mapMaybe) и Data.List (для intersect).
Задача 2
Рассмотрим очень похожую задачу, а именно задачу про Число Эрдёша. Вкратце объясню что это такое: все те, кто написал научную статью с математиком Полом Эрдёшом получают число 1, все те кто написал какую-либо научную статью с соавторами Пола Эрдёша (но не с ним самим) получают число 2, и т.д. То есть соавторы людей с числом Эрдёша, равным n, имеют число Эрдёша n+1. Задача заключается в том, чтобы для конкретного человека найти это число (если связь между этим человеком и Эрдёшом найти не удаётся, выводим число -1). Итак, для начала определим типы данных с которыми будем работать — это учёные (учёный состоит из инициала и фамилии), они же являются авторами, а также база данных каждый элемент который, содержит название статьи (научной работы) и имена авторов, которые её опубликовали. Еще задекларируем базу данных, которую мы будем использовать для тестов:
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")]
Начнем как и в предыдущей задаче с написания функции, которая определяет всех соседей (т.е. тех, кто находится в непосредственной связи с этим автором):
neighbours :: Database -> Author -> [Author]В отличие от предыдущей задачи, каждый элемент базы данных у нас может содержать более двух элементов типа Author, поэтому функцией mapMaybe не обойтись. Для каждого элемента базы данных ([Author],PaperTitle) мы будем проверять, входит ли автор, соседей которого мы пытаемся найти, в массив [Author], если да, то берем весь массив [Author], если нет, переходим к следующему элементу базы данных. В конце надо будет убрать имя автора которого мы искали из получившегося списка (мы же ищем его соседей, поэтому он нам ни к чему):
neighbours :: Database -> Author -> [Author]
neighbours (Db []) _ = []
neighbours (Db ((a,_):xs)) (Sc i s) = filter (/= (Sc i s)) ((neighbour a) ++ (neighbours (Db xs) (Sc i s)))
where
neighbour a
| (Sc i s) `elem` a = a
| otherwise = []Не забудем задекларировать то, как мы будем сравнивать наших учёных:
instance Eq Scientist where
(Sc i1 s1) == (Sc i2 s2) = (i1 == i2) && (s1 == s2)Теперь будем искать все возможные пути от автора «start» до учёного (Sc 'P' «Erdos»). Функция paths практически не чем не отличается от той, что мы уже написали:
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 = []Имея массив всех возможных путей от автора к Эрдёшу, можно преобразовать каждый из путей в его длину с помощью функции length (т.е. получим массив, который содержит длины каждого из путей). Из получившегося массива, выбирем минимальное число (=кратчайший путь) и отнимем единицу от этого числа, т.к. сам Эрдёш имеет число 0. Незабудем перед этим проверить, есть ли вообще какой-либо путь, который ведет к Эрдёшу (если нет, то вернем -1):
erdosNum :: Database -> Scientist -> ErdosNumber
erdosNum db sc
| length (paths db sc) == 0 = (-1)
| otherwise = (-) (minimum (map length (paths db sc))) 1Успехов в программировании!