代数プログラミング入門 Ch4 関数

1 関数

Haskellは関数型言語なので,関数の記述がプログラミングにおける花形です. この章ではHaskellの関数に関する記法を学びましょう.

1.1 関数と演算子

関数型言語では関数を組み合わせてプログラムを書きます. 関数の正確な定義は後に譲るとして,ここでは取り敢えず｢特定のデータ型の値を受け取って,特定のデータ型の値を返すもの｣という定義にしましょう.このとき受け取る値を引数,返す値を返り値といいます.

Haskellでは,数学の記法と非常に近い方法で関数を定義します. 例えば,

f : \mathbb{Z} \rightarrow \mathbb{Z} \\ f(x) = x + 1

という,整数xを受け取って整数x + 1を返すだけの関数について考えましょう.

Haskellでは上の関数は以下のように定義されます.

f :: Int -> Int
f x = x + 1

main = do
    print $ f 4 --  5

()の代わりにスペースを使う点以外は全く同じ書き方で, =の左側に関数名と引数,右側に返り値を書きます. 関数名は小文字の英字で始めるというルールがあります.

f :: Int -> Intは型注釈であり,このfという関数が,引数にIntを取り,返り値としてIntを返すということを指定しています. 型注釈は高度な処理をしない限り省略しても自動的にGHCが推論してくれますが,可読性のためにもできるだけ書くようにしましょう.

do以下の記述で, f 4の結果を確認しています. printは,文字列に変換可能な値を受け取り,標準出力する関数です. また (f 4)を省略して$ f 4 としています.

引数は何個でも利用できます. 例えば2引数関数

multiple(x,y) = x * y

は以下のように定義できます.

multiple :: Double -> Double -> Double
multiple x y = x * y
multiple 3 4

main = do
    print $ multiple 3 4 --  12.0

また,以下の記号を組み合わせて中置演算子名として利用することも可能です.

(.*) :: Double -> Double -> Double
x .* y = x * y

main = do
    print $ 3 .* 4 --  12.0

絵文字などのUnicode記号も利用することができます.

(✖) :: Double -> Double -> Double
x ✖ y = x * y

main = do
    print $ 3 ✖ 4 --  12.0

記号を利用して関数を定義する場合には,定義時に() で囲うことで一般の関数のように定義することができます. 例えば, 乗算を新たに定義するとして,以下のように書くことができます.

(.*) :: Int -> Int -> Int
(.*) x y = x * y
main = do
    print $ 3 .* 4 --  12

前置の2引数関数も`` (バッククオート)で囲むことで中置演算子として定義することができます.

x `multiple` y = x * y

main = do
    print $ 3 `multiple ` 4 --  12

1.1.1 結合性

先に述べたように異なる複数の演算子が連なっている式は, 演算子の優先順位に従って計算される順位が変わります.

例えば,* の優先順位は7で, + の優先順位は6なので,2 * 3 + 3 という式は,

   2 * 3  + 3
= (2 * 3) + 3
= 6 + 3
= 9

と言う風に*が優先して計算されます.

では,同じ演算子が複数回連なっている場合にはどのような順序で計算されるのでしょうか? このルールを決めるのが 結合性(Associativity) です.

ユーザーが作成した演算子の結合性を指定するには,右,左,非の順にinfixr,infixl,infix宣言を利用します. いずれも, infix(r/l/なし) 優先順位 記号 の順に書きます.

例えば先程作成した,.* を右結合の優先順位7で指定するには,以下のように書きます.

x .* y = x * y
infixr 7 .*

1.2 カリー化,部分適用

Haskellでは多引数関数を実装できることは先程確認しました. しかし,Haskellはすべての関数が,引数を一つだけとるという原則があります. これは,矛盾するようですが,この矛盾を解消する概念がカリー化(Currying)です.

カリー化とは複数引数関数に対して,｢一つの引数を取り,次に残りの引数を取る関数を返すようにする変換｣です.

例として,以下のxとyを受け取りその和を返す関数addは

add :: Int -> Int -> Int
add x y = x + y

