Две простенькие задачи на Haskell (для начинающих)

Приветствую всех пользователей Хабрахабр!
Я недавно начал изучать 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

должен вернуть узел номер 3 (массив состоящий из одного узла).

Начнем с того, что напишем функцию, которая возвращает всех соседей определённого узла.

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 -> [Pfad]
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 -> [Pfad]
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

Успехов в программировании!

Автор: IvanP

Источник