基本データ型上の関数
胡 振江東京大学 計数工学科 2008年10月27日
論理型
論理型(Bool)はTrueとFalseだけを含む. data Bool = False | True
論理型上の関数
論理否定
not :: Bool → Bool
not False = True not True = False Remark:
パターンマチング (Pattern matching)による定義
書き換え規則 (Rewriting rules) not ⊥ = ⊥
論理型上の関数
論理積・論理和
(∧), (∨) :: Bool → Bool → Bool False∧ x = False True∧ x = x False∨ x = x True∨ x = True Remark: ⊥ ∧ False = ⊥ False∧ ⊥ = False True∧ ⊥ = ⊥ Haskellでは、”∧’ ⇒ ”&&”, ”∨” ⇒ ”||”
論理型上の関数
論理積の別の定義
(∧) :: Bool→ Bool → Bool
False∧ False = False False∧ True = False True∧ True = True True∧ False = False Remark:
⊥ ∧ False = ⊥ False∧ ⊥ = ⊥ True∧ ⊥ = ⊥
論理型上の関数
比較演算子
(==) :: Bool → Bool → Bool x== y = (x ∧ y ) ∨ (not x ∧ not y ) (6=) :: Bool → Bool → Bool x6= y = not (x == y )
Remark:
Haskellでは、”6=” ⇒ ”/=”
同値性を定義したい型には論理型だけではなく、他に多くの 型がある。論理型上の定義はその一例に過ぎない。
論理型上の関数
比較演算子の定義:class/instance
class Eq α where
(==), (6=) :: α → α → Bool x 6= y = not (x == y ) instance Eq Bool where
論理型上の関数
その他の比較演算子の定義
class Eq α ⇒ Ord α where
(<), (≤), (>), (≥) :: α → α → Bool x≤ y = (x < y ) ∨ (x == y ) x> y = not (x ≤ y )
x≥ y = (x > y ) ∨ (x == y ) instance Ord Bool where False< False = False False< True = True True< False = False True< True = False
例
xor
xor :: Bool → Bool → Bool xor p q = (p ∧ not q) ∨ (not p ∧ q)
imply
imply :: Bool → Bool → Bool imply p q = not p ∨ q
leap: 閏年を判定する関数
leap :: Int → Bool leap y = y ‘mod‘ 4 == 0 ∧
自然数型
自然数型はすべての自然数(0, 1, 2, ...) 含む。 data Nat = Zero | Succ Nat Remark:
Natは再帰的に定義されている。
Zero, Succはデータ構成子である。
自然数上の関数定義
加算
(+) :: Nat → Nat → Nat
m+ Zero = m
m+ (Succ n) = Succ (m + n)
自然数上の関数定義
乗算
(×) :: Nat → Nat → Nat
m× Zero = Zero
m× (Succ n) = (m × n) + m ベキ算
(↑) :: Nat → Nat → Nat
m↑ Zero = Succ Zero m↑ Succ n = (m ↑ n) × m
自然数上の関数定義
比較演算
instance Eq Nat where
Zero == Zero = True
Zero == Succ n = False Succ m== Zero = False Succ m== Succ n = m == n instance Ord Nat where
Zero < Zero = False Zero < Succ n = True Succ m< Zero = False Succ m< Succ n = m < n
自然数上の関数定義
比較演算
自然数を次のように定義すれば、比較演算子の定義が自動的に導 出される。
data Nat = Zero | Succ Nat deriving (Eq, Ord)
自然数上の関数定義
減算
(−) :: Nat → Nat → Nat
m− Zero = m
(Succ m) − (Succ n) = m − n
減算は部分関数である。
Succ Zero− Succ (Succ Zero) = { second equation for (-) }
Zero− Succ Zero = { case exhaustion }
自然数上の関数定義
階乗
fact :: Nat → Nat
fact Zero = Succ Zero fact (Succ n) = Succ n × fact n
Fibonacchi関数
fib :: Nat → Nat
fib Zero = Zero
fib (Succ Zero) = Succ Zero
文字型
文字型 Char はASCII (American Standard Code for Information
文字を操作する関数
ord :: Char → Int: 文字を対応するASCII符号の整数に変換
ord ′b′ ⇒ 98
chr :: Int → Char : ASCII符号の整数を対応する文字に変換
chr 98 ⇒ ′b′
関係演算子:文字の間は比較できる.
instance Eq Char where x == y = ord x == ord y instance Ord Char where x < y = ord x < ord y
文字型上の関数の定義
isDigit: 文字が数字であることを判定する関数.
isDigit :: Char → Bool isDigit x = ′0′ ≤ x ∧ x ≤′ 9′
capitalise: 小文字を大文字に変える関数.
captalise :: Char → Char
capitalise x | isLower x = chr (offset + ord x) | otherwise = x
評価例
captalise ′a′
= { definition and isLower ′a′= True }
chr(offset + ord ′a′) = { definition of offset }
chr(ord ′A′− ord ′a′+ ord ′a′) = { arithmetic }
chr(ord ′A′)
= { since chr (ord c) = c for all c }
文字列型
文字列型String は文字の列の集まりである.
{” ”, ”hello”, ”This is a string.”, . . .}
type String = [Char ] ? "a"
"a"
? "Hello World"
"Hello World"
? putStr "Hello World"
文字列上の関数
show :: a → String: 任意の型のデータを文字列に変換
show 100 ⇒ ”100” show True ⇒ ”True”
show (show 100) ⇒ ”\”100\””
++ :: String → String → String: 二つの文字列をつなぐ連接
演算子
”hello” ++ ” ” ++ ”world ” ⇒ ”helloworld ”
整数型とその上の関数
整数型はすべての整数から構成されている。
Int: single precision integer
Integer: arbitrary precision integer
算術演算子 使用例 + (加算) 2 + 3 ⇒ 5 − (減算) 2 − 3 ⇒ −1 ∗ (乗算) 2 ∗ 3 ⇒ 6 / (除算) 3/2 ⇒ 1.5 ˆ (ベキ乗算) 2ˆ3 ⇒ 8 div (整数除算) div 3 2 ⇒ 1 3 ‘div ‘ 2 ⇒ 1 mod (整数除余) mod 5 3 ⇒ 2 5 ‘mod‘ 3 ⇒ 2
関数定義
階乗fact :: Integer → Integer
fact 0 = 1
fact (n + 1) = (n + 1) ∗ fact n
整数の符号を計算する関数
sign :: Int → Int sign n | n> 0 = 1
| n== 0 = 0
浮動小数点数型とその上の関数
浮動小数点数型はすべての浮動小数点数から構成されている.
Float: single precision floating-point numbers
Double: arbitrary precision floating-point numbers
演算子 使用例
+ (加算) 2.3 + 3.3 ⇒ 5.6 − (減算) 2.5 − 3 ⇒ −0.5 ∗ (乗算) 2.5 ∗ 2.5 ⇒ 6.25 / (除算) 3.2/2 ⇒ 1.6
数型上の関数の定義
例: 数の絶対値を返す関数abs.
abs :: Num a⇒ a → a
abs x = if x < 0 then − x else x
読みやすいために,次のように書いてもよい.
abs x | x < 0 = −x | otherwise = x
宿題
Hugsシステムを使って、基本型上の関数をテストする。