第３章　関数と定数の定義

3.1　関数
3.2　パターン
3.3　ガード
3.4　式
3.5　局所定義
3.6　定数の定義
3.7　関数の型付け

3.1　関数

関数定義       =  [関数の型定義]             // 関数の型付けについては、4章参照
                  関数の定義
関数の定義     =  {関数代替部定義 ;}+
関数代替部定義 =  関数 {パターン}            // パターンについては3.2参照
                  {LetBefore式}              // 3.5.4参照
                  {{|ガード}=[>] 関数本体}+  // ガードについては3.3参照
                  [局所関数代替部定義]       // 3.5参照
関数           =  関数名                     // 通常の関数
               |  (関数名)                   // 前置を使用した演算子関数
関数本体       =  ルート式 ;                 // 3.4参照
                  [局所関数定義]             // 3.5参照

• 仮引数で指定されたパターンは、それに対応する関数適用の実引数に照合しており（3.2参照）、且つ、
• 右手側で指定されたオプションのガード（3.3参照）がTrueに評価される場合。

• 関数定義は、実装モジュール（2.3参照）でのみ認められる。
• 関数の代替部は、テキスト順にグループ化される（レイアウトセンシティブモードを選択していない場合は、セミコロンによって分割される）ことが必要である。
• 各関数代替部は、同一の関数記号で始まらなければならない。
• 関数は一定のアリティを持つので、各規則では、同一数の仮引数を指定しなければならない。関数は、カリー化して使用できるし、高階関数型言語で通常のように、どんな数の引数にも適用できる。
• 関数名は、原則として、同一の名前空間と同一の通用範囲内の他の名前とは異なっていなければならない（2.1参照）。しかし、関数と演算子を多重定義できる（６章参照）。

CLEANモジュールの関数定義の例

module example                            // モジュールヘッダ

import StdInt                             // 黙示的インポート

map:: (a -> b) [a] -> [b]                 //  mapの型
map f list = [f e \\ e <- list]           //  関数mapの定義

square:: Int -> Int                       //  squareの型
square x = x * x                          //  関数squareの定義

Start:: [Int]                             //  Start規則の型
Start = map square [1..1000]              //  Start規則の定義

• 演算子が中置で使用される場合、両側に引数が存在していなければならない。演算子は、カリー化された方法で使用できるが、その時には、通常の前置関数として使用しなければならない。

演算子定義

(++) infixr 0 :: [a] [a] -> [a]
(++) []      ly  = ly
(++) [x:xs]  ly  = [x:xs ++ ly]

(o) infixr 9 :: (a -> b) (c -> a) -> (c -> b)
(o) f g = \x = f (g x)

3.2　パターン

パターン         =  [変数 =:] 括弧パターン
括弧パターン     =  (グラフパターン)
                 |  構成子
                 |  パターン変数
                 |  特殊パターン
                 |  ダイナミックパターン

グラフパターン   =  構成子 {パターン}                      // 通常のデータ構成子
                 |  グラフパターン 構成子名 グラフパターン // 中置データ構成子
                 |  パターン

パターン変数     =  変数
                 |  _

代数データ型定義の例と、関数定義のパターン照合での使用例

::Tree a = Node a (Tree a) (Tree a)
         | Nil

Mirror:: (Tree a) -> Tree a
Mirror (Node e left right)  =  Node e (Mirror right) (Mirror left)
Mirror Nil                  =  Nil

無名変数の使用例

:: Complex :== (!Real,!Real)        //  シノニム型定義

realpart:: Complex -> Real
realpart (re,_) = re                //  reと_はパターン変数

パターンと部分パターンを識別するリストパターン、ガードと変数の使用法。
mergeは、2つの（ソートされた）遅延リストを1つの（ソートされた）リストに結合する

merge:: [Int] [Int] -> [Int]
merge f []   = f
merge [] s   = s
merge f=:[x:xs] s=:[y:ys]
| x<y        = [x:merge xs s]
| x==y       = merge f ys
| otherwise  = [y:merge f ys]

• 指定したパターンによって、関数を部分関数（3.7.3参照）に変えることができる。部分関数が、その関数の定義域の外側で適用されると、実行時エラーをもたらす。コンパイル時には、そのような状況が発生するかもしれないという警告が生成される。

• 関数定義の左手側に導入される全ての変数記号は、異なった名前を持たなければならない。

特殊パターン      = 基本値パターン          // 4.1.2参照
                  | リストパターン          // 4.2.2参照
                  | 組パターン              // 4.3.2参照
                  | 配列パターン            // 4.4.2参照
                  | レコードパターン        // 5.2.2参照

