Haskell の Prelude 散策 (2) - 述語 | すぐに忘れる脳みそのためのメモ

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

1. 述語とは、主語に関する「何かを表す」部分

前回は、リスト操作の一部を試した。今回は、Prelude を読んでいたときに見かけた、

predicate (述語)

について調べる。

「述語」と言えば、小学校の国語の時間に習った「主語」と「述語」思い出す。「ことばのきまり」という授業あったけれど、嫌いだったなぁ。 ^^;

述語 – Wikipedia によると、

言語学において文や節の中心をになう成分のこと。他の名詞句に関する何かを表わす部分である。

例えば

私は日本人です。

という文の場合、主語である「私」に関する `何かを表わす部分’ というが「日本人です」に相当する。

2. Prelude のドキュメントに書かれている「述語」

さて、Prelude のドキュメントにおいて、関数の説明に `predicate’ という言葉が使われていた関数は以下の 7 つ。

filter :: (a -> Bool) -> [a] -> [a]
any :: (a -> Bool) -> [a] -> Bool
all :: (a -> Bool) -> [a] -> Bool
takeWhile :: (a -> Bool) -> [a] -> [a]
span :: (a -> Bool) -> [a] -> ([a], [a])
break :: (a -> Bool) -> [a] -> ([a], [a])

filter 関数における述語

上記の関数の、どこが述語なのだろう？

例えば filter 関数のドキュメントには次のように書かれている。

filter, applied to a predicate and a list,…

「filter は述語とリストに適用され…」とあることより、filter 関数の第1引数が述語に相当する。

つまり、型としては

(a -> Bool)

を指し示している。

filter 関数は、例えば次にようにして使う。

*Main> filter (> 3) [1..5]
[4,5]

第1引数の型を調べると、

*Main> :t (> 3)
(> 3) :: (Ord a, Num a) => a -> Bool

この場合、filter の対象であるリストの要素が数なので、第１引数の型、型変数 `a’ は数でかつ比較可能なものでなければならないという制約が付いている。上記のドキュメントにあった通り

a –> Bool

という型の関数であることがわかる。つまり、これが述語。リストの要素が、どのような性質のものであるかを示す。

上記のセクションで書いてあるものを、無名関数を使って書くなら、

 \x -> x > 3

引数 x に数を与えると真偽が定まる。(Bool 型が返される。)

3. 述語論理の「述語」

情報の論理数学入門―
ブール代数から述語論理まで

「情報の論理数学入門」の「述語論理」によると、

… 「太陽は西に沈む」は、「沈む」という関係が「太陽」と「西」を結び付けているとみることができる。また、… 「6 は素数である」は、「素数」とう性質が「6」にあることを表わしている。

この「沈む」や「素数」のようにある関係や性質を表すものを述語 (predicate) とよび、「太陽」や「西」、「6」のようにその対象となっているものを項 (term) という。

述語は命題論理と同じく真偽の 2 値をとる。項は述語の引数となる。

(太字は引用者による、p127)

重要なのは、述語が「関係や性質を表わすもの」であり、「真偽の 2 値をとる」ということ。

先ほどの filter 関数の例で考えるなら、「x は 3 より大きい」というのが述語で性質を示しており、第2引数であるリストの要素が具体的に x に代入されることによって真偽が定まる。

項として、特定の値が与えられているものを個体定数 (individual constant) と言い、「任意の個体定数を代表する変数を個体変数 (individual variable) 」(p128) と呼ぶ。上例の場合、「x は 3 より大きい」の x が個体変数ということか。

4. Ruby の述語

ところで、Ruby にはメソッドの接尾辞に

?

が付いているものがある。

メソッド呼び出し - Rubyリファレンスマニュアルによると、

メソッド名には通常の識別子の他、識別子に ? または ! の続いたものが許されます。慣習として、述語(真偽値を返すメソッド)には ? を、同名の(! の無い)メソッドに比べてより破壊的な作用をもつメソッド(例: tr と tr!)には ! をつけるようになっています。

(太字は引用者による)

真偽値を返すメソッドが、述語だと述べられている。

Enumerable モジュールを見ると、以下のメソッドに `?’ がついている。

all?
any?
member?, include?

例えば、次の式は全て true を返す。

p (1..10).all?{|x| x > 0}
p (1..10).any?{|x| x > 9}
p (1..10).include?(3)

5. Emacs Lisp の述語

Emacs Lisp プログラミングの「1.8.4 引数に誤った型のオブジェクトを指定」でも同様に、

