最近、Haskellの勉強を始め、少し習得したので、少し蓄積した経験を共有することにしました。 もちろん、Haskellの知識はDarkusのようなレベルではないため、以下に説明する2つのタスクは初心者を対象としていますが、経験豊富なユーザーはおそらくそれを修正し、改善方法を教えてくれるでしょう。 これは、Habrahabrに関する私の最初の記事だけでなく、一般に、これまでに書いた最初のチュートリアルです。
タスク1
n地区で構成される都市では、税関ポイントを作成する必要があります。 しかし、彼らは街の最も忙しいエリアにインストールする必要があります。 ロードされているのは、都市Aの一部からパートBに行く場合に通過する必要があるエリアです。 迂回路がない場合。 都市をグラフ、地域をノードと考えると、特定のパスのすべての「ボトルネック」（=ボトルネックまたは「針の目」とも呼ばれます）を探します。 次の宣言が与えられます。
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と2つの領域（開始と終了）を渡すと、パンクから別のパンクに移動する場合に通過する必要があるすべてのノードの配列が取得されます。
例を挙げましょう。 次の都市があるとしましょう
city = CM（6、[（2,3）、（1,2）、（3,1）、（4,3）、（4,6）、（5,6）、（5,3）]）
その後、関数呼び出し
bottlenecks city 1 6
ノード番号3（1つのノードで構成される配列）を返す必要があります。
まず、特定のノードのすべての隣接ノードを返す関数を作成します。
neighbours :: CityMap -> District -> [District]
各Route要素は2つの要素のみで構成されているため、ペア（p、q）の要素の1つが目的の（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]
動作します！ 任意のノードの隣接ノードを見つけることができるようになったので、任意の2つのポイント間のパスを見つけると便利です。 むしろ、単なるパスではなく、可能なすべてのパス：
paths :: CityMap -> District -> District -> [Path]
アルゴリズムのすべてのステップで、すでに訪れたノードを思い出すことを忘れてはなりません（そうでなければ、無限に円を描いて歩きます）。 スタートからゴールまでのパスを見つけるためのアルゴリズム：
1. start ==ゴールの場合、[[start]]を返します
2.訪問済みノードの配列にstartが存在しない場合（=訪問済み）、近隣の各要素（=次）について、この近隣から目標までのパスを検索します。
3.それ以外の場合は[]を返します（つまり、すでにstartにアクセスした場合）
問題は、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]]
AからBへのすべての可能なパスがあるため、ボトルネックを見つけるのは非常に簡単です。これは、あらゆる方法で使用されるノードです。 ノードAとBもすべてのパスに存在するため、可能なソリューションのセットからすぐに除外する必要があることに注意してください。
[1..n] \\ [start, goal] -- n -
すべてのパスで使用される番号を見つけるために、両方のセットで見つかった要素のみを返す交差関数を使用します。 つまり この関数をすべての可能なソリューションのセットとセットパスの最初の要素に適用してから、2番目の要素などに回答を適用する必要があります。 答えは次のように書くことができます。
((((([1..n] \\ [start, goal]) intersect paths[0]) intersect paths[1]) intersect paths[2]) intersect...)
次に、ボトルネック関数を1行で記述できます。
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
非常によく似た問題、つまりエルドス数の問題を考えます。 それが何であるかを簡単に説明します：数学者PaulErdösと科学論文を書いた人はすべて1番、共著者PaulErdösと科学論文を書いた人（彼とは一緒ではありません）は2番などになります。 つまり、nに等しいエルドス数を持つ人々の共著者は、エルドス数n + 1を持ちます。 タスクは、特定の人のこの番号を見つけることです（この人とErdösの間の接続が見つからない場合、番号-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型の要素を3つ以上含めることができるため、mapMaybe関数は不可欠です。 各データベースアイテム（[Author]、PaperTitle）について、見つけようとしている隣人の著者が[Author]配列に入るかどうかを確認し、そうであれば、[Author]配列全体を取得し、そうでない場合は、次の要素に移動しますデータベース 最後に、結果リストから探している著者の名前を削除する必要があります（彼の隣人を探しているので、彼を必要としません）。
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 = []
科学者を比較する方法を宣言することを忘れないでください。
instance Eq Scientist where (Sc i1 s1) == (Sc i2 s2) = (i1 == i2) && (s1 == s2)
ここで、「開始」の作成者から科学者（Sc 'P' "Erdos"）までのすべての可能な方法を探します。 パス関数は、すでに書いたものと実質的に違いはありません。
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関数を使用して各パスをその長さに変換できます（つまり、各パスの長さを含む配列を取得します）。 結果の配列から、最小数（=最短パス）を選択し、この数から1を引きます。 Erdös自体の番号は0です。忘れる前に、Erdösにつながる方法があるかどうかを確認してください（ない場合は、-1を返します）。
erdosNum :: Database -> Scientist -> ErdosNumber erdosNum db sc | length (paths db sc) == 0 = (-1) | otherwise = (-) (minimum (map length (paths db sc))) 1
プログラミングで頑張ってください！