Haskell Programming Language 第２章 言語プログラミングの言語 Haskell Programming Language

言語の定義には言語が必要 言語の記述にプログラミング言語を使用 関数型言語による言語プログラミング 言語機能の記述はプログラムとして実行可能 抽象的な言語の概念を具体例を通じて確認 関数型言語による言語プログラミング 関数でアルゴリズムを表現する 複雑な概念を簡潔に表現 関数型言語の基本的な概念の理論的な基盤が確立されている

関数型言語Haskell ホームページ システムHugs 参考書 http://www.haskell.org/ http://haskell.cs.yale.edu/hugs/ 参考書 ホームページを参照 Bird,R. and Wadler,P.: Introduction to Functional Programming, Prentice-Hall, 1988. (邦訳: 武市正人訳, 関数プログラミング, 近代科学社, 1991, ISBN4-7649-0181-1)

式・値 式の評価：式＝＞値 Prelude> 3*8 24 Prelude> 2+3*8 26 1.6 Prelude> 3 / 5 0.6 Prelude> mod 3 2 1 Prelude> 3 `mod` 2 Prelude> 3 `div` 2

定義・スクリプト 定義：値に名前をつけること スクリプト：定義をまとめて記述したもの E:\work\2000\00\2-1.hs E:\work\2000\00\2-1.lhs You can write anything here. > x = 3*8 > y = x+21 x = 3*8 y = x+21 …

環境 環境：式を評価する際の名前と値の対応 局所的な宣言(local declaration): whereのあとに定義を置く 局所的な宣言をもつ式: let 定義 in 式 x = y * (y + 5) 　　where y = 3 let y = 3 in y * (y + 5)

式の構成 （まとめ） 演算子を用いて演算対象を結合 演算子を一般化(演算対象数)した関数 関数を用いて式を組み合せてより 大きい式を構成する 式の構成　（まとめ） 演算子を用いて演算対象を結合 標準的な環境: 算術演算子など 演算子を一般化(演算対象数)した関数 関数を用いて式を組み合せてより 大きい式を構成する Sin, cos: functions

関数 数学的な関数の定義 関数は 記法 集合のあいだの写像 式を構成する際の結合手段 写像の対応関係の表現 対応関係の計算法 f 　::　 a 　->　 b

関数の定義と適用 定義 適用 square 5 square 5 + 2 square :: Int -> Int square x = x * x 適用 square 5 square 5 + 2

関数抽象 関数そのものを表す表記法 関数：値 適用 \x -> x * x square = \x -> x * x

演算子と関数 演算子と関数に本質的な違いはない セクション(section): 2項演算子は演算対象のあいだに置く 関数はつねに引数の前に置く セクション(section): 演算子を関数として扱う仕組み (*) 3 8 = (3*) 8 = (*8) 3 = 3*8

演算子と関数 2引数関数の演算子化 関数名を逆引用符(アクサングラーブ)で囲む sumsquares x y = square x + square y where square z = z * z sumsquares 3 4 3 `sumsquare` 4

演算子の定義 名前：記号文字で表現 結合順位(precedence): 左結合的: -, / 右結合的: ^ 結合的: +, * x *+ y = x * 10 + y

標準的な演算子例 infixl 9 !! infixr 9 . infixr 8 ^ infixl 7 * infix 7 /, `div`, `rem`, `mod` infixl 6 +, - infix 5 \\ infixr 5 ++ infix 4 ==, /=, < , < =, > , > = infix 4 `elem`, `notElem` infixr 3 && infixr 2 ||

高階関数 高階関数(higher order function) 関数合成(functional composition) 関数を引数にとる関数 関数を結果とする関数 関数合成(functional composition) (f . g) x = f (g x) 関数の部分適用(partial application) 2引数以上の関数に一部の引数だけを与えること t1-> (t2 -> ( ... -> (tn-> t) ) ) (1+)

再帰的な定義 定義する関数の定義式のなかにそれ自体が現れる factorial 0 = 1 factorial (n+1) = n * factorial n factorial n = if x==0 then 1 else n*factorial(n-1)

データ型 型: 同様の性質をもつ値の集合と演算 基本型 リスト 組 関数

基本型 整数型Int 論理型Bool 文字型Char 浮動小数点数型Float

整数型Int 定数の表記: 数字0,1,...,9による10進表記 演算 関数 加算+,減算-,乗算*,除算`div`,剰余`rem`など negate :: Int -> Int odd :: Int -> Bool even :: Int -> Bool

論理型Bool 論理値はTrueとFalse 演算 論理和||, 論理積& & 関数 not :: Bool -> Bool

文字型Char 引用符‘で囲まれた1つの文字で表現 関数の例 ord :: Char -> Int chr :: Int -> Char

浮動小数点数型Float 定数：　 浮動小数点数 演算と関数 整数型と同様なものが多い

リスト おなじ型のデータが一列に並んだデータ 型: [t] リスト型 [t] のデータは 構成子 空リスト [ ] 空でないリスト：[1,2,3,4,5]、[1..5] 構成子 [] :: [t] (:) :: t -> [t] -> [t] （右結合的） 型変数

