Go to Qiita Advent Calendar Top
LoginSignup
7
1

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.

@ken_hamada(Kenichiro Hamada)

【老害が高級言語で苦しんでますシリーズ１】Elixirのリスト・再帰系でしょーもないミスをした話

Last updated at Posted at 2019-04-28

プロフを見ても分るかと思いますが、私は老害なもので今風のプログラミングがとてもとても苦手です。

例えばC言語でコードを組む時にそう積極的に再帰とかは使っていなかったのです（これは単に筆者の技量の問題ですね）。でも関数型で組むときは再帰を上手く使えないとかなーというのもあってお勉強中です。

これはリストとか再帰で苦しむ老害を見て笑いつつ、なにがしか参考になって貰えれば嬉しいかなというポエム寄りな記事なのです。長い割には内容は薄いので読もうと思う方は注意が必要なのです。

筆者の環境

本記事の内容を実行しながら確認したい場合は、ErlangとElixirが動く環境が必要です。私の確認環境は以下。

  • CentOS 7.5.1804
  • Erlang 10.2
  • Elixir 1.7.4

一応公式を以下に。

ただCentOSとか私はソースからビルドとかもしてました。要望があればざっくりとまとめた記事作ってはみますが需要ありますかね…

何故かしばらくErlangの話

アナグラムのコード

「プログラミングErlang」のp.44にあるアナグラムのコードです。以下は同コードを元に少し手を加えたものです。

%% test.erlとしてこれを書いてみました。
-module(test).

-export([perms/1]).
-import(lists, [all/2, any/2, filter/2, reverse/1, reverse/2,
		foreach/2, map/2, member/2, sort/1]).

perms([]) -> [[]];
perms(L)  -> [[H|T] || H <- L, T <- perms(L--[H])].

  • （出典）プログラミングErlang
    https://www.ohmsha.co.jp/book/9784274067143/

    上記の「ダウンロード」でダウンロード出来るコードから引用し、少し手を加えたのが上記コードです。

ぶっちゃけこのコラムはこれをElixirでやりたかったというだけの話になりますので、そんなの速効で書けるという方にとって以下の説明はもうマジで読む価値ないですごめんなさい。

さて、これをコンパイル＆実行すると以下のようになるです。erlを起動して以下の感じで。これはtest.erlをコンパイルする例です。

1> c(test).
{ok,test}
2> test:perms("123").
["123","132","213","231","312","321"]
3> test:perms([1,2,3]).
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

ちなみにerlのシェルから出たい場合にはCTRL-Cからのa＋＜エンター＞です

このコードをプログラミングErlangでは「単語の文字を入れ替えて別な単語を作る」と定義しています。と言われましてもリスト構造（head, tail）と再帰使いまくりで私には非常に難しいのですー（涙目ｗ）。

まず、関数本体は以下の2行です。

perms([]) -> [[]];
perms(L)  -> [[H|T] || H <- L, T <- perms(L--[H])].

permsと同じ名前の関数が２つありますが、()内を見てください。条件が違います。上のは [] という空のリストの場合に処理されます。次の L というのはこの場合、空ではないリストが来た場合に処理されます（Lが空ではないリストであるというのはコードとかから判断する感じ・・なのかな）

で、最初の行はまーいいです

perms([]) -> [[]];

空のリストが来たら、空のリストを戻すってそんだけのコードですね（実は筆者ここの認識がメチャ甘いのですが、それは後で明らかになる話）。問題は次のリストが空ではない場合のコード。

perms(L)  -> [[H|T] || H <- L, T <- perms(L--[H])].

うわー関数型だーという頭の悪い感想しか出ません…うん、徐々にやろうと。

リスト

リストの話。リストはまー[1,2,3]みたいなデータを並べた物です。さすがに老害でも配列の概念でここは理解できるですよ。

ここからが関数型っぽいなーと思うのですが（そうか？という突っ込みが怖いｗ）、このリストを先頭とそれ以外に分ける考え方がErlangにはあります。つまり以下。

