Go to Qiita Advent Calendar 2024 Top
LoginSignup
21
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

アカウンティング・サース・ジャパンAdvent Calendar 2017

Day 12
@hirota745

『プログラミングの基礎』 in Elixir

Last updated at Posted at 2017-12-12

はじめに

『プログラミングの基礎』という本があります。Amazonのレビューによると、関数プログラミングの入門書としても使えるようで、ちょうど私も関数プログラミングに入門したいと思っていた時だったので読んでみました。ただし、この本の中ではOCamlというプログラミング言語を使っているのですが、どうせやるなら最近の言語で、ということでElixirを使ってみようと思います。

ここではこの本の目標である、「メトロネットワーク最短路問題を解くプログラム」をElixirを使って本の順番に沿って書いていきたいと思います。ここでは動作する最初のプログラムの作成まで(16章まで)を行います。

また、最短路問題に直接関わらない事項については省略しますが、今回のプログラムの作成に最低限必要なElixirに関する事項(関数定義、データ型など)については少し書きます。

対象読者

『プログラミングの基礎』をElixirで試しつつ読んでいる方(ものすごく狭い範囲ですが…)

Elixirレベル

『プログラミングElixir』をとりあえず一周読んでみたレベルです。ですので本来のElixir的な書き方とは異なる可能性があります。

内容

4章 関数の定義

Elixirでの無名関数と名前付き関数は以下のように定義します。

無名関数

無名関数
fn
  parameter-list -> body
  parameter-list -> body
  ...
end

&(&1 + &2)はfn (a, b) -> a + b endのショートカットとなります。
また、無名関数を呼び出す際は引数との間にドット(.)が必要です。

無名関数の呼び出し
(fn (a, b) -> a + b end).(1, 2)
(&(&1 + &2)).(1, 2)
sum = &(&1 + &2)
sum.(1, 2)

名前付き関数

Elixirでは名前付き関数を定義する場合、モジュールの中に定義する必要があります。

名前付き関数
defmodule MyModule do
  def sum(a, b), do: a + b
end

上記のような書き方のシンタックスシュガーとして以下のように書くこともできます(一行で書く場合は上、複数行では下を使うのが普通のようです)。

名前付き関数
defmodule MyModule do
  def sum(a, b) do
    a + b
  end
end

名前付き関数を呼び出す際は、無名関数のときのようなドット(.)は不要です。

名前付き関数の呼び出し
MyModule.sum(1, 2)

5章 条件分岐

if

Elixirではifは以下のように書きます。

if
if condition, do: xxx, else: yyy

シンタックスシュガーとして以下のように書くこともできます。

if
if condition do
  xxx
else
  yyy
end

7章 組とパターンマッチ

OCamlでの「組」の代わりとして、Elixirのタプル(タプルは{:a, :b}のように中括弧で囲む)を使用したいと思います。

8章 レコード

OCamlでの「レコード」の代わりとして、ElixirのMapを使用していきます。
(Mapと似たようなものとして他にキーワードリストというものがあり、順序が保証されているなどの特徴があるのですが、ここではMapを使用します。)

Map
map = %{name: "myname", age: 10}
# アクセス方法
map[:name]
map.name

OCamlの「type」の代わりにElixirのStructを使います。

Struct
defmodule MyStruct do
  defstruct name: "", age: 0
end
%MyStruct{name: "myname", age: 10}

ここからメトロネットワーク最短路問題に関するプログラムの作成に入ります。

[metro]駅名情報の定義

まず最短路問題を解くために必要なデータとして、駅名情報(漢字名、かな名、ローマ字、所属路線名)を表すStructを定義します。

Ekimei
defmodule Ekimei do
  defstruct kanji: "", kana: "", romaji: "", shozoku: ""
end

次に駅と駅の間のつながりを表す情報(駅間情報(起点漢字名、終点漢字名、路線名、駅間距離、所要時間))を表すStructを定義します。

Ekikan
defmodule Ekikan do
  defstruct kiten: "", shuten: "", keiyu: "", kyori: 0, jikan: 0
