Haskell Programming Language

Presentation on theme: "Haskell Programming Language"— Presentation transcript:

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

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

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

4 式・値 式の評価：式＝＞値 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

5 定義・スクリプト 定義：値に名前をつけること スクリプト：定義をまとめて記述したもの 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 …

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

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

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

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

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

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

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

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

14 標準的な演算子例 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 ||

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

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

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

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

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

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

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

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

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

24 リストの関数 連接演算子 ++ リストの内包表記(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 < - [ ]]

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

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

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

28 カリー化(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?

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

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

31 値の列挙によるデータ型の定義 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

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

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

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

35 リストのパターン照合 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

36 組のパターン照合 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

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

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

39 標準的な関数 たたみ込み関数(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 (++) [ ] 定義？

40 抽象型 抽象型(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

41 対応関係の例

42 関数型による 抽象型 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

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

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