実際には

add :: Int -> (Int -> Int)

として機能しています. 関数の呼び出しは左結合なので,

add 5 10 = (add 5) 10 であり, ここで(add 5) :: Int -> Intという新たな関数に2が適用されています.

ghci> :{
ghci| add :: Int -> Int -> Int
ghci| add x y = x + y
ghci| :}
ghci> :t add
add :: Int -> Int -> Int
ghci> :t (add 5)
(add 5) :: Int -> Int

Haskellでは,標準で全ての関数がカリー化されており,これによって関数の複数の引数のうち一部だけを与えて,残りの引数を持つ関数を生成する部分適用(Partial Application)が可能となっています.

-- add関数を利用した部分適用
add5 :: Int -> Int
add5 = add 5

-- 実際の利用例
result = add5 10

1.3 分岐

関数型言語において,手続き型言語におけるIF文に相当するのがパターンマッチと指示関数(特性関数)です.

1.3.1 パターンマッチ

パターンマッチに近い概念は既にフィボナッチ数の漸化式として出てきています.フィボナッチ数の漸化式は,以下のように表されます.

この関数はPythonでは,以下のようにif文による分岐で記述されるのが一般的です.

def fib(x):
    if x == 0:
        return 1
    elif x == 1:
        return 1
    else:
        return fib(x-1) + f(x-2)

これをHaskellでパターンマッチを利用して以下のように定義することができます.

fib :: Int -> Int
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

このHaskellのコードは,

• 関数fibの引数が0のときには返り値として1を返し,

• 関数fibの引数が1のときには返り値として1を返し,

• 関数fibの引数がそれ以外のときには返り値としてfib (n - 1) + fib (n - 2)を返します.

この最後のfib n = fib (n - 1) + fib (n - 2)は再帰関数といって後ほど扱いますが,取り敢えず,特定の引数に対して特定の返り値を指定するこのような関数の記述方法をパターンマッチといいます.

パターンマッチは,数値以外の引数に関しても適用可能であり,リストではリストの要素数に応じて使い分けることが多いです.

以下の,strHead関数は,リストの先頭の要素を文字列として表示する関数です.リストが空のときには"Empty",要素が一つのときにはその要素,それ以外のときには先頭の要素を文字列にして返します.

showの詳細は後ほど扱いますが,どの様に標準出力に表示するかを定めてあるデータ型を文字列に変換する関数です.

strHead :: Show a => [a] -> String
strHead []     = "Empty"
strHead [x]    = show x
strHead (x:xs) = show x

main = do
    print $ strHead [] --  "Empty"
    print $ strHead [3,4] --  "3"

パターンマッチはこのようにリストx:xsの先頭部分xを指定するなどの利用法が可能です. 値の特定の部分を取得する用法として頻出なのがタプルを引数に取るパターンマッチです.

以下のコードは,3つ組のタプル(x,y,z)から指定した位置の値を取り出す関数getFromTupleです.

getFromTuple (x,y,z) 0 = x
getFromTuple (x,y,z) 1 = y
getFromTuple (x,y,z) 2 = z

このような用法は後に紹介する代数的データ型を扱う際にも頻出します.

1.3.2 ガード

数式における分岐は,指示関数を用いて行うこともできます.

Haskellにおいて指示関数の記法に相当するのがガードです.

fib :: Int -> Int
fib n | n == 0 = 1
      | n == 1 = 1
      | n >= 2 = fib (n-1) + fib (n-2)

main = do
    print $ fib 5 --  8

特徴関数におけるifの位置が先に来ている以外は,基本的に対応関係にあるのがわかるかと思います.

1.3.3 case式

パターンマッチをインデントブロックで実現する手法としてcase式があります. パターンマッチで判定する変数をcase 変数 of のあとに指定して, それぞれのパターンとその結果を->でつなげる記法です. 指定のパターンに当てはまらないものすべて(これをワイルドカードといいます)を指定するために_を利用します.

fib :: Int -> Int
fib n = case n of
        0 -> 1
        1 -> 1
        _ -> fib (n-1) + fib (n-2)