number-or-marker-pの`p'は、 Lispプログラミングの早い時期に始まった慣習である。 `p'は「述語（predicate）」の略である。初期のLisp研究者が用いた専門用語では、 述語とはある性質が真か偽か調べる関数を意味する。したがって、`p'があることで、number-or-marker-pは、与えられた引数が数であるかマーカーであるかの真偽を調べる関数の名前であることがわかる。

(太字は引用者による)

試してみる。

(number-or-marker-p 10)
t
(number-or-marker-p "hoge")
nil
(number-or-marker-p '(1 2 3))
nil

Lispでは、nilは「偽（false）」をも意味し、空リスト()の同義語でもある）

(2.1 バッファ名より)

6. Haskell の takeWhile, span, break 関数

Haskell に戻り、takeWhile, span, break, elem 関数を試しておく。

最初の 3 つは前回見たリスト操作の区分で言うと、リストの部分 (Sublists) を取得する操作に該当する。

まずは takeWhile から。これは対象のリストを先頭から見ていき、述語が真である内は返すが、偽となったら、はい、それまでよ。

  print $ takeWhile (< 5) [1..10]    -- [1,2,3,4]
  print $ takeWhile (> 3) [1..10]    -- []

二つ目の式は、リストの先頭から述語が偽となってしまうので空のリストが返される。

span もリストの先頭要素から見ていき、述語を満す要素のリストと、そうでない要素のリストの分けて、タプルにして返す。

  print $ span (< 3) [1..10]         -- ([1,2],[3,4,5,6,7,8,9,10])
  print $ span (> 3) [1..10]         -- ([],[1,2,3,4,5,6,7,8,9,10])

気を付ける点は、2 つ目の式は、リストの先頭要素が述語を満さいないため、返されるタプルの第１要素が空の要素になるということ。

break は span の反対で、同様にリストの先頭から見ていき、述語を満さない要素のリストと、それよりも後ろにあるリストの要素に分けてタプルにして返す。

  print $ break (== 5) [1..10]       -- ([1,2,3,4],[5,6,7,8,9,10])
  print $ break (> 5) [1..10]        -- ([1,2,3,4,5],[6,7,8,9,10])
  print $ break (< 5) [1..10]        -- ([],[1,2,3,4,5,6,7,8,9,10])

これも先ほどと同様に、3 つ目の式は、リストの先頭要素が述語を満してしまうので、タプルの第１要素は空のリストになる。

7. Prelude にある a –> Bool を引数に持つ関数

先ほど述べたように、predicate とドキュメントに書かれていたのが、上記 7 つの関数だった。

しかし、

a –> Bool

という型を、その関数に持つものは、他にも Prelude に存在する。

Eq、Ord クラスにある、比較のためのメソッド。
RealFloat クラスの isXXXX という形式のメソッド。
odd 関数。

takeWhile の逆の動作をする、

dropWhile :: (a -> Bool) -> [a] -> [a]

  print $ dropWhile (< 5) [1..10]    -- [5,6,7,8,9,10]
  print $ dropWhile (> 3) [1..10]    -- [1,2,3,4,5,6,7,8,9,10]

二つ目の式において、述語はリストの先頭要素において偽になるので、そこで終了。

until 関数は、第１引数が述語、第2引数が関数、そして第3引数が対象の型変数 a 。対象に対する述語が真になるまで、関数の適用が繰り返され、述語が真となったときの値が返される。

until :: (a -> Bool) -> (a -> a) -> a –> a

  print $ until (> 100) (* 2) 5      -- 160

この場合、最初に 5 という数値があり、これを 2 倍することを繰り返すと、5, 10, 20, 40, 80, 160 となり、160 の時点で述語「160 は 100 よりも大きい」が真となるので、このときの値が返される。

ところで、until 関数のドキュメントには次のように書かれている。

until p f yields the result of applying f until p holds.

関数は慣習的に f と書かれるが、述語は `p’ と表現されるようだ。

8. 高階述語 (higher order predicate)

情報の論理数学入門―
ブール代数から述語論理まで

「情報の論理数学入門」によると、

項は一般に述語であってもよい。変数が述語を表わすとき、それを述語変数 (predicate variable)という。引数に述語を含まない述語を第１階述語 (first order predicate) という。(p129)

上記の例で試した、引数における述語の項は、全て特定の値だった。つまり、第１階述語。

述語の引数に 1 つでも第１階述語があればそれは第２階述語である。一般に、引数に (n-1) 階述語があればその述語を第 n 階述語という (n >=2)。 2 階以上の述語を高階述語 (higher order predicate) という。

(同上より)

universal quantifier や existential quantifier との関係はどうなんだろうか…。段々目が回ってきた。(@_@;)

パタッ(o_ _)ｏ~†

すぐに忘れる脳みそのためのメモ

2008年12月7日日曜日