リストと文字列は兄弟 ?
以前に引用したように、Haskell においては「文字列 = 文字のリスト」。
実は、 Haskell では文字列もリストなのです。文字列は文字のリストとして表現されていて、特別な文字列は存在しません。ですから、リストの処理を覚えてしまえば文字列処理も身についたことになります。 (ふつうのHaskellプログラミング, p.36)
ということを読んでいなければ、多分、ずっと気がつかずにいたかもしれない。 ^^; Python においても、文字列とリストが上位にシーケンス型をいただいていることにより、同じように考えることができる。前回の例において、文字列をリストと同じように扱えたのは、同じシーケンス型だからという理由による。
(とか言いつつ、最近までこのことを理解しているとは言い難いコードを書いていた。むしろ、ドキュメントを読んでいないことがバレバレな…。)
多くのデータ構造は速度のために存在する。例えば、現代の言語の多くは文字列とリストを持っている。意味的には、文字列は、全ての要素が文字であるというリストであって、一般的なリストのサブセットと言える。ならどうして別のデータタイプが必要なんだろう。実は必要じゃないんだ。文字列は単に効率のためだけに存在している。けれど、プログラムを速く走らせるハックのためだけに言語に意味をごてごてと付け足すなんて、スマートじゃない。
(太字は引用者による)
ということより、リストと文字列は兄弟というよりも主従関係 (？) か。
Haskell でリストを操作する関数を文字列に適用 - tails 関数
例えば、Haskell には Data.List.tails という関数がある。
tails 関数は、リストxsそのもの、リストxsの第2要素以降、リストxsの第3要素以降、……をリストにして返します。
(ふつうのHaskellプログラミング , p95)
以下を実行すると、
import Data.List main = do print $ tails "hoge" print $ tails [1,2,3]
結果は、
["hoge","oge","ge","e",""] [[1,2,3],[2,3],[3],[]]
文字列が特別なものではないことがわかる。
tails 関数 の実装方法
tails 関数は再帰的に書けそうなので、要素が空の状態から徐々に要素を増やし、例を挙げながら考えた。
- 空のリスト[] → [[]]
- 要素一つ [1] → [[1], []]
- 要素二つ [1,2] → [[1,2], [2], []]
- 要素三つ [1,2,3] → [[1,2,3], [2,3], [3], []]
- 要素四つ [1,2,3,4] → [[1,2,3,4], [2,3,4], [3,4], [4], []]
ここまで書いてやっと気がついた。 (@_@) 例えば、要素 4 つの場合であれば、先頭の要素は与えられたリスト。2 番目以降の要素は、[2,3,4] に tails 関数を適用したものであることがわかる。つまり、
L[0] + tails(L[1:])
Python で tails 関数を実装
リストで考える
上記に相当するものを Python で実装するとして、これまでなら次のように書いていた。
def tails(L):
if L == []: return [L]
else:
return [L] + tails(L[1:])
しかし、これでは以下を実行したとき、文字列に適用した再帰呼出しが延々と続いてしまう。 (@_@;)
print tails([1,2,3])
print tails("hoge")
しかし、これは当り前で、例えば、
print "hoge"[4:]
の呼出しは`空文字’となり、
print "hoge"[4:] == []
は False となるため。
文字列も扱えるように
文字列も扱えるようにするためには、判定を次のように変更する必要がある。
def tails(L):
if not L: return [L]
else:
return [L] + tails(L[1:])
これは、2.3.1 真値テスト によると、if において、次のものは偽であると見なされるため。
… 空のシーケンス型。例えば
''、()、[]。 …
以前、if L == [] と if not L のどちらを使うのがいいのか迷ったとき、 if L == [] の方が 「もし L が空のとき」 と自然に読めたので、そちらを使っていた。しかし、これではリストの型に固定された判定となってしまう。せっかく Python ではリストと文字列を透過的に扱うためにシーケンス型を導入してくれているのに、全く活用していなかった。「空のシーケンス型」という言葉を頭に入れておかなければいけない。 (+_+)
しかし、この記述直観的に理解しにくいので、反対の `if L’ を「リスト (シーケンス) に要素がある場合」と覚え、それを逆にして、`if not L’ を「リストに要素がない場合」として覚えることにした。
Ruby による tails 関数の実装
Ruby は、 Python とは if における真偽判定が異なるので注意が必要。制御構造 - Rubyリファレンスマニュアル によると、
Ruby では
falseまたはnilだけが偽で、それ以外は 0 や空文字列も含め全て真です。
つまり、先ほどの Python と同じように書いたとしても、
list = [] if not list p 'if' else p 'else' end
結果は else と表示される。 配列や文字列の場合 empty? メソッドを使う必要がある。
実装例 (1)
まずは上記の Python の真似をして配列で実装してみる。
def tails(list)
if list.empty?
[list]
else
[list] + tails(list[1..list.size])
end
end
p tails([1,2,3])
p tails("hoge".split(//)).map{|e| e.join}
しかし、これでは文字列の場合、split メソッド で一文字ごとの配列に分割し、関数を適用した後で、また join メソッド でつなげないといけない。 tails 関数の引数が配列であるとした場合、文字列は配列に変換する必要がある。
実装例 (2)
なんとかして文字列と配列を透過的に扱えないかと考えたところ、両クラスとも Enumerable モジュールをインクルードしていたのを思い出した。そして、 Ruby では組込みのクラスであっても変更して使うことができる。(これをオープンクラスという言う。 cf. 「オープンクラスとRuby on Rails」 昔、「たのしいRuby
実装の方針は、まず文字列と配列の共通の Enumerable モジュールに tails メソッドを追加。この中で文字列・配列に対して次の二つのメソッドを呼ぶ。
- tail : 文字列であれば、先頭の文字を除いた文字を返す。配列であれば、先頭の要素を除いた要素を返す。
- empty : 空であることを表わすものを返す。文字列であれば “” 空文字。配列であれば [] 空のリスト。
module Enumerable
def tails
if self.empty?
[self.empty]
else
[self] + self.tail.tails
end
end
end
class Array
def tail
result = []
self.each_with_index{|e,i| result << e unless i == 0}
result
end
def empty
[]
end
end
class String
def tail
result = ""
self.split(//).each_with_index{|e,i| result += e unless i == 0}
result
end
def empty
""
end
end
p [1,2,3].tails
p "hoge".tails
0コメント:
コメントを投稿