%% [H|T] の説明
1> A = [1,2,3].
[1,2,3]
2> [B|C] = A.
[1,2,3]
3> B.
1
4> C.
[2,3]

ちなみに一個した値がないリストの場合はどうなるかというと、以下のようにそれ以外が空のリスト[]になります。

5> E = [3].
[3]
6> [F|G] = E.
[3]
7> F.
3
8> G.
[]

リストの各要素毎に処理をさせたい場合に、Erlangではリスト内包表記を使って表現する事が出来ます。例えば[1,2.3]という処理があって、これをそれぞれ2倍さす場合に、C言語なら for で回す感じになりますが、以下の感じで表記出来ます。

%% || の説明
1> A = [1,2,3].
[1,2,3]
2> [ X * 2 || X <- A].
[2,4,6]

更に結合とか削除も当然ですができます。

%% -- の説明
1> A = [1,2,3].
[1,2,3]
2> A -- [2].
[1,3]
3> A ++ [4].
[1,2,3,4]

関数

あとはえーと関数の書き方かな。例えば単純に二倍する関数は以下の感じです。

%% 関数の説明。 func_sample.erlとしてこれを書いてみました。
-module(func_sample).
-export([test/1]).

test(X) -> X * 2.

コンパイル＆実行するとこうなります。

1> c(func_sample).
{ok,func_sample}
2> func_sample:test(100).
200

さて、perms関数はというと。

これまでの情報を元にまとめると下図の感じになるです。

perm_vrlang.png

この辺りの説明はnitsujiさん（？）の以下記事が非常に良くまとまっています。

上記などを元に、私の方でざっくりまとめたのが以下の図です（図の方が下手だとかツッコミが来そうですが…）

図がちっこく映るという場合は図をクリックしてみましょう。

perm_desc.png

さて、長すぎる前ふりで大変申し訳ありませんが、これをElixirで実装してみましょうというのがお題です。とはいえ文字列はElixirだと少しやりざまが変わるので、リストに関して同じ処理をする関数を実装する感じで進めます。

Elixirで再帰だリストだやってみる

まずは環境系

Elixirの動作確認はmixでやりました。testプロジェクトを作ってみます（testフォルダが出来る）。以下の感じでiexのシェルに入ります。

# mix new test
# cd test
# iex -S mix

次にソースコード（test/lib/test.ex)を変更します。test関数を追記です。

defmodule Test do
  @moduledoc """
  Documentation for Test.
  """
  ##この関数を試験的に追加します。
  def test() do
    IO.puts "Test program"
  end
  ##ここまで。後はmix様がお作りになったものです

  @doc """
  Hello world.

  ## Examples

      iex> Test.hello()
      :world

  """
  def hello do
    :world
  end
end

で、iexで以下のように実行します。

iex(9)> recompile
Compiling 1 file (.ex)
:ok
iex(10)> Test.test
Test program

これで実行＆確認の準備が出来たです。次に今回使いそうな主要な機能を確認します。
ちなみにiexのシェルから出たい場合もCTRL-Cからのa＋＜エンター＞です

リスト

例えば[1,2,3]がリストになるのはErlangと同じです。先頭とそれ以外に分離さすのも同じ感じですね。変数名が小文字になるのが違ったりはしますが、以下の感じです。

# [H|T] の説明
iex(1)> a = [1,2,3]
[1, 2, 3]
iex(2)> [b|c] = a
[1, 2, 3]
iex(3)> b
1
iex(4)> c
[2, 3]

リストに一個しか値がない場合の挙動も同じですね。

iex(5)> e = [3]
[3]
iex(6)> [f|g] = e
[3]
iex(7)> f
3
iex(8)> g
[]

内包表記ですが、forを使った例で。Erlangの説明の時と同じでリストの各値を倍にする記述は以下の通りです。ここらは双方の違いが出てきて興味深いです。

