Hatena::ブログ(Diary)

エンジニアのソフトウェア的愛情 このページをアンテナに追加 RSSフィード Twitter

2014-09-28

型システムの学習に手を出します

今月は、3年ぶりになるXP祭りに参加してきました。さらに初めてとなるRubyKaigiに参加してきました。

外の、「ちょっとした身内の集まり」の規模を超えたイベントに参加したのは、2年ぶりぐらいになります。

このところ、体力低下、気力低下、意識低下、等々に悩まされていましたが、久々にイベントに参加して気がついたのは「栄養不足」でした。栄養が不足していたら、そりゃぁいろいろ低下するよね、という感想。

ただし、ストレスで食べる量が増えたせいで4kg体重が増えました。腸疾患を抱えている身としては、食べて太れるというのは実はありがたいこと。でも+4kgの体重というのは、体力のない身には厳しい。というわけで、増えたときの倍の時間はかかりましたが-3kg(元の体重から+1kg)まで到達しました。もう少し落とした方が身体の取り回しは楽そうです。


閑話休題

イベントの話は、またいずれかの機会に語りたいのですが、今回はそっちの話ではなくて。


型システム入門 プログラミング言語と型の理論

会社の同僚に「読書会やろう!」とそそのかされて、購入してきました。

数ページを斜め読みしただけですが、わくわくしてきます。こういう話題を社内でできるがうれしい。

問題はどこまで理解できるか見当もつかないところ。


アンダースタンディングコンピュテーション

時を同じくしてジュンク堂RubyKaigi店で購入したのがこちら。

流れが来ています。


しっかり笹田さんのサインも頂いてきました。

f:id:E_Mattsan:20140928205040j:image:w360


数理言語学事典

もう一つジュンク堂RubyKaigi店で購入した、事典。

考えてみると、ターゲットはどのあたりなのか、なかなか難しい書籍です。

まるで、あちこちをつまみ食いして半端な知識のわたしのために用意されたようにも思える一冊。

数理言語学事典

数理言語学事典



9月は再起動の月。

2014-08-09

いかにして表計算の列名をつくるか・特別篇

Haskellでたわむれていると。 id:nobsun さんが実に軽快な解法をコメントに残してくださいました。

colns = concat cns where cns'@(_:cns) = [""] : [[c:ns | c <- ['A'..'Z'], ns <- nss] | nss <- cns' ]

Qiita では、さらにエレガントな解を展開されていますので、ぜひそのシンプルなコードを見てみてください。


[Char] と [String] から [String]

A〜Zの並びをかけ合わせるためにわたしが取った方法は、文字列のリストのリストに sequence適用するというものでした。

Prelude> sequence [ [ "A", "B", "C" ], [ "A", "B", "C" ] ]
[["A","A"],["A","B"],["A","C"],["B","A"],["B","B"],["B","C"],["C","A"],["C","B"],["C","C"]]

(A〜Zの文字を使うと結果が大きくなってしまうため、A〜Cの文字で説明しています。以下同様)


ただし、これだと生成されるのは文字列のリストのリストになってしまいます。

そのためリストの各要素(文字列のリスト)を連結してやる必要がありました。

Prelude> map concat $ sequence [ [ "A", "B", "C" ], [ "A", "B", "C" ] ]
["AA","AB","AC","BA","BB","BC","CA","CB","CC"]

この方法をリスト内包表記で書き換えると、おおよそ次のようになります。

Prelude> [ concat [x, y] | x <- [ "A", "B", "C" ], y <- [ "A", "B", "C" ] ]
["AA","AB","AC","BA","BB","BC","CA","CB","CC"]

ここで String の連結のために concat [x, y] としていますが、xChar であれば x:y と書くことができます。

また x に文字を取り出すのであれば x <- [ "A", "B", "C" ]x <- ['A'..'C'] と書けばよいことになります。

Prelude> [ x:y | x <- ['A'..'C'], y <- [ "A", "B", "C" ] ]
["AA","AB","AC","BA","BB","BC","CA","CB","CC"]

自分の内包表記に自分を使う

y の値を取り出しているリスト [ "A", "B", "C" ] は、上の式の [ "A", "B", "C" ][""] に置き換えることで得ることができます。

 [ x:y | x <- ['A'..'C'], y <- [""] ]
["A","B","C"]

これを cns_0 と置くと、

Prelude> let cns_1 = [ x:y | x <- ['A'..'C'], y <- cns_0 ]
Prelude> cns_1
["A","B","C"]

先ほどの式を cns_2 とすると、

Prelude> let cns_2 = [ x:y | x <- ['A'..'C'], y <- cns_1 ]
Prelude> cns_2
["AA","AB","AC","BA","BB","BC","CA","CB","CC"]