main = do
    print $ fib 5 --  8

ワイルドカードはどのような値に対しても同じ値を返す関数を実装する場合などにも利用されます.

return10 :: a -> Int
return10 _ = 10

1.3.4 if式

Haskellにはifも存在します. if 条件に当てはまる場合の返り値をthenで指定します. else if で条件を追加し, elseでそれ以外のパターンを指定します. Pythonなどのif文と異なり,式なのでelseの場合の返り値も必ず指定する必要があります.

fib :: Int -> Int
fib n = if n == 0 then 1
        else if n == 1 then 1
        else fib (n-1) + fib (n-2)

main = do
    print $ fib 5 --  8

Haskellではあまりif式は利用されませんが, 1行で書けるため,式の中で部分的に利用する場合に便利です.

fib :: Int -> Int
fib n = if n == 0 then 1 else if n == 1 then 1 else fib (n-1) + fib (n-2)

1.4 再帰

Haskellにおいてもfor文に相当する記法は存在しますが,基本的にループは再帰によって実装されます. 再帰とは関数内で自分自身を呼び出すことです. これまで何度も登場していたfibも再帰を利用していましたが, もう少し細かく見てみましょう.

以下のPythonにおけるfor文を事例に考えてみましょう.

def total(xs):
    result = 0
    for x in xs:
        result += x
    return result

これと同値なプログラムをHaskellで記述すると以下のようになります.

total :: [Int] -> Int
total []  = 0
total [x] = x
total (x:xs) = x + (total xs)

main = print $ tatal [1..10] --  55

このtotal関数は,与えられたリストが空の場合0を返し,要素が一つの場合その要素を返します. 要素が複数あるリストの場合には,先頭の要素xをそれ以降の要素xsの合計に足すという処理を行います.

total [1,2,3]における処理の流れを追っていくと以下のようになります.

total [1,2,3]
= 1 + (total [2,3])
= 1 + (2 + (total [3]))
= 1 + 2 + 3 + (total [])
= 1 + 2 + 3 + 0
= 6

再帰の基本は,ループの終了状態をパターンマッチなどで指定して,そこに至るまでの状態の変化を再帰で記述することです. 処理がどのような状態になったら終わるのかを意識して記述しないと永遠に終了しないプログラムになるので注意しましょう.

1.5 高階関数

これまで扱ってきた関数の引数はすべて,値でしたが値ではなく関数を引数として指定することが可能です. 関数を引数に取る関数を高階関数といいます.

例えば関数fとリスト[x,y,z]を引数として受け取り,リストの各要素にfを適用したリスト[f x, f y, f z]を返す関数は以下のように実装できます.

applyFToList :: (a -> b) -> [a] -> [b]
applyFToList f []     = []
applyFToList f [x]    = [f x]
applyFToList f (x:xs) =  (f x): (applyFToList f xs)

main = do
    print $ applyFToList (2*) [4,5,6]  -- [8,10,12]
    print $ applyFToList (1+) [4,5,6]  -- [5,6,7]
    print $ applyFToList show [4,5,6]  -- ["4","5","6"]
    print $ applyFToList fib  [4,5,6]  -- [5,8,13]

関数部分は, (a -> b)のように,丸括弧で囲んでいます.

1.5.1 map

この関数と同じものが組み込み関数(あらかじめ定義された関数)として提供されている代表的な高階関数map :: (a -> b) -> [a] -> [b]です.

main = do
    print $ map (2*) [4,5,6]  -- [8,10,12]
    print $ map (1+) [4,5,6]  -- [5,6,7]
    print $ map show [4,5,6]  -- ["4","5","6"]
    print $ map fib  [4,5,6]  -- [5,8,13]

Ambiguous occurrence ‘map’
    It could refer to
       either ‘Prelude.map’,
              imported from ‘Prelude’ at app/practice.hs:1:1
              (and originally defined in ‘GHC.Base’)
           or ‘Data.Text.map’,
              imported from ‘Data.Text’ at app/practice.hs:4:1-16