# for の説明
iex(1)> a = [1,2,3]
[1, 2, 3]
iex(2)> for x <- a, do: x * 2
[2, 4, 6]

リストから特定の値を足したり引いたりですね、これはあんまり変わらず以下です。

%% -- の説明
iex(1)> a = [1,2,3]
[1, 2, 3]
iex(2)> a -- [2]
[1, 3]
iex(3)> a ++ [4]
[1, 2, 3, 4]

関数

ソースコード（test/lib/test.ex)のtest関数を以下のように書き換えてみます。


  ##この関数を試験的に追加します。

  def test(x), do: x * 2

  ##ここまで。後はmix様がお作りになったものです

iexの場合 recompileコマンドで再度ビルドする事が出来ます。以下はビルド＆実行の結果

iex(1)> recompile
Compiling 1 file (.ex)
:ok
iex(2)> Test.test(100)
200

Perms関数（バグ込）の作成

これらの要素を込みで、perms関数をElixirに持ってきます。要は

  • forで各値を総当たりさせる
  • [h|t]で分割して、それぞれ処理をさせる
  • そうすると、最後に空のリストが引数になるので、その手当もする
  • で、結果が集まって目的のデータが出てくる筈。

で組んだのがこれ（※１）です。以下をtest/lib/test.exに追加します。

  def perms([]), do: []
  def perms(l) do
    for h <- l, t <- perms(l -- [h]), do: [h|t]
  end
  • （※１）実はpermsの再帰をどこに入れるのかとかでも迷って色々やったのですが（笑）、そこは省略です。

同じ関数を並べると()内の条件で処理が振り分けられるのはErlanと同じです。で、コンパイル＆ビルドすると

iex(1)> recompile
Compiling 1 file (.ex)
:ok
iex(2)> Test.perms([1,2,3])
[]

あれ、空のリストが戻ってくるよ何故だーとなったのです。すみません、私これぐらい初心者なんです…

doで何をしているか

では一体doで何してるんだーって事でデバッグ出力を入れたのが以下です。doを複数行で記述する場合、直前の，とか：を取り、なおかつ do end　で挟むように記述する必要があります。

  ##以下をtest関数の下にでも追加です。
  def perms([]), do: []
  def perms(l) do
    for h <- l,
        t <- perms(l -- [h])
    do
      IO.puts "--> h=#{h}"
      IO.inspect t
      [h|t]
    end
  end
  ##ここまで。

コンパイル＆ビルドするとこれ。

iex(3)> recompile
Compiling 1 file (.ex)
:ok
iex(4)> Test.perms([1,2,3])
[]

何もない。って事はdoに来ない？何故？

パターンマッチの再確認

Elixirの特徴であるパターンマッチはfor文にも当然適用できますし、されます。doに来ないというのはパターンが何もマッチしなかったのかもしれません。そこでforのパターンマッチの挙動自体を以下の仕様で再確認します。

  • 1000,2000,3000,4000,5000のリストを作成
  • 3000より上であれば、2倍にする計算を行う
  • 8000より上であれば、2倍にする計算を行う

結果はこれ

iex(1)> a = [1000, 2000, 3000, 4000, 5000]
[1000, 2000, 3000, 4000, 5000]
iex(2)> for x <- a, x > 3000, do: x * 2
[8000, 10000]
iex(3)> for x <- a, x > 8000, do: x * 2
[]

条件にかなわないと[]が戻るのか。となるとパターンマッチの対象外になっているのかなと。だとすると怪しいのは　def perms([]), do: [] 　かも。

空リスト時の処理を変更する

リストが空の時の処理をいじります（ここで気付よというのが恐らく普通の方の反応だと思います。私はバカなのでどうなるかなーて感じでやってました…）。とりあえず999の値入りのリストで戻してみます。

  ##以下をtest関数の下にでも追加です。
  def perms([]), do: [999]
  def perms(l) do
    for h <- l,
        t <- perms(l -- [h])
    do
      IO.puts "--> h=#{h}"
      IO.inspect t
      [h|t]
    end
  end
  ##ここまで。