3.3　ガード

ガード       = 論理式
             | otherwise

• 関数の最後の規則代替部のみが、ガードとしてotherwiseを持つことができるが、ガードを持たなくともよい。
• ガードは、関数を部分関数に変えることができる（3.6.3参照）。部分関数がその定義域の外側に適用される場合には、実行時エラーがもたらされる。コンパイル時には、これを検知できない。

ガードを持つ関数定義

filter:: Int [Int] -> [Int]
filter pr [n:str]
| n mod pr == 0  = filter pr str
| otherwise      = [n:filter pr str]

前のfilterに同等な定義

filter:: Int [Int] -> [Int]
filter pr [n:str]
| n mod pr == 0  = filter pr str
                 = [n:filter pr str]

• 入れ子されたガードの少なくとも1つが成功であると保証する為に、入れ子ガード代替部は、最後の代替部として'デフォルトケース'を常に持たなければならない。

入れ子されたガードの例

例 引数1 引数2
| 述語11 引数1                              // if 述語11 引数1
    | 述語21 引数2   = 計算1 引数1 引数2    // then (if 述語21 引数2
    | 述語22 引数2   = 計算2 引数1 引数2    // elseif 述語22 引数2 then
    | otherwise     = 計算3 引数1 引数2    // else ...)
| 述語12 引数1       = 計算4 引数1 引数2    // elseif 述語12 引数1 then ...

3.4　式

ルート式         = グラフ式

グラフ式         = 適用
適用             = {括弧グラフ}+
                 | グラフ式 演算子 グラフ式
括弧グラフ       = グラフ変数
                 | 構成子
                 | 関数
                 | (グラフ式)
                 | ラムダ抽象                        // 3.4.1参照
                 | Case式                            // 3.4.2参照
                 | Let式                             // 3.5.1参照
                 | 特殊式
                 | ダイナミック式

関数             = 関数名
                 | (関数名)
構成子           = 構成子名
                 | (構成子名)
演算             = 関数名
                 | 構成子名
グラフ変数       = 変数
                 | 選択子変数

• 全ての式は、正当な型でなければならない（５章参照）。
• 式内で現れる全記号は、その式が現れる通用範囲内のどこかで定義されていなければならない。
• グラフ式の通用範囲内には、各ノード変数と選択子変数の定義がなければならない。

• 式内で等しい優先順位を持つ演算子を、その固定性が衝突する方法で適用することは認められていない。従って、a₁ op₁ a₂ op₂ a₃において、演算子op₁とop₂が同一の優先順位を持つ場合には、ある衝突が発生する。つまり、op₁がinfixlと定義される場合、その式はa₁ op₁ (a₂ op₂ a₃)と読まれなければならない一方で、op₂がinfixlと定義される場合、その式は、(a₁ op₁ a₂) op₂ a₃と読まれなければならない。
• 演算子が中置で使用される場合、両側に引数が存在していなければならない。演算子は、カリー化された（2つより少ない引数に適用される）方法で使用できるが、その場合には、通常の前置関数/構成子として使用されなければならない。演算子が通常の前置関数/構成子として使用される場合、それを括弧で囲まなければならない。

循環ルート式の例。yは、循環グラフを参照するルート式である。
乗算演算子*は、ここでは、カリー化された方法で、前置して使用される。

ham :: [Int]
ham = y
where y = [1:merge (map ((*) 2) y) (merge (map ((*) 3) y) (map ((*) 5) y))]

特殊式                   =| 基本値             // 4.1.1参照
                         |  リスト             // 4.2.1参照
                         |  組                 // 4.3.1参照
                         |  配列               // 4.4.1参照
                         |  配列選択           // 4.4.1参照
                         |  レコード           // 5.2.1参照
                         |  レコード選択       // 5.2.1参照

3.4.1　ラムダ抽象

ラムダ抽象    = \ {パターン} =  グラフ式
              | \ {パターン} -> グラフ式

ラムダ式の例

AddTupleList:: [(Int,Int)] -> [Int]
AddTupleList list = map (\(x,y) = x+y) list

定義されている無名関数の引数は、それに対応する関数本体でただ１つの意味しか持たない。

3.4.2　Case式と条件式

Case式            = case グラフ式 of
                    { {Case代替部定義}+ }
                  | if 括弧グラフ 括弧グラフ 括弧グラフ