end

9章 リスト

リストを連結する際、OCamlではコロン2つ(::)を使うのですが、Elixirではパイプ(|)を使います。またリスト中の区切りとして、セミコロン(;)の代わりにカンマ(,)を使います。

リスト
# 1 :: []の代わりに
[1 | []]
# [2; 1]の代わりに
[2, 1]

OCamlでは再帰関数を定義するときには、再帰でない関数を定義するときとは異なる書き方(letではなくlet recを使う)をしますが、Elixirでは再帰関数かどうかを区別して定義する必要はありません。

[metro]駅名リストと駅間リストの準備

メトロネットワーク最短路問題を解くために必要な元データを準備します。実際のデータはこの本のサポートページからダウンロードできます。これをElixirで使えるようにするために以下のように加工します。

  • リスト中の区切りを表すセミコロン(;)をカンマ(,)に変更
  • ひとつのデータを表す{}を%Ekimei{}または%Ekikan{}に変更
  • "X."を"X.0"に変更('X'は数字)

Elixirでは名前付き関数はモジュール内に定義する必要があります。しかし、モジュール外に定義された変数にはモジュール内からはアクセスできないようです。そこで駅名リスト・駅間リストをGlobalDataというモジュール内にAttributeを使って定義し(@で始まる部分)、それを外部へ公開する関数も合わせて定義しています。

GlobalData.ekimei_listとGlobalData.ekikan_list
# 駅名リスト
defmodule GlobalData do
  @ekimei_list [
    %Ekimei{kanji: "代々木上原", kana: "よよぎうえはら", romaji: "yoyogiuehara", shozoku: "千代田線"},
    ...(省略)
  ]
  @ekikan_list [
    %Ekikan{kiten: "代々木上原", shuten: "代々木公園", keiyu: "千代田線", kyori: 1.0, jikan: 2},
    ...(省略)
  ]

  def ekimei_list, do: @ekimei_list
  def ekikan_list, do: @ekikan_list
end

10章 再帰関数を使ったプログラミング

OCamlでは局所変数を定義する際に使用するlet 変数名 = 式1 in 式2ですが、Elixirでは同様のものを見つけられませんでした(単純に見つけられなかっただけで、同様のものがあるかもしれません)。ここでは単純にローカル変数を作ることで代用します。

[metro]駅名リスト・駅間リストからの情報の取得

[metro]かな名からの漢字名への変換

駅名リストを使って、かな名から漢字名を取得する関数を定義します。

romaji_to_kanji
def romaji_to_kanji(_romaji, []), do: ""
def romaji_to_kanji(romaji, [%Ekimei{romaji: r, kanji: k} | _tail]) when r == romaji, do: k
def romaji_to_kanji(romaji, [_head | tail]) do
  romaji_to_kanji(romaji, tail)
end

[metro]駅間の距離を取得する関数の定義

駅名を二つ漢字名で受けて、駅間リストからその距離を取得する関数を定義します。
駅名はどちらを先に指定しても同じ結果が返るようにします。直接つながっていない場合は、無限大を返します。
ここでは無限大を表現するために9999kmを使います(日本の長さは3000kmくらいなので、ここでは9999kmを無限大としても問題無さそうです)。

get_ekikan_kyori
def get_ekikan_kyori(_kiten, _shuten, []), do: 9999
def get_ekikan_kyori(kiten, shuten, [%Ekikan{kiten: k, shuten: s, kyori: ky} | _tail]) when (kiten == k and shuten == s) or (shuten == k and kiten == s), do: ky
def get_ekikan_kyori(kiten, shuten, [%Ekikan{kiten: k, shuten: s, kyori: ky} | tail]), do: get_ekikan_kyori(kiten, shuten, tail)

12章 ダイクストラのアルゴリズム

この本で使用する、ダイクストラのアルゴリズムは以下のようになっています(このアルゴリズムは、重みが非負の場合は正しく最短路を求められます)。