import Data.Text hiding (map)
-- map 以外すべてをimport

import Data.Text hiding (Text,empty)
-- Text,emptyのみをimport

以下, よく用いられる代表的な高階関数に関して紹介します.

1.5.2 filter

filter :: (a -> Bool) -> [a] -> [a]はリストの中から与えられた関数で判定される条件に合致するもののみを抽出する関数です.

{-# LANGUAGE OverloadedStrings #-}
import Data.Text (elem)

main = do
    print $ filter (10 < ) [5,10,15,20] --  [15,20]
    print $ filter (Data.Text.elem 'a') ["cat","dog","bird"] --  ["cat"]

1.5.3 fold

foldl :: (a -> b -> a) -> a -> [b] -> a,

foldr :: (a -> b -> b) -> b -> [a] -> b

は畳み込み関数です.foldlはリストの左端,foldrはリストの右端から値を一つずつ抜き出して,2引数関数によって一つの値に畳み込んでいきます. リストのデータ構造的に基本的にはfoldlのほうが効率が良いのでfoldlが用いられます.

例として,

main = do
    print $ foldl (+) 0 [1,2,3] --  6

の挙動は,

foldl (+) 0 [1,2,3]

foldl (+) (0+1) [2,3]

foldl (+) (1+2) [3]

foldl (+) (3+3) []

6

となります.

1.5.4 zipWith, zip

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

は2つのリストからそれぞれ値を順番に取り出して,関数を適用した結果をリストに格納する高階関数です.

例として.

main = do
    print $ zipWith (++) ["a","b","c"] ["x","y","z"] --  ["ax","by","cz"]

の挙動は,

zipWith (++) ["a","b","c"] ["x","y","z"]

["a" ++ "x" ,"b" ++ "y","c" ++ "z"]

となります.

zip :: [a] -> [b] -> [(a,b)]

は2つのリストからそれぞれ値を順番に取り出して,[(左のリスト値,右のリストの値)]を返す関数です. タプルを返す2引数関数 , によって zipWith (,) として実装されます.

zip' :: [a] -> [b] -> [(a,b)]
zip' = zipWith (,)

tuple :: a -> b -> (a,b)
tuple a b = (a,b)

zip'' :: [a] -> [b] -> [(a,b)]
zip'' = zipWith tuple

main = do
    print $ zip [1,2,3] [11,12,13] --  [(1,11),(2,12),(3,13)]
    print $ zip' [1,2,3] [11,12,13] --  [(1,11),(2,12),(3,13)]
    print $ zip'' [1,2,3] [11,12,13] --  [(1,11),(2,12),(3,13)]

squareList [1,2,3,4] -- [1,4,9,16]

productList [1,2,3,4] -- 24

maxList [1,4,3] [2,2,5] -- [2,4,5]

1.6 無名関数(ラムダ式)

高階関数に与える関数はその場限りの利用となる場合が多いため,先程のzipWithとtupleによってzipを定義した例のように, いちいち別の関数名をつけることは手間が多くなり,コードも冗長になりがちです. そのような場合に, 使い捨ての関数を定義する手法が,無名関数(ラムダ式) Lambda expressionです.

ラムダ計算は\lambdaを表す記号,\を用いて, \ 引数 -> 返り値の形で式を定義できます.

例として,

f x y z = x + y + z は

\ x y z -> x + y + z となります.

zipWith の例は以下のようにも定義できます.

main = do
    print $ zip [1,2,3] [11,12,13] -- [(1,11),(2,12),(3,13)]
    print $ zipWith (\ x y -> (x,y)) [1,2,3] [11,12,13] --  [(1,11),(2,12),(3,13)]

また,練習問題中のmaxListは,以下のように定義できます.

main = do
    print $ zipWith (\x y -> if x > y then x else y)
                    [1,4,3]
                    [2,2,5] -- [2,4,5]

main = do
   print $ (,) "a" "b" -- ("a","b")
   print $ flip (,) "a" "b" -- ("b","a")
   ---
   print $ (>) 1 2 -- False
   print $ flip (>) 1 2 -- True

main :: IO ()
main = do
   print $ flip map [-3 .. 3]
         $ \ x -> case x >= 0 of
                True  -> 1
                False -> 0
        -- [0,0,0,1,1,1,1]

addThree [1,2,3] -- [4,5,6]

onlyEven [1,2,3,4,5,6] -- [2,4,6]

sumAbs [-3,4,-1,2] -- 10

1.7 関数合成

数学において,2つの関数 f(x), g(x)があるとき, f(g(x))を合成関数と呼び, f \circ g とも書きます. 通常Haskellでも関数を合成する場合には,

f (g x) あるいは f $ g x と書きますが,関数 (.)によって (f . g) x と書くことができます. 関数定義においては

h = f . g のように定義することが可能です.

f :: Int -> Int
f x = 2 * x

g :: Int -> Int
g x = 3 + x


-- 実行例
main :: IO ()
main = do
    -- f(g(x))
    print $ f $ g 2 -- 10
    -- \[f \circ  g \]
    print $ (f . g) 2 -- 10
    -- 定義
    let h = f . g
    print $ h 2 -- 10

:::

2 変数(値の束縛)

Pythonなどの言語では,特定の変数に値を代入することができます.例えば,以下の最大値を求めるプログラムでは,変数mに最初の中身はリストの最初の要素が代入された後,次々とより大きな変数が代入されていきます. 変数は名前の通り,次々とその値を変更していきます.

xs = [3,5,2,4,6,7,1]
m  = xs[0]

for x in xs[1:]:
    if x > m:
        m = x
print('max value:',m)

一方でHaskellでは,変数に一度値を割り当てると,その変数の値を後から変更することができません. 変数に値を再代入するという操作が許されていないのです. この性質を普遍性 （immutability）といいます. したがって,Haskellでは代入という言葉を使わず束縛といいます. これは,通常の手続き型言語との大きな違いになります.

例えば,以下のように一度値を束縛した変数に新しく変数を代入しようとするとxという変数に複数の宣言をしているというエラーが出ます(ghciでやる場合には,:{ :}を入れる必要があり余計にややこしいですね.すみません).

ghci> :{
ghci| x = 1
ghci| x = 2
ghci| :}

<interactive>:5:1: error:
    Multiple declarations of ‘x’
    Declared at: <interactive>:4:1
                 <interactive>:5:1

これは一見非常に不便なように感じられますが,これによって関数型プログラムでは,プログラムの安全性を高めています.

例えばPythonにおける以下のプログラムについて考えてみましょう.

counter = 0

def count_plus(x):
    global counter
    counter += x
    return counter

print(count(1))  # 出力: 1
print(count(1))  # 出力: 2

このプログラムでは,count()関数に対して同じ引数1を与えているにもかかわらず,関数を呼び出すたびに,グローバル変数counterが変更されて,結果が変わります. 同じ関数を呼び出しても,結果が変わるために関数のみから,関数の挙動を把握することができません.

一方でHaskellでは,常に同じ関数は,同じ入力に対して,同じ返り値を返します. このような特性を参照透過性(Referential Transparency)と呼び,これによってプログラムの挙動を把握しやすくしています.

また,上記のPythonのプログラムは,関数を実行するたびに,関数の外にある,counterという変数の状態が変化しています. このような,関数が実行されることで単に値を返す以外に何らかの｢外部の状態を変化させる｣ことを関数の副作用(Side Effect)といいます. これは言い換えれば,関数の実行によるプログラム全体への影響が,関数以外の外部の状態に依存していることを意味しており,プログラムの挙動を予測することを難しくします.

参照透過性と副作用は相互に結びついた概念ですが,Haskellでは参照透過性を保ち,副作用を排除するようにプログラムが設計されています. このように, ｢参照透過性｣ と ｢副作用の排除｣ の両方を持った関数型言語を 純粋関数型言語 と呼びHaskellの大きな特徴の一つです.

Haskellにおいて,変数への再代入が禁止されていることのメリットは理解していただけたかと思いますが,Haskellにも変数自体はあります.

Haskellにおける変数は主に,トップレベル変数及びローカル変数に大別されます.

2.1 トップレベル変数

先程の x=1のように,独立して宣言される変数をトップレベル変数と呼びます. トップレベル変数は,Pythonなどの言語におけるグローバル変数と同様に,スクリプト内のどこ場所からでも利用することができます.

x = 1

someFunc :: Int -> Int
someFunc y = x + y

main = do
    print $ someFunc 1 --  2

2.2 ローカル変数

手続き型言語においてスコープが制限された変数のように,特定の関数内でのみ参照可能な局所変数として,ローカル変数が存在します. Haskellにおけるローカル変数は, let式,where節の2つのパターンが用意されています(ラムダ式内の引数も見方によってはローカル変数かもしれません.)

2.2.1 let式

関数内で let 宣言 in 式の形式で局所変数を定義できます.

someFunc :: Int -> Int
someFunc y = let x = 1
           in x + y

main = do
    print $ someFunc 1 --  2

この変数xは別の関数内で参照することはできません.

someFunc :: Int -> Int
someFunc y = let x = 1
           in x + y

someFunc2 :: Int -> Int
someFunc2 y = x + y

main = do
    print $ someFunc2 1 --  Variable not in scope: x :: Int

複数の宣言をひとまとめにすることも可能です.

someFunc :: Int -> Int
someFunc z = let x = 1
                 y = 2
           in x + y + z

main = do
    print $ someFunc 1 --  4

Do記法を利用するとinを省略することができます.

someFunc :: Int -> Int
someFunc z = do
    let x = 1
        y = 2
    x + y + z

main = do
    print $ someFunc 1 --  4

2.2.2 where節

数式の直後にインデントをつけてwhere 宣言と書くことでも局所変数や局所関数を定義できます.

someFunc :: Int -> Int
someFunc z = f z
    where
    x = 1
    y = 2
    f z = x + y + z

main = do
    print $ someFunc 1 --  4

3 練習問題(関数総合)

-- 実行例
main :: IO ()
main = do
  let xs = [1, 2 .. 5]
      ys = [5, 4 .. 1]
  putStrLn $ "標準偏差: " ++ show (stddev xs) ---  1.4142135623730951
  putStrLn $ "相関係数: " ++ show (correlation xs ys) --- -0.9999999999999998

-- 平均値を求める関数\mean :: [Double] -> Double
mean xs = sum xs / fromIntegral (length xs)

-- 標本標準偏差を求める関数
stddev :: [Double] -> Double
stddev xs = sqrt variance
  where
    m = mean xs
    n = fromIntegral (length xs)
    variance = sum (map (\x -> (x - m)^2) xs) / n

-- 積率相関係数を求める関数
correlation :: [Double] -> [Double] -> Double
correlation xs ys = covariance / (stddev xs * stddev ys)
  where
    mx = mean xs
    my = mean ys
    n  = fromIntegral (length xs)
    covariance = sum (zipWith (\x y -> (x - mx)*(y - my)) xs ys) / n

-- 実行例
main :: IO ()
main = do
  let xs = [1, 2 .. 5]
      ys = [5, 4 .. 1]
  putStrLn $ "標準偏差: " ++ show (stddev xs) ---  1.4142135623730951
  putStrLn $ "相関係数: " ++ show (correlation xs ys) --- -0.9999999999999998

-- 実行例
main :: IO ()
main = do
   print $ perceptronOR False False -- False
   print $ perceptronOR True False  -- True
   print $ perceptronOR False True  -- True
   print $ perceptronOR True True   -- True

perceptronOR :: Bool -> Bool -> Bool
perceptronOR x1 x2
  | sum >= 0  = True
  | otherwise = False
  where
    g True = 1
    g False = 0
    sum = 0.5 * g x1 + 0.5 * g x2 - 0.2

-- 実行例
main :: IO ()
main = do
   print $ perceptronOR False False -- False
   print $ perceptronOR True False  -- True
   print $ perceptronOR False True  -- True
   print $ perceptronOR True True   -- True