となります。

cns_0 = [""] とし、f s = [ x:y | x <- ['A'..'C'], y <- s ] とすれば、

cns_0 = [""]
cns_1 = f cns_0 = ["A","B","C"]
cns_2 = f cns_1 = ["AA","AB","AC","BA","BB","BC","CA","CB","CC"]
...

となり、[ cns_1, cns_2 ] というリストを得たいばあい、f[ cns_0, cns_1 ] の要素を次々に適用して得られる値をリストにすればよいことになります。

Prelude> [ [ x:ns | x <- ['A'..'C'], ns <- nss] | nss <- [ cns_0, cns_1 ] ]
[["A","B","C"],["AA","AB","AC","BA","BB","BC","CA","CB","CC"]]

つまり [ cns_1, cns_2, ... ] というリストを得たいばあい、f[ cns_0, cns_1, ... ] の要素を次々に適用して得られる値をリストにすればよく、これはつまり得たいリストの先頭に cns_0 を付加したリストになります。

Prelude> let cns' = [""]:[ [ x:ns | x <- ['A'..'C'], ns <- nss] | nss <- cns' ]
Prelude> take 4 cns'
[[""],["A","B","C"],["AA","AB","AC","BA","BB","BC","CA","CB","CC"],["AAA","AAB","AAC","ABA","ABB","ABC","ACA","ACB","ACC","BAA","BAB","BAC","BBA","BBB","BBC","BCA","BCB","BCC","CAA","CAB","CAC","CBA","CBB","CBC","CCA","CCB","CCC"]]

このリストの要素を連結し先頭の空文字列を削除すれば、最終的に欲しかった文字列のリストが得られることになります。