ダイクストラのアルゴリズム(『プログラミングの基礎』P113より)

  1. 始点から始点への最短距離は0と確定する。それ以外の点への最短距離は(まだわからないので)無限大としておく。
  2. Uを最短経路が確定した点の集合,Vを最短距離がまだ確定していない点の集合とする。最初はUには始点のみ,Vには始点以外のすべての点が入る。
  3. Vが空集合になったら,すべての点への最短距離が確定したことを意味するので終了する。
  4. 直前に確定した点につながっている点について,その最短距離を更新する。具体的には「その点がすでに持っている最短距離」と「直前に確定した点経由でその点に行った場合の最短距離」を比べ,短い方をその点への最短距離とする。
  5. Vの中で,最短距離が最小の点pを選択する。
  6. pの保持している最短距離を確定しpをVからUに移す。
  7. ステップ3へ。

[metro]各点の状態を保持する型の定義

ある時点での各点の状態(駅名、最短距離、最短経路となる駅名のリスト)を保持するStructを定義します。

Eki
defmodule Eki do
  defstruct namae: "", saitan_kyori: 0, temae_list: []
end

[metro]初期状態の駅状態のリストを作成する関数の定義

上で定義した型を使って、各駅の初期状態(最短距離: 無限大、最短経路: 空)のリストを作成する関数を定義します。

make_eki_list
def make_eki_list([]),  do: []
def make_eki_list([%Ekimei{kanji: k} | tail]) do
  [%Eki{namae: k, saitan_kyori: 9999, temae_list: []} | make_eki_list(tail)]
end

[metro]ステップ1を実行する関数の定義

アルゴリズムのステップ1を実行する関数を定義します。上で定義した関数を使って作成した駅状態リストを引数で受けることを前提として、始点の駅の駅状態の最短距離を0とする関数を定義します。

shokika
def shokika([], _shiten), do: []
def shokika([%Eki{namae: k} | tail], shiten) when shiten == k do
  [%Eki{namae: k, saitan_kyori: 0, temae_list: [shiten]} | shokika(tail, shiten)]
end
def shokika([head | tail], shiten), do: [head | shokika(tail, shiten)]

[metro]駅名リストの重複を削除する関数の定義

駅名リストを駅名の情報としてのみ使用する場合、路線名は不要です。路線名があるために現状の駅名リストには同じ駅の駅名が複数登録されています。ここで路線名を無視し、駅名の重複を取り除く関数を定義します。

seiretsu
# 駅名(かな名)の同じものがない場合のみリストに値を挿入する関数
# 重複を取り除く関数で使用する。
def insert_ekimei([], n), do: [n]
def insert_ekimei([head | tail], n) do
  if n.kana == head.kana do
    [head | tail]
  else
    if n.kana < head.kana do
      [n | [head | tail]]
    else
      [head | insert_ekimei(tail, n)]
    end
  end
end
# 与えられた駅名リストの重複を(かな名に従って)取り除く関数
def seiretsu([]), do: []
def seiretsu([head | tail]), do: insert_ekimei(seiretsu(tail), head)

13章 一般化と高階関数

[metro]ステップ4を実行する関数の定義

アルゴリズムのステップ4を実行する関数を定義します。ステップ4では、ある点pにつながっている各点について、それまでの最短距離と点pを経由した場合の最短距離を比較します。点pを経由した場合の方が距離が短い場合、その点の最短距離と最短経路を更新します。

まずはある点pとリストではなく、ある点pとある点qで上記の処理を行う関数を定義します。

koushin1
def koushin1(p, q) do
  kyori = get_ekikan_kyori(p.namae, q.namae, GlobalData.ekikan_list())
  if kyori == 9999 do
    q
  else
    if q.saitan_kyori > (p.saitan_kyori + kyori) do
      %Eki{namae: q.namae, saitan_kyori: p.saitan_kyori + kyori, temae_list: [q.namae | p.temae_list]}
    else
      q
    end
  end
end

