[[プログラミング]]

*Haskell [#qe34fb41]
#contents
----
#main_google_AdSense()

**Programming in Haskell [#jfaa53b7]
-Graham Hutton著の「Programming in Haskell」や参考リンクのスライドに関するメモ。
--ちなみにオーム社から翻訳版として「Haskellプログラミング」というタイトルで出版されている。
***第1章 導入 (Introduction) [#g4112448]
-

***第2章 はじめの一歩 (First Steps) [#hc13dafd]
-

***第3章 型とクラス (Types and classes) [#e28d8b9a]

***第4章 関数定義 (Defining functions) [#y4b4b199]

***第5章 リスト内包表記 (List comprehensions) [#rf740073]

***第6章 再帰関数 (Recursive functions) [#w0d93fa7]

***第7章 高階関数 (Higher-order functions) [#o0ebd248]

***第8章 関数型パーサー (Functional parsers) [#y6012088]

***第9章 対話プログラム (Interactive programs) [#pf099b05]

***第10章 型とクラスの定義 (Declaring types and classes) [#o7aa1d34]

***第11章 切符番号遊び (The countdown problem) [#o956c676]

***第12章 遅延評価 (Lazy evaluation) [#gd52ef8a]

***第13章 プログラムの論証 (Reasoning about programs) [#bb50e0f7]


**ふつうのHaskellプログラミング [#s1d34753]
-青木峰郎著の「ふつうのHaskellプログラミング」に関するメモ。
***第1章 [#ia9acaad]
-高階関数
--引数や戻り値として関数を取る関数。
-多相型(polymorphic type)
--Javaでいう総称型(generic type)、C++とかではtemplate
-遅延評価
--式を評価する方式の一つ。最初に数値(引数)の評価では無く、関数の評価を行う。Haskellは遅延評価を基本としている。

***第2章 [#c05a3326]
-mainアクション
--Haskellでは実行するとmainアクションの評価が始まる。
-関数の適用
--以下におなじみの"Hello, World!"のHaskellでの例を示す。Haskellでは、"Hello, World!"に関数putStrLnを適用する(apply)と言い、そのアクションを評価することにより、Hello, Worldが表示される。
 main = putStrLn "Hello, World!"
--ちなみに""中にエスケープシーケンスも代入可能。
-レイアウト
--do式等に記述される後続の複数のアクションは同一のインデントでなければならない。
--Javaでいうブロック構文
--別名、オフサイドルール(off-side rule)と言う。
-束縛
--Haskellでは変数を値で初期化することを、変数を値に束縛する(bind)、という。
--通常のプログラミング言語では値が変数に束縛されるイメージが強いが、Haskellではあくまでも変数は束縛される側である。
--値に束縛された変数から、値を得ることを参照(refer)という。
-$演算子
--関数の戻り値を新たに関数の引数として利用するなど、複数の関数を連続して書きたい場合、従来の言語では括弧のネストが見づらかったが、$演算子を用いることにより、スマートに記述が可能。
 f (g ( h "Hello, World!"))
 f $ g $ h "Hello, World!"
-lines及びunlines関数
--lines :: String -> [String]~
改行区切りの文字列をStringのリストにする。
--unlines :: [String] -> String~
Stringのリストを改行区切りの文字列にする。

--lines関数とは改行区切りの文字列をStringのリストにする関数。
 lines :: String -> [String]
--unlines関数とはStringのリストを改行区切りの文字列にする関数。
 unlines :: [String] -> String
***第3章 [#n0816b65]
-型推論
--言語処理系がその型を前後の文脈などによって自動的に推論する仕組み
-型変数
--例としてlength関数の型は以下のとおりである。
 [a] -> Int
--aに限らず、アルファベットの小文字から始まる変数を、型変数という。ちなみに多相型は型変数を含む型のことである。
--関数が以下のような型の場合、同じである可能性もあるが、aとbは同じでなくても良い。
 [a] -> [b]
-if式
--Haskellでは三項演算子のように、if全体が値を持つ。なのでif式。
 if 条件式 then 式1 else 式2
--とか
 if 条件式 then 式1
           else 式2
--等。

***第4章 [#p94200e1]
-コマンドライン引数取得
--Haskellでコマンドライン引数を取得するには、SystemモジュールのgetArgsアクションを用いる。
--以下はechoコマンドの一例
 import System
 main = do args <- getArgs
           putStrLn $ unwords args
--unwords :: [String]->String~
["a","b","c"]を"a b c"のように、空白区切りにする関数。
--unwords関数とは["a","b","c"]を"a b c"のように、空白区切りにする関数。
 unwords :: [String]->String
-Mainモジュール
--どの変数も、何らかのモジュールに所属している。Haskellではファイルに明示的にモジュールを宣言しない場合、main変数だけが公開されている、Mainモジュールとなる。
-Preludeモジュール
--getContentsや、リストの操作関数は全てPreludeモジュール内で定義されている。原則、暗黙にインポートされる。
-where節
--式で一時的に使用する変数(関数)の定義に用いる。whereの中で定義した変数はwhere節を記述した関数以外からは参照不可。whereの中からは外側の変数を参照可能。
 式 where 定義1
          定義2
--や
 式 where
      定義1
      定義2
--等。
-filter関数
--filter :: (a -> Bool) -> [a] -> [a]~
型がa -> Boolである関数を、リスト[a]の各要素に適用し、Trueである要素のみを取り出す関数。
--filter関数とは型がa -> Boolである関数を、リスト[a]の各要素に適用し、Trueである要素のみを取り出す関数。
 filter :: (a -> Bool) -> [a] -> [a]
-any関数
--any :: (a -> Bool) -> [a] -> Bool~
型がa -> Boolである関数を、リスト[a]の各要素に適用し、いずれかの値がTrueならば、Trueを返す関数。
--any関数とは型がa -> Boolである関数を、リスト[a]の各要素に適用し、いずれかの値がTrueならば、Trueを返す関数。
 any :: (a -> Bool) -> [a] -> Bool

***第5章 [#k2ee8998]
-置き換えモデル(substitution model)
--Haskellにおいて、式の評価は置き換えモデルによって表現される。
--置き換えモデルでは関数の適用は定義で置き換えていくことにより、評価を行う。
--例えば
 f n = n*n
--という定義の関数がある場合、f (1+2)を評価する際に、まずは以下のように置き換えが行われる。
 f (1+2)
 => (1+2)*(1+2)
 => 3*3
--Haskellでは、加算や乗算の演算子も関数であるので、上記式はさらに置き換えが行われ、結果として評価した値を得る。
--この置き換えのプロセスを、簡約と言う。
-最内簡約(innermost reduction)及び最外簡約(outermost reduction)
--置き換えモデルで説明した通り、Haskellでは引数より先に関数の展開が行われる。これを最外簡約と言う。
--一方、C言語等では以下のように簡約される。これを最内簡約と言う。
 f (1+2)
 => f 3
 => 3*3
-グラフ簡約(graph reduction)
--最内簡約の手順では、引数が簡約によって複数箇所に登場する(例えば1+2)。これらの引数に与えられた式の評価は、個別に行われるのではなくあくまでも一度だけ行われ、その結果を共有している。
--このように評価された式を全体で共有しながら簡約する方法を、グラフ簡約と言う。
-遅延評価(lazy evaluation)
--遅延評価とは、式や値などの評価を、実際に必要とするまで行わないことを言う。
--以下のプログラムでは、先頭の100+100のみ評価が行われ、後述の要素の評価は行われない。
 head [100+100,123*321,200-2]
--式や値が必要とされるという判断として、パターンマッチと組み込みの演算の2種類が挙げられる。
-参照透過性(referential transparency)
--参照透過性とは、ある変数や関数等で構成される式があった場合、その式の評価結果は常に一定であるということ。言い換えると、変数もまた一定であり関数も同じ引数である限り一定である。
-副作用
--変数への再代入など、それ以降で評価される式の結果に対して影響を与えることを、副作用と言う。
--Haskellでは、主に画面への出力やキーボードからの入力がそれに相当する。
--入出力を用いた場合でも参照透過性を維持するために、HaskellではIOモナドという、特殊な仕組みを利用する。

***第6章 [#jf340114]
-整除
--Haskellでは整数の除法及び剰余に対して、4種類の演算子が定義されている。
--C言語において、剰余演算子は(a/b)*b+(a%b)=aが成立するような、aとbの組み合わせと定義されている。しかし、aかbのオペランドが負数であった場合、0方向でまるめるか負の無限大方向へまるめるかによって結果が異なる。
--C言語の標準規格であるC99においては、0方向でまるめることが定められている。
--Haskellではこれらに対応して、4種類の演算子が定義されている。
---0方向として: 商 `quot` 剰余 `rem`
---負の無限対方向として: 商 `div` 剰余 `mod`
-null関数
--null関数とはリストが空である場合にTrue、そうでない場合にFalseを返す関数。
 null :: [a] -> Bool

***第7章 [#ydc58e3e]
-コメント
 --コメント例1
 -- コメントの例2
 {-
   コメントの例3
 -}
 --@コメントにならない。--の直後に記号があり、演算子と解釈されてしまう。
-ブレース構文
--doやcase等のコードブロックを{}と;で表す構文
-if式
--条件式。式なのでif式自体が値を持つ。
 ifTest :: Char -> Bool
 ifTest c = if c=='a' then True else False
-パターンマッチ
--パターンマッチとは引数などの値によって場合わけを行うこと。
--変数パターン(variable pattern)
 nothing :: a -> a
 nothing x = x -- 変数パターン
---どんな値に対してもマッチし、変数xをその値に束縛する。
--_パターン、ワイルドカード(wildcard)
 const :: a -> b -> a
 const x _ = x -- _パターン
---constの第2引数に対して_パターンはどんな値にもマッチする。しかし束縛はされない。
--リテラルパターン(literal pattern)
 delTab :: Char -> Char
 delTab '\t' = ' ' -- リテラルパターン
 delTab c = c
--タプルパターン(tuple pattern)
 resTuple :: (Int,Bool) -> String
 resTuple (i,b) = show i ++ "," ++ show b -- タプルパターン
--リストパターン(list pattern)
--データコンストラクタ(data constructor)によるパターン
 last [] = error "last []" -- []は空リストを作成するデータコンストラクタ
 last [x] = x -- リストパターン
 last (_:xs) = last xs -- :は新しいリストを作成するデータコンストラクタ
---リストパターンは変数一つのみのリストに対してマッチする。
--アズパターン(as pattern)
 asTest :: (Int,Bool) -> String
 asTest mix@(i,b) = show mix ++ "," ++ show i ++ "," ++ show b
---タプルパターンに限らず、変数名@パターンによる記述が可能。
-ガード
--任意の式を用いたパターンマッチ。
 strAnalyze :: String -> Bool
 strAnalyze (x:xs)
           | x=='a'    = otherwise
           | x=='b'    = True
           | otherwise = False
--ガードはパターンマッチと合わせて一つの条件であるため、パターンマッチに成功した後のガードが失敗した場合、成功したパターンの次のパターンへマッチが続く。
-case式
 caseTest :: String -> IO ()
 caseTest str = putStr msg
                 where msg = case str of
                               []     -> "error!\n"
                               (x:xs) -> str ++ ", ok\n"
-let式
 f n = let x = n
           y = x + n
           z = y + n
       in x + y + z
--式なのでlet式自体が値を持つ。対して似ているwhere節は値は持たず、変数の定義を行う。
-2項演算子の定義
--既存の演算子以外の新たな演算子を定義する場合、以下のように記述する。ただし使える文字列は特定の記号(e.g. ! # +等)のみであり、新たに定義する演算子を括弧で囲う必要がある。
 (++++) :: Int -> Int -> Int
 x ++++ y = x + y + 2
--また、通常の関数と同様な形式で定義したい場合は以下のように記述する。
 (++++) :: Int -> Int -> Int
 (++++) x y = x + y + 2
--また、関数名などの識別子を用いた2項演算子の定義も以下のように記述可能。
 doubleInc :: Int -> Int -> Int
 x `doubleInc` y = x + y + 2
--関数名などの識別子を用いた2項演算子は以下のように使用する。
 20 `doubleInc` 5
-関数束縛(function binding)
--以下のようなコードは、引数を2乗するという関数(式)に変数fが束縛されている。
 f n = n*n
-パターン束縛(pattern binding)
--let式やwhere式でも、関数定義と同様にパターンを使った変数の束縛が可能
 let (x:xs) = "Hello!"
 in xs

***第8章 [#g39a9bb2]
-無名関数
--関数束縛のように、普通は新しい関数を定義すると同時に変数が束縛されるが、Haskellでは変数の束縛と関数の定義の分離が可能である。
--以下は無名関数を表す式の例である。￥は$ \lambda $と読み、￥の後に続くnが引数のパターンで、->以降が関数の本体である。
 \n -> n*n
--無名関数を用いた通常の関数の定義は以下のとおりである。
 f = \n -> n*n
--普通の関数宣言と同様にパターンマッチが可能である。ただし複数のパターンマッチは不可。
 namelessStr :: (Int,Int) -> String
 namelessStr = \str@(x,y) -> show str
-関数合成(function composition)
--Haskellでは(.)演算子によって関数合成が可能。使用例としてはf . gなど。
 (.) :: (b -> c) -> (a -> b) -> (a -> c)
-関数の部分適用(partial application)
--Haskellでは関数の引数を一部だけ渡して適用しておくことが可能。この場合の戻り値は関数である。これを部分適用という。
--部分適用の考えを用いるとHaskellでは2引数以上の関数は存在せず、2引数以上の関数は全て関数を戻り値として得る高階関数である。
-セクション
--Haskellでは部分適用を行った2項演算子のことを、セクションと言う。
 (+1)
--セクションの使用例を以下に示す
 map (+1) [1,2,3,4,5]
 > [2,3,4,5,6]
-部分適用による変数の削減
--以下に引数として与えられたリストの全要素に、定数を加算する関数を示す。
 incList :: Int->[Int]->[Int]
 incList x xs = map (+x) xs
--この関数を引数がリストで戻り値もリストである関数を返す、高階関数と見ると変数が削減できることがわかる。
 incList :: Int->([Int]->[Int])
 incList x = map (+x)
-ポイントフリースタイル(point-free style)
--関数を関数で定義するコーディングスタイル。
--ここで言うポイントは、合成関数の(.)演算子ではなく、圏論(category theory)の用語。Haskellでは値のことを指す。
--ちなみにincList関数は変数xがあるので、完全なポイントフリースタイルではない。
--ポイントフリースタイルの利点としては、変数が少なくなるのでソースコードの可読性が高くなる。しかし引数がソースコード上から見えるなくなるので、関数の型宣言は不要でもしておくべきである。

***第9章 [#yafc2baf]
-静的型チェック(static type checking)
--コンパイル時に型のチェックを行う。
-型推論
--確実に型がわかる部分をベースに、他の箇所の型を繰り返し自動的に推論していく機能のこと。
--戻り値が多相型で引数も多相型である場合など型の特定が不可能な場合は、::構文によって明示的に型宣言をする必要がある。
-型宣言
--Haskellでは明示的に型宣言を行う場合は::構文を用いる。
 hogeVariable :: Int
--::構文は変数だけではなく、式に対しても使用可能。
 10 :: Integer
-代数的データ型(algebraic type)
--Haskellで新しい型を定義するには、data宣言を用いる。
--data宣言で定義できる型は代数的データ型と言う。
--構造体スタイル
---ローカル部とドメインから構成されるメールアドレス型を定義する。
 data MailAddress = MailAdr String String
---MailAddressが型名及び型コンストラクタと呼び、MailAdrがMailAddress型のデータコンストラクタと呼び、最後の2つのStringはその型が持つフィールドと呼ぶ。
---MailAddress型のデータMailAdr String Stringに対して、パターンマッチが可能である。
 getMailAdr :: MailAddress -> String
 getMailAdr (MailAdr local domain) = local++"@"++domain
---MailAddress型は型名と型コンストラクタが同じであったが、フィールドの型に型変数を用いた型の場合は異なる。
 data MyArray a = CMyArray [a]
---上記例では型名がMyArray aで、MyArrayは型コンストラクタである。また、CMyArrayはデータコンストラクタであるが、文脈によって区別可能であるため型コンストラクタとデータコンストラクタの名前が同じでも良い。
---フィールドラベルを用いて、フィールドにラベルを付けることによって、パターンマッチをするときにラベルでの指定が可能となる。
 data MailAddress = MailAdr {mLocal::String, mDomain::String}
 getMailAdr (MailAdr {mLocal = l, mDomain = d}) = l++"@"++d
---フィールドラベルを用いて代数的データ型を宣言した場合、ラベルと同名の関数が自動的に宣言される。この関数をセレクタといい、セレクタを用いると代数的データ型からセレクタに対応するフィールドの値が取得できる。
 privateAdr :: MailAddress
 privateAdr = MailAdr "example" "vnull.com"
 
 main = do print (mDomain privateAdr) -- vnull.comが表示される。
---フィールドの再構築
 getMailAdr (privateAdr {mLocal = "e.g."}) -- "e.g.@vnull.com"を取得
--列挙型スタイル
---メッセンジャー等のユーザーの在席状況の列挙型を定義する
 data UserState = Online | Offline | Idle | Busy
---OnlineやOfflineなどは、全てデータコンストラクタである。列挙型に限らず、代数的データ型でのデータコンストラクタと関数との違いとしては、上記例のように引数は無くても良く、これ以上簡約できないことである。
--共用型スタイル
---しいて言うならC言語での共用型に似ている使い方らしい。
 data HyperType = NumType Int | StrType String
---上記例ではHyperType型が代数的データ型のNumType IntかStrType Stringのどちらかであるということ。
--再帰的な型
---代数的データ型の宣言に自身を用いることが可能。
 data Stack a = Empty | Push a (Stack a)
-type宣言
--type宣言によって型に別名が付けられる。
 type Pos a = (a,a)
--Pos Int型はプログラム中では2つのInt型のタプルの、(Int,Int)型として扱われる。
--既存の型の別名扱いなので、データコンストラクタは存在しない。
--再帰的な型の定義は不可。
-newtype宣言
--dataのデータコンストラクタ以降に続く型が1個のみ版。
--data宣言された型の評価は正格評価されるが、newtypeは非正格だとか。不確か。
-型クラス
--型の所属するクラス。多相型に制約を付ける場合に用いる。
--制約の付いた多相性をアドホック多相(ad hoc polymorphism)と呼ぶ。
--それに対して制約のない多相性をパラメータ多相(parameter polymorphism)と呼ぶ
-class宣言
--class宣言によってある型クラスの性質を宣言することができる。(e.g. (==)関数が実装されている必要がある、等)
-instance宣言
--ある型がある型クラスのインスタンスであるということを宣言することが出来る。(e.g. (==)関数の実際の実装)

***第10章 [#m9f525af]
-省略

***第11章 [#ufbef66f]
-省略


**メモ [#u038e4a4]
-正格(strict)
--関数fが正格であるとは停止しない式に関数fを適用した場合、その式も停止しないことを言う。そのような関数の性質を正格性と言う。
--Haskellでは遅延評価を基本としているので、非正格な言語である。


**環境設定 [#lfb9b429]
***Haskell mode (emacs) [#u31ea315]
-Hasklellプログラミングをemacsでする為に、Haskell modeが存在する。
-以下のリンクから最新版のアーカイブをダウンロードし、適当な場所に解凍する(e.g. ~/share/emacs/site-lisp/haskell-mode-*.*.*/)
--http://projects.haskell.org/haskellmode-emacs/
-~/.emacsに以下の記述を追加する。
 ;; haskell
 (load "~/share/emacs/site-lisp/haskell-mode-*.*.*/haskell-site-file")
 (setq haskell-program-name "/usr/bin/ghci")
--標準ではインタプリタとしてHugs 98が指定されているので、ghciを使用したいときにhaskell-program-nameを指定する。
-サブウィンドウでインタプリタを起動する
 M-x run-haskell
-編集しているプログラムをインタプリタでロードする
 C-c C-l

**参考リンク [#v1460dec]
--http://www.cs.nott.ac.uk/~gmh/book.html
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS