読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

プログラミングHaskell第1章(導入) まとめ

プログラミングHaskellでは実際のHaskellで入力する記号ではなく数学記号で記述されている。
否定とノットイコールの入力方法が慣れ親しんでるプログラミング言語とは違う。

数学記号 意味 入力方法
 \to 変換する ->
 \Rightarrow クラス制約 =>
 \geq 以上 >=
 \leq 以下 <=
 \not = 等しくない /=
 \wedge かつ &&
 \vee または ||
¬ 否定 not
 \uparrow 累乗 ^
 \circ 合成 .
 \lambda 無名関数 \
++ 連結 ++
 \leftarrow 引き出す <-
 \ll = 順序付け >>=
+++ 選択 +++

連結、選択、順序付けの記号の出し方わからなかった。。。

Haskellプログラム例1:リストの要素の総和

リストの合計を求める例。リストは[]で表現される。
 --コメントアウト(これはなれないと見づらいなあ)。
xがリストの最初の要素。xsが残りの要素を示す。
= 0としているところが基底。0は加算に対して単位元だから空リストに対しては0を返すようにする。

mysum::Num a => [a] -> a -- 自動的に推論されるので書かなくても良い
mysum [] = 0
mysum (x:xs) = x + mysum xs
 
main = print $ mysum [1, 2, 3] -- sum [1..3]

通常は、標準ライブラリのsum, [..]を使えば良い。

Haskellでは、全ての関数が、型を持つ。明記しなければ、関数の型は自動的に推論される。
上の例だと、任意の数値(Num)型aに対し、型aのリストを型aの数値に変換することを示している。

Haskellプログラム例2:クイックソート

++はリストの連結を示す。

qsort [] = []
qsort (p:xs) = qsort smaller ++ [p] ++ qsort larger
        where
                smaller = [a|a <- xs, a <= p]
                larger = [b|b <- xs, b > p]

main =  print $ qsort [4,1,3,6,7,9,5,2,4,5,6,-1]

とても分かりやすい(小並感)。
javaで実装したクイックソート(http://kanetai.hatenablog.com/entry/20130226/1361895000)と比べても結構短くかける。
※ピボットの選び方や、smller, largerの分け方に違いはある。
上のhaskellの例は、リストの生成、結合をしまくるので非効率的だけど可読性は非常に高い。

この場合型は、

qsort::Ord a => [a] -> [a]

になる。順序を持つ型aに対して、型aのリストから型aのリストを返す。
従って、数値以外でも適用可能で、例えば文字のソートもできる。

main =  print $ qsort "afeb"

ちなみに練習問題になってますが、<=のところを<にしたらピボットの重複要素消えますね(smaller, largerのどちらにも入らないので)。

通常、Data.listのsortで十分

import Data.List
sort [4,1,3,6,7,9,5,2,4,5,6,-1]

ところで、eclipseシンタックスハイライトが全く機能していない気がするんだが、なんでだろう。