次にこれを点pとリストに対して実行する関数を定義します。こちらの関数がステップ4を実行する関数となります。

koushin
def koushin(p, v), do: Enum.map(v, fn q -> koushin1(p, q) end)

14章 高階関数を使ったリスト処理

本章では、関数内だけで使用する関数を局所関数として定義していますが、Elixirでは関数内に名前付き関数を定義することはできませんでした。そこで無名関数を変数に入れて使うことにします。

[metro]ステップ4を実行する関数の定義(再)

先ほど定義したkoushin1関数は、koushin関数内でのみ使用しています。そこでkoushin1関数をkoushin関数内で定義して使うように変更します。

koushin
def koushin(p, v) do
  koushin1 = fn (p, q) ->
    kyori = get_ekikan_kyori(p.namae, q.namae, GlobalData.ekikan_list())
    if kyori == 9999 do
      q
    else
      if q.saitan_kyori > (p.saitan_kyori + kyori) do
        %Eki{namae: q.namae, saitan_kyori: p.saitan_kyori + kyori, temae_list: [q.namae | p.temae_list]}
      else
        q
      end
    end
  end
  Enum.map(v, fn q -> koushin1.(p, q) end)
end

[metro]ステップ1を実行する関数の定義(再)

はじめの方で定義したステップ1を実行する関数の定義は、その直前に定義した、初期状態の駅状態リストを作成する関数で作成した駅状態リストを入力とすることを前提としていました。これらをひとつの関数にまとめます。

make_initial_eki_list
def make_initial_eki_list(lst, shiten) do
  Enum.map(lst, fn
    %Ekimei{kanji: k} when shiten == k -> %Eki{namae: k, saitan_kyori: 0, temae_list: [shiten]}
    %Ekimei{kanji: k} -> %Eki{namae: k, saitan_kyori: 9999, temae_list: []}
  end)
end

[metro]ステップ4を実行する関数の定義(再々)

さらに、ステップ4を実行する関数の定義(再)では局所関数定義(の代わりの無名関数定義)を使っていましたが、この局所関数(もどき)自体も単純な無名関数に変更します。

koushin
def koushin(p, v) do
  Enum.map(v, fn
    q -> kyori = get_ekikan_kyori(p.namae, q.namae, GlobalData.ekikan_list())
         if kyori == 9999 do
           q
         else
           if q.saitan_kyori > (p.saitan_kyori + kyori) do
             %Eki{namae: q.namae, saitan_kyori: p.saitan_kyori + kyori, temae_list: [q.namae | p.temae_list]}
           else
             q
           end
         end
  end)
end

15章 新しい形の再帰

[metro]ステップ5、6を実行する関数の定義

駅状態リストの中から最短距離が最小の駅を見つけ、その駅状態とその駅を除いた駅状態リストを返す関数を定義します。これによりアルゴリズムのステップ5とステップ6を行います。

saitan_wo_bunri
def saitan_wo_bunri([head | []]), do: {head, []}
def saitan_wo_bunri([head | tail]) do
  {p, v} = saitan_wo_bunri(tail)
  # headとpを比較
  if head.saitan_kyori < p.saitan_kyori do
    {head, [p | v]}
  else
    {p, [head | v]}
  end
end

この関数は右からの畳み込みを使って定義することができます。

saitan_wo_bunri
def saitan_wo_bunri([head | tail]) do
  List.foldr(tail,
    {head, []},
    fn x, {p, v} -> if x.saitan_kyori < p.saitan_kyori, do: {x, [p | v]}, else: {p, [x | v]} end
  )
end

16章 情報の蓄積

[metro]ステップ4を実行する関数の定義(再々々)

ステップ4を実行するために必要な元データは、ステップ4を実行する関数内で直にグローバルから取得しています。これを外部から与えられるように変更します。

