PROGRAMMING IN HASKELL

Slides:



Advertisements
Similar presentations
プログラミング言語論 第3回 BNF 記法について(演習付き) 篠埜 功. 構文の記述 プログラミング言語の構文はどのように定式化できるか? 例1 : for ループの中に for ループが書ける。 for (i=0; i
Advertisements

2.5 プログラムの構成要素 (1)文字セット ① ASCII ( American Standard Code for Interchange ) JIS コードと同じ ② EBCDIC ( Extended Binary Coded Decimal for Information Code ) 1.
プログラミング言語論 第10回(演習) 情報工学科 木村昌臣   篠埜 功.
(Rubyistのための) 超音速:ML入門
プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
プログラムのパタン演習 解説.
プログラミング言語としてのR 情報知能学科 白井 英俊.
ソフトウェア基礎科学 授業資料: 論理関係(logical relations)のお話
はじめに 教科書 プログラミングHaskell Graham Hutton (著), 山本 和彦 (翻訳) オーム社、全 232 ページ
情報基礎A 第10週 プログラミング入門 VBAの基本文法2 データ型・If ~Then~Else
型宣言 (Type Declarations)
プログラミング言語論 第6回 型 情報工学科 篠埜 功.
型宣言(Type Declarations)
プログラミング言語論 第4回 式の構文、式の評価
情報基礎A 第7週 プログラミング入門 VBAの基本文法2 データ型・If ~Then~Else
条件式 (Conditional Expressions)
言語処理系(5) 金子敬一.
プログラミング演習Ⅰ 課題2 10進数と2進数 2回目.
ML 演習 第 7 回 新井淳也、中村宇佑、前田俊行 2011/05/31.
プログラミング言語論 第12回 関数型プログラミング 情報工学科 篠埜 功.
PROGRAMMING IN HASKELL
4 ソフトウェア工学 Software Engineering 抽象データ型 ABSTRACT DATA TYPE.
PROGRAMMING IN HASKELL
PROGRAMMING IN HASKELL
PROGRAMMING IN HASKELL
プログラミング言語論 第9回 Hoare論理の練習問題 手続きの引数機構 変数の有効範囲
第10回関数 Ⅱ (ローカル変数とスコープ).
PROGRAMMING IN HASKELL
PROGRAMMING IN HASKELL
お仕事にまったく役にたたない内容のコードレビューやりたいと思います。
国立情報学研究所 ソフトウェア研究系 助教授/
 型推論1(単相型) 2007.
4.リスト,シンボル,文字列.
フロントエンドとバックエンドのインターフェース
第5章 計算とプログラム 本章で説明すること ・計算の概観と記述法 ・代表的な計算モデル ・プログラムとプログラム言語.
C言語 はじめに 2016年 吉田研究室.
15.cons と種々のデータ構造.
Type Systems and Programming Languages
プログラミング 3 2 次元配列.
基礎プログラミング演習 第6回.
第6回レポート解説 条件1 条件2 条件3 月の入力 月、日、曜日の表示 日の入力 曜日の入力
オブジェクト指向言語論 第三回 知能情報学部 新田直也.
プログラミング入門2 第6回 関数 情報工学科 篠埜 功.
第14回 前半:ラムダ計算(演習付) 後半:小テスト
国立情報学研究所 ソフトウェア研究系 助教授/
PROGRAMMING IN HASKELL
プログラミング言語論 第10回 情報工学科 篠埜 功.
~sumii/class/proenb2010/ml2/
復習 if ~ 選択制御文(条件分岐) カッコが必要 true 条件 false 真(true)なら この中が aを2倍する 実行される
情報処理Ⅱ 第7回 2004年11月16日(火).
5. 任意長の合成データ:リスト プログラミング論I.
PROGRAMMING IN HASKELL
関数型言語の基礎 型なしl計算 型理論 構成的プログラミング GUIにあらわれる関数概念 PBD VL
~sumii/class/proenb2010/ml5/
プログラミング基礎a 第3回 C言語によるプログラミング入門 データ入力
オブジェクト指向言語論 第二回 知能情報学部 新田直也.
コンパイラ 2012年10月11日
プログラミング 4 文字列.
プログラミング入門2 第6回 関数 情報工学科 篠埜 功.
Haskell Programming Language
オブジェクト指向言語論 第七回 知能情報学部 新田直也.
オブジェクト指向言語論 第七回 知能情報学部 新田直也.
情報処理Ⅱ 2005年11月25日(金).
オブジェクト指向言語論 第三回 知能情報学部 新田直也.
プログラミング基礎a 第5回 C言語によるプログラミング入門 配列と文字列
情報処理Ⅱ 小テスト 2005年2月1日(火).
プログラミング基礎a 第3回 C言語によるプログラミング入門 データ入力
復習 いろいろな変数型(2) char 1バイト → 英数字1文字を入れるのにぴったり アスキーコード → 付録 int
プログラミング言語論 プログラミング言語論 演習7 解答と解説 演習7 解答と解説 1.
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
Presentation transcript:

PROGRAMMING IN HASKELL Chapter 4 - Defining Functions 関数定義 愛知県立大学 情報科学部 計算機言語論(山本晋一郎・大久保弘崇、2011年)講義資料 オリジナルは http://www.cs.nott.ac.uk/~gmh/book.html を参照のこと

条件式(Conditional Expressions) 注意: 条件文ではない 他のプログラミング言語と同様に、条件式を用いて関数を定義 abs :: Int  Int abs n = if n  0 then n else -n abs は整数 n を取り、n が非負のとき n そのものを返し、それ以外は –n を返す

Haskell では、条件式は必ず else 部を持つため、入れ子になった条件式の曖昧さ(dangling else)は生じない 条件式の入れ子: signum :: Int  Int signum n = if n < 0 then -1 else if n == 0 then 0 else 1 注意: Haskell では、条件式は必ず else 部を持つため、入れ子になった条件式の曖昧さ(dangling else)は生じない

ガード付き等式(Guarded Equations) 条件式の代わりに、ガード式を用いて関数を定義 abs n | n  0 = n | otherwise = -n 前ページの定義と同じ、ただしガード式を使用

ガード式を用いると、複数の場合分けによる関数定義が読みやすくなる: signum n | n < 0 = -1 | n == 0 = 0 | otherwise = 1 注意: 「その他の場合」を表す otherwise は Prelude において True と定義されている

パターンマッチング(Pattern Matching) 関数の多くは、引数に対するパターンマッチにより、簡潔かつ直観的に定義できる not :: Bool  Bool not False = True not True = False not は False を True へ、True を False へ写像

関数定義におけるパターンマッチの書き方は一通りとは限らない。例えば、 (&&) :: Bool  Bool  Bool True && True = True True && False = False False && True = False False && False = False は、よりコンパクトにも書ける。 True && True = True _ && _ = False

次の定義はより効率的である。1つめの引数が False のとき、2 つめの引数を評価しない: True && b = b False && _ = False 注意: 下線文字(アンダースコア) “_” は任意の値とマッチするワイルドカード

パターンは記述順(上から下)にマッチを試される。例えば、次の定義は常に False を返す: True && True = True パターン中に同じ変数を 2 回使うことはできない。例えば、次の定義はエラーとなる: b && b = b _ && _ = False

リストパターン(List Patterns) 空でないリストは、内部的には “cons” と呼ばれる演算子 : (コロン文字)を繰り返し用いて構成されている [1,2,3,4] 1:(2:(3:(4:[]))) を意味する。 1:2:3:4:[] とも書ける(: は右結合)。

リストに対する関数は x:xs という形のパターンで定義できる head :: [a]  a head (x:_) = x tail :: [a]  [a] tail (_:xs) = xs head と tail は空でないリストをそれぞれ、 先頭要素、残りのリストに写像する

x:xs パターンは非空リストにのみマッチする: 関数の典型的なパターンマッチ: f [] = … f (x:xs) = … 注意: x:xs パターンは非空リストにのみマッチする: > head [] Error x:xs パターンは括弧でくくる必要がある。関数適用はリスト構成子 “:” より優先度が高い。例えば、次の定義はエラーになる: head x:_ = x

Integer Patterns (非推奨) Haskell 2010 で使用禁止 Integer Patterns (非推奨) 数学と同様に、整数上の関数を定義するのに n+k パターンが使える。ここで n は整数変数で、k は正の整数定数。 pred :: Int  Int pred (n+1) = n pred は正の整数を 1 つ小さな値に写像する

n+k パターンは k 以上の整数にのみマッチする 注意: n+k パターンは k 以上の整数にのみマッチする > pred 0 Error n+k パターンは括弧でくくる必要がある。関数適用は加算の “+” より優先度が高い。例えば、次の定義はエラーになる: pred n+1 = n

式(Lambda Expressions) 式を用いて、名前を付けずに関数を構成できる x  x+x 「数 x を取り x+x を結果として返す」無名関数を表す

注意: 記号  はギリシャ文字の「ラムダ」で、キーボードからはバックスラッシュ “\” で入力する 数学では、無名関数を記号  を用いて x  x+x のように表す Haskell で無名関数の表記に  を用いるのは算法からきている。 算法は Haskell が基礎を置いている関数理論である。

式が有用な理由 式はカリー化された関数の形式的な意味付けに用いられる 例: カリー化された add の意味 add x y = x+y

式は、関数を結果として返す関数を定義するときにも用いられる 例: 2引数の関数: 第2引数は無視し、第1引数を返す const :: a  b  a const x _ = x より自然に 1引数の関数: 引数が何であっても x を返す関数を返す const :: a  (b  a) const x = _  x

式は、1 回しか参照されない関数に名前を付けるのを避けるためにも用いられる 例: odds 4 = map f [0..3] where … = map f [0, 1, 2, 3] where … = [1, 3, 5, 7] odds n = map f [0..n-1] where f x = x*2 + 1 よりシンプルに odds n = map (x  x*2 + 1) [0..n-1]

セクション 演算子が 2 つの引数の間に置かれているとき、処理系内部では、括弧を付けて演算子をカリー化関数にして引数の前に置くように変換される 例: > 1+2 3 > (+) 1 2

この変換において、演算子の引数を括弧の中に含んでもよい 例: > (1+) 2 3 > (+2) 1 一般に、演算子  と引数 x, y に対して、3種類の関数 (), (x), (y) をセクションと呼ぶ

セクションが有用な理由 セクションを用いると、単純だが有用な関数を簡潔に定義できる 例: - successor function セクションを用いると、単純だが有用な関数を簡潔に定義できる 例: - successor function - reciprocation function (逆数関数) - doubling function - halving function (1+) (*2) (/2) (1/)

まとめ(4章) ガード式 abs n | n  0 = n | otherwise = -n パターンマッチング リストパターン head (x:_) = x 式: 関数の記法、名前を付けずに関数を構成 カリー化された関数の意味 add x y = x+y の意味は add = x  (y  x+y) 関数を結果として返す関数 const :: a  (b  a) const x = _  x セクション: 演算子を関数にする x  y に対して関数 (), (x), (y) 関数の典型的なパターンマッチ: f [] = … f (x:xs) = …