コンパイル＆ビルドするとこれ。

iex(1)> recompile
Compiling 1 file (.ex)
:ok
iex(2)> Test.perms([1,2,3])
--> h=3
999
--> h=2
[3 | 999]
--> h=2
999
--> h=3
[2 | 999]
--> h=1
[2, 3 | 999]
--> h=1
[3, 2 | 999]
--> h=3
999
--> h=1
[3 | 999]
--> h=1
999
--> h=3
[1 | 999]
--> h=2
[1, 3 | 999]
--> h=2
[3, 1 | 999]
--> h=2
999
--> h=1
[2 | 999]
--> h=1
999
--> h=2
[1 | 999]
--> h=3
[1, 2 | 999]
--> h=3
[2, 1 | 999]
[
  [1, 2, 3 | 999],
  [1, 3, 2 | 999],
  [2, 1, 3 | 999],
  [2, 3, 1 | 999],
  [3, 1, 2 | 999],
  [3, 2, 1 | 999]
]

おー出てきました。デバッグで入れたIOが動いている事も確認出来ました。で結果を見ると各リストの前半は良さげですが、最後に　| 999　って出てきました何これ？

色々ググると、以下のサイトがヒット。cons演算子というものらしいです。

という知識をもって本家に行きます。

以下は本家（上記URL)からの引用です。

Similarly, we could write the list [1, 2, 3] using only such pairs (called cons cells):

[1 | [2 | [3 | []]]]
[1, 2, 3]

Some lists, called improper lists, do not have an empty list as the second element in the last cons cell:

[1 | [2 | [3 | 4]]]
[1, 2, 3 | 4]

ふーむ。どうやら[999]が不適切だという事らしいです・・・あ。

perms関数ってリストというよりはリストのリストを返す関数でしたよねそういえば・・そっか（※２）。

  • （※２）Erlang時の戻り値は[[1,2,3], [1,3,2], ...]です。

リストのリストならそれっぽくなるのかを確認

という事で、そこだけ変えてみます。後IO系はとりあえず邪魔なので取り、do含めて一行に戻してみました。それが以下のコード。[999]ではなく[[999]]にしています。

  ##以下をtest関数の下にでも追加です。
  def perms([]), do: [[999]]
  def perms(l) do
    for h <- l, t <- perms(l -- [h]), do: [h|t]
  end
  ##ここまで。

コンパイル＆ビルドするとこれ。

Compiling 1 file (.ex)
:ok
iex(2)> Test.perms([1,2,3])
[
  [1, 2, 3, 999],
  [1, 3, 2, 999],
  [2, 1, 3, 999],
  [2, 3, 1, 999],
  [3, 1, 2, 999],
  [3, 2, 1, 999]
]

思った通りで、余計な999が項目として追加されています。そうそうこれが欲しかったのですー

終わったのか？

＃いや、そのセリフはフラグだから…（何の？）

動作的に分った所で、999を削除した空のリストのリストにしてみました。これで完成な筈。

  ##以下をtest関数の下にでも追加です。
  def perms([]), do: [[]]
  def perms(l) do
    for h <- l, t <- perms(l -- [h]), do: [h|t]
  end
  ##ここまで。

コンパイル＆ビルドするとこれ。

iex(1)> recompile
:noop
iex(2)> Test.perms([1,2,3])
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

ようやく同じ結果が出せましたよー。つかここまで読む人恐らくいないですよね長々すみませんどうも…

まとめ

さて「いやー［［］］ と ［］ を間違えたんですバカでしょ僕」をどこまで長いポエムで語れるかの実験はこれで終わりです。ここまで読まれた方もしもいれば、お疲れ様でした。無駄なお時間を取らせて申し訳ありませんでした。

ライセンスなど

図ではプロ生ちゃんを使わせてもらいました。これは著作権があり以下の利用条件があります（そう厳しい物ではないのですが）。

7
1
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
7
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?