koushin
  def koushin(p, v, ekikan_list) do
    Enum.map(v, fn
      q -> kyori = get_ekikan_kyori(p.namae, q.namae, ekikan_list)
           if kyori == 9999 do
             q
           else
             if q.saitan_kyori > (p.saitan_kyori + kyori) do
               %Eki{namae: q.namae, saitan_kyori: p.saitan_kyori + kyori, temae_list: [q.namae | p.temae_list]}
             else
               q
             end
           end
    end)
  end

[metro]ダイクストラのアルゴリズムのメインループを実行する関数の定義

ダイクストラのアルゴリズムのメインループ

  • 駅状態リスト(V)から最短距離を持つ駅状態(p)を抜き出す。
  • 残りの駅状態リスト(V)のうち、最短距離を持つ駅(p)につながる駅状態を更新する。
  • 駅状態リスト(V)が空になるまで繰り返す。

を実行する関数を定義します。

dijkstra_main
def dijkstra_main([], _ekikan_list), do: []
def dijkstra_main([head | tail], ekikan_list) do
  {saitan, rest} = saitan_wo_bunri([head | tail])
  [saitan | dijkstra_main(koushin(saitan, rest, ekikan_list), ekikan_list)]
end

[metro]ある駅間の最短経路を求める関数の定義

これまで定義してきた関数を使って、ダイクストラのアルゴリズムを動かすための関数を定義できます。
この関数には、ローマ字で始点、終点を指定します。

dijkstra
def dijkstra(shiten, shuten) do
  ekimei_list = seiretsu(GlobalData.ekimei_list)
  shiten_kanji = romaji_to_kanji(shiten, ekimei_list)
  shuten_kanji = romaji_to_kanji(shuten, ekimei_list)
  initial_eki_list = make_initial_eki_list(ekimei_list, shiten_kanji)
  eki_list = dijkstra_main(initial_eki_list, GlobalData.ekikan_list)
  Enum.find(eki_list, fn %Eki{namae: n} -> n == shuten_kanji end)
end

21章 逐次実行

[metro]駅状態の表示関数の定義

これまでの関数は全て副作用のない関数でした。最終的には結果を画面に出力する関数が必要です。この関数はこれまでと違い、副作用のある関数となります。

print_eki
def print_eki(%Eki{namae: n, saitan_kyori: s, temae_list: t}) do
  IO.write "#{n}までの最短経路は"
  Enum.each(Enum.reverse(t), fn (n) -> IO.write " #{n} " end)
  IO.puts "で、その距離は#{s}kmです。"
end

[metro]メトロネットワーク最短路問題のプログラム

コマンドライン引数でローマ字の始点と終点を受け取り、その最短経路を出力するプログラムを作ります。
ElixirではSystem.argvにコマンドライン引数がリスト形式で設定されます。
(これまでに定義してきた関数は、全てMetroモジュール内に定義しています。)

Main.main
defmodule Main do
  def main(argv) do
    [shiten, shuten] = argv
    Metro.print_eki(Metro.dijkstra(shiten, shuten))
  end
end

Main.main(System.argv)

最後に実行してみます。

$ elixir metro.exs myogadani meguro
目黒までの最短経路は 茗荷谷  後楽園  飯田橋  市ヶ谷  麹町  永田町  溜池山王  六本木一丁目  麻布十番  白金高輪  白金台  目黒 で、その距離は12.700000000000003kmです。

どうやらうまく動いているようです。

まとめ

『プログラミングの基礎』という書籍をもとに関数型言語を使ってプログラムを作ってみました。関数プログラミングやElixirに関してはまだ入門者レベルですが、なにか動くプログラムを最後まで作ってみることがまずは大切だと思いますので、第一段階としては良かったと思います。
今回はとりあえず動くものを作るところまでとなりましたが、書籍ではこのプログラムをさらに改良しています。またメトロネットワーク最短路問題のプログラム以外の部分にも大切そうなことが書いてあります。内容もわかりやすく、そこまで厚い本ではないので、途中で挫折せずに読みきることができると思います。興味のある方はぜひ書籍を読んでみていただければ、と思います。

(作成したプログラムをここに置いておきます。)

参考文献

21
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
21
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?