Case代替部定義    = {パターン}
                    {{LetBefore式}
                    {| ガード} = [>] 関数本体}+
                    [局所関数代替部定義]
                  | {パターン}
                    {{LetBefore式}
                    {| ガード} -> 関数本体}+
                    [局所関数代替部定義]

パターン内で定義される変数は、それに対応する代替部においてただ１つの意味を持つ。

• case式の全ての代替部は、同一型でなければならない。
• パターンのどれも照合しない場合、実行時エラーが生成される。

case式

h x =          case g x of
               [hd:_]   = hd
               []       = abort "result of call g x in h is empty"

は、意味的には以下のものと同等である。

h x = mycase (g x)
where
          mycase  [hd:_]    = hd
          mycase  []        = abort "result of call g x in h is empty"

• 条件式のthenとelse部は、同一型でなければならない。
• 弁別式は、型Boolでなければならない。

3.5　局所定義

局所定義      = グラフ定義
              | 関数定義

3.5.1　let式：式内の局所定義

Let式        = let {{局所定義}+ } in グラフ式

letブロックで定義された関数と選択子は、以下のexpression内でただ１つの意味しか持たない。

リストの内包表記内で使用されるlet式の例

doublefibs n = [let a = fib i in (a, a) \\ i <- [0..n]]

3.5.2　whereブロック：関数代替部内の局所定義

局所関数代替部定義   = [where] {{局所定義}+ }

whereブロックで定義された関数と選択子は、関数定義全体において局所的に使用できる。

sieveとfilterは、whereブロック内で定義された局所関数である。これらは、primesの内側でのみ意味を持つ。
大域レベルでは、この関数は見えない。

primes::[Int]
primes = sieve [2..]
where
    sieve::[Int] -> [Int]                    // primesの局所関数
    sieve [pr:r]  = [pr:sieve (filter pr r)]

    filter::Int [Int] -> [Int]               // primesの局所関数
    filter pr [n:r]
    | n mod pr == 0  = filter pr r
    | otherwise     = [n:filter pr r]

primesの代替的な定義。関数filterは、sieveに局所定義されている。
filterは、sieveの引数prに直接にアクセスできる。

primes::[Int]
primes = sieve [2..]
where
     sieve::[Int] -> [Int]                 // primesの局所関数
     sieve [pr:r]  = [pr:sieve (filter r)]
     where
           filter::[Int] -> [Int]          // sieveの局所関数
           filter [n:r]
           | n mod pr == 0  = filter r
           | otherwise     = [n:filter r]

3.5.3　Withブロック：ガードされた代替部内の局所定義

局所関数定義      = [with] {{局所定義}+ }
局所定義          = グラフ定義
                  | 関数定義

withブロック内で定義された関数と選択子は、それに対応する関数代替部内でのみ局所的に使用できる。

3.5.4　Let-Before式：ガード間に定義された局所定数

状態遷移関数の使用。一意に型付けられた状態ファイルは、file、file1、file2と多くの改名を伴いながら、
ある関数からまたある別の関数に渡される。

readchars:: *File -> ([Char], *File)
readchars file
| not ok     = ([],file1)
| otherwise  = ([char:chars], file2)
where
      (ok,char,file1)  = freadc file
      (chars,file2)    = readchars file1

LetBefore式         = # {グラフ定義}+
                    | #!{グラフ定義}+

このことは、以下の図で示されている。

let before式、短縮記法、let beforeの特別な通用範囲を使用している再利用名の例

readchars:: *File -> ([Char], *File)
readchars file
# (ok,char,file)      = freadc file
| not ok              = ([],file)
# (chars,file)        = readchars file
= ([char:chars], file)

スレッド化した引数を改名する同等な定義

readchars:: *File -> ([Char], *File)
readchars file
# (ok,char,file1)  = freadc file
| not ok           = ([],file1)
# (chars, file2)   = readchars file1
= ([char:chars], file2)

let before式の濫用

exchange:: (a, b) -> (b, a)
exchange (x, y)
# temp = x
  x    = y
  y    = temp
= (x, y)

3.6　定数の定義

グラフ定義 = 選択子 =[:] グラフ式 ;

関数内に局所定義されたグラフ：lastとラベル付けられたグラフは、
関数StripNewline内で共有され、ただ一回だけ計算される。

StripNewline:: String -> String
StripNewline "" = ""
StripNewline string
| string !! last<>'\n' = string
| otherwise            = string%(0,last-1)
where
        last = maxindex string