リストの関数 連接演算子 ++ リストの内包表記(list comprehension) [1,2,3]++[4,5] = [1,2,3,4,5] ++型 ？ リストの内包表記(list comprehension) 数学の集合の表記法と同様の記法 [x+1 | x < - [1,2,3]] [x+y | x < - [10,20,30], y < - [4,5]] [ [x | x < - [0..9], even x] [x-y | x < - [1,2,3], y < - [ ]]

文字列 文字の並びを "で囲む表記法もある 型： String ([Char]) 例 “Hello ” ++ “world!” = “Hello world!”

組 いくつかのデータの組から構成されるデータ 型: ( t1, t2, ..., tn ) 値の例 関数 (1,2) (1,True,[2,3,4]) 関数 fst :: (t1,t2) -> t1 snd :: (t1,t2) -> t2

関数 関数をデータとして扱う 型: s -> t 値の表現：関数抽象 関数:高階関数

カリー化(currying) 対のデータをとる関数を、関数を値とする関数に変換すること f' :: Int -> Int -> Int f' x y = x^2 + y^2 f :: (Int,Int) -> Int f (x,y) = x^2 + y^2 curry :: ((a,b) -> c) -> (a -> b -> c) curry f x y = f (x,y) Uncurry?

型の表現式 定義に型を明示することは必要ではない 型の同義名(type synonym): 定義では型を添えるとわかりやすくなる type IntPair = (Int,Int) T = Int | Bool | Char | Float | t | [T] | (T1,T2,…,Tn) | T1 -> T2

構成子(constructor)を定義する 代数型 データの構成法によるデータ型の定義 すでに存在するデータからあらたなデータを作り出す 構成子(constructor)を定義する

値の列挙によるデータ型の定義 data Day = Sun | Mon | Tue | Wed | Thu | Fri | Sat workday :: Day -> Bool workday Sun = False workday Mon = True workday Tue = True workday Wed = True workday Thu = True workday Fri = True workday Sat = False

構成法の列挙による型の定義 data Figure = Circle Float ｜Rectangle Float Float 構成子Circle, Rectangle 半径が 5.2 の円: Circle 5.2 辺が 3.2 と 2.5 の長方形は？

再帰的な型の定義 自然数を帰納的に定義するPeanoの数 data Nat = Zero | Succ Nat data List a = Nil | Cons a (List a)

パターン照合 関数定義における引数のパターンに応じた場合分け area :: Figure -> Float area (Circle r) = 3.14 * r ^ 2 area (Rectangle x y) = x * y

リストのパターン照合 head :: [a] -> a head (x:xs) = x tail :: [a] -> [a] tail (x:xs) = xs sum :: [Int] -> Int sum [] = 0 sum (x:xs) = x + sum xs

組のパターン照合 fst :: (a,b) -> a fst (x,_) = x snd :: (a,b) -> b snd (_,y) = y fst3 :: (a,b,c) -> a fst3 (x,_,_) = x snd3 :: (a,b,c) -> b snd3 (_,y,_) = y thd3 :: (a,b,c) -> c thd3 (_,_,z) = z

標準的な関数（リスト上） 写像関数(map function) リストの各要素に関数を適用 > map (1+) [1,2,3] map :: (a -> b) -> [a] -> [b] map f xs = [ f x | x < - xs ]

標準的な関数（リスト上） 濾過関数(filter function) 条件を満たすリストの要素を抽出 filter even [0..9] ｆilter :: (a -> Bool) -> [a] -> [a] filter p xs = [ x | x < - xs, p x ]

標準的な関数 たたみ込み関数(fold function) リストの要素間に演算子をはさみこむ foldl () e [x1,x2, ..., xn] = (((e  x1)  x2) ...)  xn foldr () e [x1,x2, ..., xn] = x1  (x2  ( ... (xn  e))) sum :: [Int] -> Int sum = foldl (+) 0 product :: [Int] -> Int product = foldl (*) 1 concat :: [[a]] -> [a] concat = foldr (++) [ ] 定義？

抽象型 抽象型(abstract type): 例：対応関係の型 Assoc a b 機能を関数で定義して型を規定 これらの関数だけでデータを扱う データ型の実現法は関数だけに依存 データ実現法の隠蔽 例：対応関係の型 Assoc a b None :: Assoc a b Loopup :: Eq a => Assoc a b -> a -> b Update :: Eq a => Assoc a b -> a -> b -> Assoc a b

対応関係の例

関数型による 抽象型 Assoc a b の実現 type Assoc a b = a -> b none :: Assoc a b none x = undefined lookup :: Assoc a b -> a -> b lookup h x = h x update :: Eq a => Assoc a b -> a -> b -> Assoc a b update h x v y | x==y = v | otherwise = lookup h y

第２章のまとめ 1 2.1 式・値・環境 2.2 関数 2.3 再帰的な定義 プログラミング言語のプログラミングに用いる言語 2.1　式・値・環境 プログラミング言語のプログラミングに用いる言語 関数プログラミング言語は式が基本 式の構成要素としての変数の表わす値は環境によって決まる 2.2　関数 式を結合する関数を定義して用いることができる 関数は始域(定義域)と終域(値域)が決まっている 2.3　再帰的な定義 関数は一般的には再帰的に定義される

第２章のまとめ 2 2.4 データ型 2.5 代数型 2.6 パターン照合 2.7 標準的な関数 2.8 抽象型 2.4　データ型 基本データ型: 数、論理値、文字 データ構造の構成法: リスト、組、関数 2.5　代数型 データ型を代数型として定義することができる 2.6　パターン照合 引数のパターンによる場合分けで関数を定義する 2.7　標準的な関数 標準的な関数でさまざまな演算の定義が可能 2.8　抽象型 データの性質を演算によって定める データの実現法によらないプログラムを書くことができる