2008年6月26日木曜日

Haskell で リストの n 番目の要素を取得 – PreludeList の (!!)

1. リストの n 番目の要素を取得する関数を定義してみる

Haskell でリストの n 番目の要素を取得するには、どうしたらいいんだろ?

例えば、

["hoge", "piyo", "hoge"]

というリストから、2番目の要素である "piyo" を取り出すことを考える。

 

take, reverse, head 関数を使って

これまで使ったことのある関数で、定義してみる。

Prelude> head $ reverse $ take 2 ["hoge", "piyo", "fuga"] 
"piyo"

  1. 取り出したい要素を、リストの末尾に来るようにして、
  2. リストを反転、
  3. リストの先頭の要素を取得。

というやり方はちょっと面倒 ^^;

 

zip, lookup 関数を使って

モナドのところで出てきた lookup 関数を使って定義してみる。

Prelude> lookup 2 $ zip [1..] ["hoge", "piyo", "fuga"]
Just "piyo"

  1. zip 関数で、リストに対して、インデックスを付け、
  2. lookup 関数で探す。

先ほどよりは、幾分ましになった。しかし、こんな基本的な操作は、違う書き方があるはず。

ふつうのHaskellプログラミング によると、

すべてのモジュールは暗黙のうちに Prelude モジュールをインポートしており、 import 宣言をまったく書かなくとも Prelude モジュールで定義された関数が使えます。(p251)

ということは、Prelude に何か定義してあるだろうか。 (@_@)

 

2. PreludeList の (!!) 演算子

The Haskell 98 Report: Standard Prelude によると、

プレリュードはひとつのルートモジュール Prelude  と 3つのサブモジュール PreludeList、PreludeText お よび PreludeIO で組織されている。

Prelude を見ると List operations のところに、

(!!) :: [a] -> Int -> a

List index (subscript) operator, starting from 0. It is an instance of the more general genericIndex, which takes an index of any integral type.

と書かれている。これだ!

Prelude> ["hoge", "piyo", "fuga"] !! 1
"piyo"

「!」 はふつうのHaskellプログラミング (p181) の二項演算子に使える文字に含まれている。

ちなみに、リストの範囲を超えたインデックスを指定すると、エラーが表示される。

Prelude> ["hoge", "piyo", "fuga"] !! 3
"*** Exception: Prelude.(!!): index too large

定義を見ると、再帰的な定義がされていた。

xs     !! n | n < 0 =  error "Prelude.!!: negative index"
[]     !! _         =  error "Prelude.!!: index too large"
(x:_)  !! 0         =  x
(_:xs) !! n         =  xs !! (n-1)

 

3. ついでに、リスト操作の基本を学ぶ

List operations を見ると、Reducing lists, Building lists ... という分類があり、たくさんの操作が定義されている。とりあえずは List operations の最初に出てきているところだけを押さえておこう。

いつもながら、自分なりに、適当に分類してみる。

  • (++) , (!!) , length, null
  • head , last , init , tail
  • reverse
  • map ,  filter

これらの関数を早速試してみる。

Prelude> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]

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

Prelude> length [1,2,3]
3

Prelude> null [1,2,3]
False
Prelude> null []
True


Prelude> head [1,2,3]
1
Prelude> last [1,2,3]
3

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


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


Prelude> map (+1) [1,2,3]
[2,3,4]
Prelude> filter (>1) [1,2,3]
[2,3]