局所定義された循環定数グラフを使用して定義されたハミング数と、
大域定議された再帰的定関数によって定義されたハミング数。
最初の定義（ham1）は効率的である。というのも、既に計算された数が、共有を経由して再利用されるからである。
第２の定義は（ham2）の方が遥かに非効率である。というのも、再帰関数は、全てを再計算するからである。

ham1:: [Int]
ham1 = y
where y = [1:merge (map ((*) 2) y) (merge (map ((*) 3) y) (map ((*) 5) y))]

ham2:: [Int]
ham2 = [1:merge (map ((*) 2) ham2) (merge (map ((*) 3) ham2) (map ((*) 5) ham2 ))]

局所定グラフ対局所定関数定義：biglist1とbiglist2は、ただの一回しか計算されないグラフであり、
biglist3は、適用される毎に計算される定関数である。

biglist1  =  [1..10000]    // （局所定義されれば）グラフ
biglist1  =  [1..10000]    // （大域定議されれば）定関数
biglist2  =: [1..10000]    // （常に）グラフ
biglist3  => [1..10000]    // （常に）定関数

選択子

選択子        = 括弧パターン     // 括弧パターンは、3.2参照

組要素を局所的に選ぶ選択子の使用例

unzip::[(a,b)] -> ([a],[b])
unzip []          = ([],[])
unzip [(x,y):xys] = ([x:xs],[y:ys])
where
        (xs,ys) = unzip xys

• グラフ定義の左手側の選択子が、右手側のグラフに照合しない場合、実行時エラーがもたらされる。
• 選択子に導入される選択子変数は、互いに異なっており、同一通用範囲及び名前空間内で既に使用されていてはならない（1.2参照）。
• 実行時に失敗するかもしれないパターンの使用を回避する為、0アリティの構成子でテストすることは認められていない。例えば、選択子パターン内で使用されるリストは、[a:_]という形でなければならない。[a]は使用できない。というのも、これは、0アリティ構成子[]でのテストを含意する[a:[]]を表しているからである。もしパターンがレコードならば、関心のある内容を持つフィールドだけを、パターン内で指示すればよい。
• 配列は、選択子内のパターンとして使用できない。
• 選択子は大域定義できない。

3.7　関数の型付け

関数定義                 = [関数の型定義]
                           関数定義

関数の型定義             = 関数名 :: 関数の型 ;
                         | (関数名) [固定性][優先順位] [:: 関数の型] ;
固定性                   = infixl
                         | infixr
                         | infix
優先順位                 = 数字
関数の型                 = 型 -> 型 [クラス文脈] [一意型不等式]
型                       = {括弧型}+
括弧型                   = [全称量化変数] [正格] [一意型属性] 単純型
全称量化変数             = A.{型変数 }+:

• ::の前の関数記号は、それに対応する書換規則の関数記号と同じでなければならない。
• 関数のアリティは、引数の数（そのデカルト積が取られる）に対応していなければならない。従って、CLEANでは、関数の型によって、そのアリティを伝えることができる。

関数のアリティがどのように型に反映されているかを示している

map:: (a->b) [a] -> [b]                      // mapは、アリティ2を持つ
map f []      =     []
map f [x:xs]  =     [f x : map f xs]

domap:: ((a->b) [a] -> [b])                  // domapは、アリティ0を持つ
domap = map

• 関数の引数と結果型は、種Xでなければならない。
• 局所定義関数の型仕様の中では、周囲の関数の型仕様で導入された型変数を参照できない（定義された型の通用範囲規則はまだない）。従って、プログラマは、このような局所関数の型を指定できない。しかし、型システムによって、その型は、（コンパイラによって大域レベルに持ち上げられた後で）推論され、検査される。

反例（不法な型仕様）。関数gは、１つの組を返す。最初の組要素の型は、fの多相引数の型と同じである。
（ここで"^"によって指示される）このような依存関係は指定できない。

f:: a -> (a,a)
f x = g x
where
          // g:: b -> (a^,b)
          g y = (x,y)

3.7.1　カリー化関数の型付け

3.7.2　演算子の型付け

• 演算子の型は、アリティ2の関数を型付けする為に定義されている要件に従わなければならない。
• 演算子が明示的に型付けされる場合、演算子名はまた、型規則の()の間に置かれなければならない。
• 中置演算子が()の間に囲まれる場合、前置関数として適用できる。右手側に新しく定義された演算子のあり得る再帰定義も、この規約に従う。

演算子定義とその型の例

(o) infix 8:: (x -> y) (z -> x) -> (z -> y)             // 関数合成
(o) f g = \x -> f (g x)

