2008年10月7日火曜日

Haskell の Prelude 散策 (1) - リスト操作 : 要素の重ね合わせ (folds)

1. Prelude の意味

Haskell のコードを読めるようになるためには、基本となる Prelude を押さえる必要がある。

ところで、Prelude の意味は、

1 (出来事などの)前ぶれ, 前兆((to ...))
2 (…の)準備行為, 前口上((to ...))
3 《楽》前奏曲, プレリュード.

Yahoo!辞書 – prelude より)

Prelude は、Haskell のコードを書けば自動的に import される。自分の実行したいコードの前に奏でられる「前奏曲」と覚えておけばいいのかな。

Prelude is a module that contains a small set of standard definitions and is included automatically into all Haskell modules.

(Prelude - HaskellWiki より)

ちなみに、前奏曲 - Wikipedia とは、

(他の楽曲の・大規模な楽曲の)前に演奏する楽曲の意味である。

 

2. Prelude の区分

Prelude が、どのような構成になっているか、見てみると、

Standard types, classes and related functions
List operations
Converting to and from String
Basic Input and output
  1. 基本的な型、クラスと、それに関連した関数
  2. リスト操作
  3. 文字列の変換
  4. 基本的な入出力

2 番目の「リスト操作」については、これまでに関数をいくつか試した。

 

Prelude を構成するモジュール

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

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

よって、先ほど列挙した  Prelude の構成の項目は、以下と対応している。

  1. ルートモジュール
  2. PreludeList
  3. PreludeText
  4. PreludeIO

 

3. リスト操作の基本

最初に、リストの基本的な操作 を、自分なりに分類しておく。

 

4. リスト操作の分類

Prelude にある、リストに対する、基本的な操作以外の分類を見てみる。

  1. 要素の重ね合わせ (要素をまとめる) : fold, 特殊なタイプ
  2. 生成 : scan (fold のリスト版)、繰り返し
  3. 部分 : take, drop
  4. 検索 : elem, lookup
  5. リスト同士のすりあわせ : zip
  6. 文字列と文字列のリスト : lines, words

今回は、 1 番目の「要素の重ねあわせ」について、試してみる。

 

5. リスト要素の重ね合わせ

「リストの要素の重ね合わせ」とは、リストから要素を取り出し、関数 f を適用しながら、要素を重ね合せていくイメージ。リストの内容を、一つの要素にまとめていく機能を持つ。

081007-001

具体的には、「リストの要素を合計する操作」などを思い浮かべるのがよい。

Haskell では、これに対応する関数名は foldl , foldr

追記 (2011.11.30) : この記事を書いたときに、意識してなかったことは、以下を参照。

 

操作の種類と例

リストの要素を、先頭(左)から重ねあわせていく方法と、末尾(右)から重ね合わせる方法の  2 つが定義されている。

  • foldl : リストの左から重ね合わせる
  • foldr : 右から重ね合わせる

先ほどの図中において、ピンク色がついている要素が「初期値」を表わすと考える。

初期値のないものが、それぞれ `foldl1, foldr1

foldl : 左から重ねる

main = do 
  print $ foldl (\x y -> x + y) 0 [1,2,3,4,5]  -- 15
  print $ foldl (+) 0 [1,2,3,4,5]              -- 15
  print $ foldl (-) 10 [1,2,3,4,5]             -- -5

foldr : 右から重ねる

main = do 
  -- 1-10
  print $ foldr (-) 10 [1]          -- -9
  -- 1-(2-10))
  print $ foldr (-) 10 [1,2]        -- 9
  -- 1-(2-(3-(4-(5-10))))
  print $ foldr (-) 10 [1,2,3,4,5]  -- -7

foldl1, foldr1 : 初期値なし

main = do 
  print $ foldl1 (+) [1,2,3,4,5]  -- 15
  -- 1-(2-(3-(4-5)))
  print $ foldr1 (-) [1,2,3,4,5]  -- 3

 

6. 特殊な重ね合わせ

上記の「重ね合わせ・まとめあげ」をする関数から導かれる、特殊な関数。

sum, product, maximum, minimum : 総和、総乗、最大、最小

main = do 
  print $ sum [1,2,3,4,5]      -- 15
  print $ product [1,2,3,4,5]  -- 120
  print $ maximum [1,2,3,4,5]  -- 5
  print $ minimum [1,2,3,4,5]  -- 1

any, all : 要素の存否

main = do 
  print $ any (==3) [1,2,3,4,5]           -- True
  print $ any (>3) [1,2,3,4,5]            -- True
  print $ any (\x -> x > 30) [1,2,3,4,5]  -- False

  print $ all (>=1) [1,2,3,4,5]           -- True

一つ括弧をはずす : concat, concatMap

concatMap は、map して concat

main = do 
  print $ concat [[1,2,3],[4,5,6],[7,8,9]]  -- [1,2,3,4,5,6,7,8,9]
  print $ concat [[[1,2]],[[3,4]],[[5,6]]]  -- [[1,2],[3,4],[5,6]]
  print $ concat ["hoge", "piyo"]           -- "hogepiyo"

  print $ map (:['!']) ['a','b','c']        -- ["a!","b!","c!"]
  print $ concatMap (:['!']) ['a','b','c']  -- "a!b!c!"
  print $ map ('*':) ["hoge", "piyo"]       -- ["*hoge","*piyo"]
  print $ concatMap ('*':) ["hoge", "piyo"] -- "*hoge*piyo"

and, or  は何にどう使えばいいだろう?(@_@) QQQ

main = do 
  print $ and [True, False, True]  -- False
  print $ and [True, True, True]   -- True
  print $ and $ map (>3) [4,5,6]   -- True
  print $ and $ map (>3) [3,4,5,6] -- False
  print $ or $ [x>3 | x <- [4,5,6]] -- True 
  print $ or $ [x>3 | x <- [1,2,3]] – False

 

7. 関連記事