Prelude> let colns = tail $ concat cns' where cns' = [""]:[ [ x:ns | x <- ['A'..'C'], ns <- nss] | nss <- cns' ]
Prelude> take 39 colns
["A","B","C","AA","AB","AC","BA","BB","BC","CA","CB","CC","AAA","AAB","AAC","ABA","ABB","ABC","ACA","ACB","ACC","BAA","BAB","BAC","BBA","BBB","BBC","BCA","BCB","BCC","CAA","CAB","CAC","CBA","CBB","CBC","CCA","CCB","CCC"]

いかにして先頭の要素を落とすか

tail 関数を使って。

Prelude> tail [1,2,3]
[2,3]

パタンマッチングを使って。

Prelude> let h:t = [1,2,3]
Prelude> h
1
Prelude> t
[2,3]

パタンマッチングを使って(元の値も使いたいとき)。

Prelude> let a@(h:t) = [1,2,3]
Prelude> h
1
Prelude> t
[2,3]
Prelude> a
[1,2,3]

2014-08-05

いかにして表計算の列名をつくるか・補遺・その補遺

おさらい。


最終形態

先日、Haskellで無限長配列を生成する例を挙げました。

再掲。

import Data.List(group)

column_names_ :: [String] -> [String]
column_names_ ss = ss ++ (map concat $ sequence [column_names_ ss, ss])

column_names :: [String]
column_names = column_names_ $ group ['A'..'Z']
drop 20 $ take 30 column_names
    -- => ["U","V","W","X","Y","Z","AA","AB","AC","AD"]

ほぼ同じ方法でRubyで書いた例も挙げました。

こんな感じ。

([*'A'..'Z'] + [*'A'..'Z'].product([*'A'..'Z']).map(&:join)).first(30).drop(20)
    # => ["U", "V", "W", "X", "Y", "Z", "AA", "AB", "AC", "AD"]


ここで。実は。Rubyのばあい、連結などということをしなくても実現できること、その後に知りました。

こんな感じ。

[*'A'..'ZZ'].first(30).drop(20)
    # => ["U", "V", "W", "X", "Y", "Z", "AA", "AB", "AC", "AD"]

演算子..メソッドsuccが定義されていれば利用できるため、加えて'Z'の次は'AA'と定義されているため、'A'から'ZZ'までを範囲として扱うことができることになるわけです。

ただ[*'A'..'ZZ']という書き方をすると、範囲を配列に変換してしまうので、小さい範囲しか必要でなくても配列全体を生成してしまいます。


これも、配列に変換せず、範囲式のまま扱うことで解決することができるのでした。

こんな感じ。

('A'..'ZZ').first(30).drop(20)
=> ["U", "V", "W", "X", "Y", "Z", "AA", "AB", "AC", "AD"]

おおざっぱな計算をすると、1桁から14桁までの文字列を利用できれば、263を表現するに充分なので、次のようなメソッドを用意すればだいたいにおいて事足りることになります。

# start 番目の文字から length 個の文字を配列として取得する
def column_names(start, length)
  ('A'..'ZZZZZZZZZZZZZZ').first(start + length).drop(start)
end
column_names(0, 10)
    # => ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J"]
column_names(20, 10)
    # => ["U", "V", "W", "X", "Y", "Z", "AA", "AB", "AC", "AD"]


結論

Rubyを使いましょう。



…そんな感じで。

2014-08-03

いかにして表計算の列名をつくるか・補遺

先日Rubyで書いたものRuby以外のメジャーどころの言語でも実装してみます。


桁上がりで1文字戻す

Ruby

再掲。

def column_names(n)
  result = ''
  begin
    result = (n % 26 + 65).chr + result
    n = n / 26 - 1
  end while n >= 0
  result
end

C++
#include <string>

std::string column_names(int n)
{
    std::string result;
    do
    {
        result = char(n % 26 + 'A') + result;
        n = n / 26 - 1;
    } while(n >= 0);
    return result;
}

Haskell
import Data.Char(chr)

reversed_column_names :: Integer -> String
reversed_column_names (-1) = []
reversed_column_names n = (chr $ fromInteger $ n `mod` 26 + 65):(column_names $ n `div` 26 - 1)

column_names :: Integer -> String
column_names = reverse.reversed_column_names

追加する文字をリストの後ろに追加していけば最後に反転する必要がなくなるのですが、文字を追加するたびに文字列を構築するよりも、一旦構築した文字列を反転する方が低コストのはずなので、このようにしています。

あと、Prologへの布石ですね。


Prolog
reversed_column_names(-1, []).
reversed_column_names(N, [R|XS]) :- R is mod(N, 26) + 65, N1 is div(N, 26) - 1, reversed_column_names(N1, XS).
column_names(N, S) :- reversed_column_names(N, S1), reverse(S1, S).

実行方法を書いておかないと(主に未来の自分が)検証ができないので、実行法をメモしておきます。

処理系には SWI-Prolog を利用しています。

$ swipl -s column_names.prolog -g 'column_names(200, S), format("~s~n", [S]), halt'
GS

-s オプションで上記のプログラムを保存したファイルのファイル名を指定します。

-g オプションでゴールを指定します。

column_names(200, S)を実行しただけでは結果が出力されないので、format("~s~n", [S])で結果を表示しています。format/2の書式はこちらを参照してください。

haltを指定することで、実行後にコマンドを終了させています。終了させないとプログラムの実行後に SWI-Prolog のプロンプトが表示されます。


やっぱりみんな大好き、直積

Ruby

再掲。

AtoZ = [*?A..?Z]
column_names = AtoZ + AtoZ.product(AtoZ).map(&:join) + AtoZ.product(AtoZ).product(AtoZ).map(&:join)

この例では3桁までの文字列しか生成していませんが、無限に続くばあいの扱いに長けた言語があるので、それで実装してみます。


Haskell

A〜Z の並びを A とし、直積を×で、文字列の並びの連結を+で表すと、列名の配列 column_names は次のようになります。

column_names = A + A × A + A × A × A + …

これを次のように変形します。

column_names = A + (A + A × A + … ) × A

すると括弧の中が column_names になるので、つまり次のように書くことができます。

column_names = A + column_names × A

これを実装すると。こんな感じになりました。

import Data.List(group)

column_names_ :: [String] -> [String]
column_names_ ss = ss ++ (map concat $ sequence [column_names_ ss, ss])

column_names :: [String]
column_names = column_names_ $ group ['A'..'Z']

A〜Z の並びを作るために group を使っているところとか、map concat とかがいまいちあか抜けない感じですが、一応目指すやり方で実装することができました。

(2014/08/05 修正: sequence [column_names_ ss, ss]とすべきところがsequence [column_names, ss]となっていました)

2014-08-01

いかにして表計算の列名をつくるか

「列名って、なに?」

これです。このA, B, ..., Z, AA, AB, ... という文字列です。

f:id:E_Mattsan:20140801195504p:image

仕事でちょっとゴルフネタ的ななにかになったので、記録しておきます。


みんな大好き、直積

列名は最初は1桁の A〜Z の26個、次に2桁の AA〜ZZ の676個、次に3桁の AAA〜ZZZ の17,576個、…と続きます。

AA〜ZZ の並びは A〜Z と A〜Z との直積で得られます。Ruby では product メソッドを使います。

AAA〜ZZZ の並びも同様に AA〜ZZ と A〜Z との直積で求めることができます。

これをふまえて。文字列配列を一挙に作ってしまおうという作戦。


実装。

AtoZ = [*?A..?Z]
column_names = AtoZ + AtoZ.product(AtoZ).map(&:join) + AtoZ.product(AtoZ).product(AtoZ).map(&:join)

column_names[200] # => "GS"

3桁あれば18,278列までまかなえるので充分なのですが、この数を配列で用意しておくと、メモリ効率がよくない感じ。



桁上がりで1文字戻す

特定の番号の列名が欲しいとき、上記のように配列に用意しておいた値を引くという手もありますが、できれば算出してしまいたいもの。

26文字を使うので一瞬26進数のように錯覚したのですが、そうではありません。

これは 0〜9 の文字を使うとわかりやすくなると思います。

0, 1, ..., 8, 9, 00, 01, 02, ..., 98, 99, 000, ...

つまり

1桁のばあい: 0〜9

2桁のばあい: 00〜99

3桁のばあい: 000〜999

という並びになることになります。

9の次が10でなく00になるようにするためには、桁上がりがおこったときに、桁上がりした桁の値を1小さくしてやる必要があります。


実装。

def column_names(n)
  result = ''
  begin
    result = (n % 26 + 65).chr + result
    n = n / 26 - 1
  end while n >= 0
  result
end


回さない方法はないのか

ループでぐるぐる回すのがRubyっぽくないと、その後丸1日ぐらい考え続けていました。

もう一度、値と桁数の関係を考えてみると、

0〜25: 1桁の26進数

26〜701: 2桁の26進数

701〜18,277: 3桁の26進数

という関係になっていることがわかります。

つまり、たとえば200であれば2桁になるので、26を引いて26進数変換すればもとめる文字列になりそうです。

irb> (200 - 26).to_s(26)
=> "6i"

はい、なりません。

これは考え方がまずいのではなく、使う文字の問題です。

各桁の値を表す文字が 0〜9 および a〜z となっているため、7番目の文字が G ではなく 6 に、18番目の文字が S でなく i になるためです。

ですので文字 A で下駄を履かせることで期待する文字が得られることになります。

irb> ((200 - 26).to_s(26)[0].to_i(26) + 'A'.ord).chr
=> "G"
irb> ((200 - 26).to_s(26)[1].to_i(26) + 'A'.ord).chr
=> "S"

桁ごとに下駄を履かせるのは面倒なので、26進数で文字列にしたものを一旦36進数として解釈し、各桁の下駄の値を足し合わせた値を加えて36進数として文字列に変換します。

最後に、列名は大文字で欲しいのでupcaseメソッドで大文字にしています。

irb> ((200 - 26).to_s(26).to_i(36) + 'AA'.to_i(36)).to_s(36).upcase
=> "GS"

そうすると最後に残るのが桁数の取得です。

1桁で表せる列名の数: 26

2桁以内で表せる列名の数: 1桁で表せる列名の数 + 2桁で表せる列名の数 = 26 + 262 = 702

3桁以内で表せる列名の数: 1桁で表せる列名の数 + 2桁で表せる列名の数 + 3桁で表せる列名の数 = 26 + 262 + 263 = 18,278

途中省略

n桁以内で表せる列名の数: 26 * (26n - 1) / (26 - 1)

ここから式を変形して、列の番号 m から次の式で桁数 n を取得することができるようになります。

floor(log26(25 * m + 26))

ここで floor は床関数です。


これらをふまえて。実装。

def column_names(n)
  c = Math.log(25 * n + 26, 26).floor
  ((n - 26 * (26**(c - 1) - 1) / 25).to_s(26).to_i(36) + ('A' * c).to_i(36)).to_s(36).upcase
end

26進数変換と36進数変換を3回やっていて効率が悪そうに見えますが…気にしてはいけません。


それ succ でできるよ

Ruby には「次の値」を返すsuccという便利なメソッドがあります。

1.succ # => 2 : 数値 1 の次の値
'1'.succ # => '2' : 文字列 '1' の次の値
'A'.succ # => 'B' : 文字列 'A' の次の値

三村さんに指摘されて知ったのですが、'Z'の次の値というのが:

'Z'.succ # => 'AA' : 文字列 'Z' の次の値
'ZZ'.succ # => 'AAA' : 文字列 'ZZ' の次の値

200番目の列名を取得したいときは200回succすれば求めたい値になります。

irb> 200.times.inject('A') {|c| c.succ }
=> "GS"

名前を求めるたびに何回もsuccするのは効率が悪そうですが、普通は列名は連続して生成するばあいが多いと思います。そのばあい、succで進めるたびに値を取り出すようにすれば、効率もよくなりそうです。





…。



結論

succ メソッドを使うといいと思うよ!