3.7.3　部分関数の型付け

• 部分関数が、その関数の定義域の外側の値に適用される場合、実行時エラーがもたらされる。コンパイラは、部分的かもしれない関数が定義されると、警告を与える。

関数を全体的にするabortの使用例

fac:: Int -> Int
fac 0                = 1
fac n
| n>=1               = n * fac (n - 1)
| otherwise  = abort "fac called with a negative number"

3.7.4　関数の型に全称量化子を明示的に使用

関数mapはいつものように定義されており、全称量化子を指定していない。

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

反例。再び同一の関数mapだが、ここでは、黙示的に想定されていた全称量化子を可視的にした。
指定した型の意味をより正確に示しているが、型定義も少し長くなっている。
Cleanの現行版は、まだ最上レベルでは全称量化子を認めていない！！！

map:: A.a b:(a->b) [a] -> [b]
map f []        =    []
map f [x:xs]    =    [f x : map f xs]

関数の型                = 型 -> 型 [クラス文脈] [一意型不等式]
型                      = {括弧型}+
括弧型                  = [全称量化変数] [正格] [一意型属性] 単純型
全称量化変数            = A.{型変数 }+:

例：関数hは、型(A.a : [a] -> Int)の多相関数を、CharのリストだけでなくIntのリストにも適用するのに使用される。
hの型仕様に全称量化子を明示的に使用することによって、この定義は認められる。

:: (A.a: [a] -> Int) -> Int
h f = f [1..100] + f ['a'..'z']

Start = h length

反例：関数h2は、型([a] -> Int)の関数を、CharのリストだけでなくIntのリストにも適用するのに使用される。
この場合、型単一化エラーによって、この定義は拒絶される。
h2の引数は、[a] -> Intで単一化可能であると想定されるが、h2の引数が(A.a :: [a] -> Int)であるとは想定されない。
従って、型変数aは、IntとCharの両方で単一化され、型エラーをもたらす。

h2:: ([a] -> Int) -> Int
h2 f = f [1..100] + f ['a'..'z']

Start = h2 length

反例：関数h3は、関数を、Charのリストだけではなく、Intのリストにも適用するのに使用される。
型を指定していないので、型推論システムは、fは、型([a] -> Int)であって、型(A.a :: [a] -> Int)ではないと想定するだろう。
この状況は、上と同一であり、再び型エラーを得るだろう。

h3 f = f [1..100] + f ['a'..'z']

Start = h3 length

• CLEANは、ランク2の多相関数を自動的に推論できない！明示的にランク2の全称量化型を指定しなければならない。
• ランク2より高いランクの明示的な全称量化（例えば、関数引数の型仕様の内側のどこかで指定された量化子）は認められていない。
• ランク2の多相関数は、関数が全称量化されている引数に対しては、カリー化した方法では使用できない。

反例：以下の例では、f1は、その最後の引数が全称量化されているので、
全ての引数に適用される場合にのみ使用できることがわかる。
関数f2は、全称量化されていない最後の引数に関してのみ、カリー化して使用できる。

f1:: a (A.b:b->b) -> a
f1 x id = id x

f2:: (A.b:b->b) a -> a
f2 id x = id x

illegal1 = f1                           // これは型エラーをもたらすだろう。

illegal2 = f1 3                         // これは型エラーをもたらすだろう。

legal1 :: Int
legal1 = f1 3 id where id x = x        // ok

illegal3 = f2                           // これは型エラーをもたらすだろう。

legal2 :: (a -> a)
legal2 = f2 id where id x = x          // ok

legal3 :: Int
legal3 = f2 id 3 where id x = x        // ok

3.7.5　正格な引数を持つ関数

関数の型     = 型 -> 型 [クラス文脈] [一意型不等式]
型           = {括弧型}+
括弧型       = [全称量化変数] [正格] [一意型属性] 単純型

正格注釈を付けられた引数を持つ関数の例

Acker:: !Int !Int -> Int
Acker 0 j =  inc j
Acker i 0 =  Acker (dec i) 1
Acker i j =  Acker (dec i) (Acker i (dec j))

• 正格性注釈は、引数の型の最外レベルでのみ認められるということに注意して欲しい。引数の型インスタンスの内側で正格性注釈を付けることはできない（組とリストのようないくつかの定義済みの型は除くが）。データ構造（のあらゆる部分）は、遅延から正格に変更できるが、その場合には、このことを型定義に指定しなければならない（5.1.5参照）。