中級プログラマを目指す

底辺学生プログラマが中級プログラマを目指し、学んだことや思ったことを書き連ねるブログ。まさかり大歓迎。

Haskellに関する備忘録(基礎編)

PCに埋もれていたものを発掘したので備忘録として載っけときます。
あまりに色々省略されすぎていて初心者には何の参考にもならないし、中級者には当たり前すぎて何の参考にもならない。
初心者の中の初心者のときに作ったものなのでマサカリポイント(特に最後の方)が滅茶苦茶あるけど面倒なので修正しません。
修正して欲しいところとかはツイッターで投げて

基礎

関数呼び出し

succ 8

関数名 変数orリテラル

リスト

[1,2,3,4,]
[1..10]
['a'..'x']
[x*y | x<-[1..10], y<-[1..10], x*y>54]

条件でフィルタリングできる

タプル

(1,4,5)

型が違っても使える
各要素が別の型の扱いなので、一緒に使おうとするコンパイルエラー

型変数

型の一般化

型クラス

型の分類
その型がどのような振る舞いを持つかを定義することによって分類
モナドとか
(Eq a)>=の>=前は型制約とか呼ぶ(モナドだけど)

パターンマッチ

型引数による評価を分けるというべきか

luccky:: Int -> String
luccky 7 = "luccky"
luccky _ = "unluccky"

上から準に評価される
タプルのパターンマッチも可能

addVectors:: (Double, Double)->(Double, Double)->(Double, Double)
addVectors (x1, y1) (x2, y2) = (x1+x2, y1+y2)

リスト内包表記でも

let xs = [(1,3), (1,4), (4,6), (2,3)]
[a+b | (a,b)<-xs]

一致しないタプルは飛ばされる

リストの扱いでx:xs,x:_もよく使うが要素数1以上じゃないといけないので注意
all@x:xsで分割前のリスト(all)も使用可能(asパターン)

ガード

具体的な値によって場合分け

bmiTell::Double->String
bmiTell bmi
  | bmi <= 18.5 = "underweight"
  | bmi <= 25.0 = "normal"
  | bmi <= 30.0 = "fat"
  | otherwise   = "fxxk!"

otherwiseないとSyntax Error

where

局所変数の定義
スコープは関数内
関数の終わりでのみ定義可能

bmiTell::Double->String
bmiTell weight height
  | bmi <= 18.5 = "underweight"
  | bmi <= 25.0 = "normal"
  | bmi <= 30.0 = "fat"
  | otherwise   = "fxxk!"
  where bmi = weight /height ^2

関数型言語なので変数定義できるということは、関数の定義も可能
パターンマッチも使える

let

式の定義
どこでも定義可能

let binding in expression  

bindingで変数を定義し、それを利用した式をexpressionに書く
;で改行できる
パターンマッチも使える
let式内で束縛した変数はlet式内でしか使えない(スコープの制限)

case

式の定義
(式なので)どこでも使えるパターンマッチ

case expression of pattern -> result
                   pattern -> result

の形で定義

再帰

説明不要
パターンマッチをつかう

fact::Integer -> Integer
fact 0 = 1
fact n = n * fact (n - 1)

クイックソートがこんなに簡単に(クイックソートではない問題は帰って)

quicksort::(Ord a) >= [a] -> [a]
quicksort [] = []
quicksort (x:xs) = 
  let smallerOrEqual = [a | a <- xs, a <= x]
      larger = [a | a <- xs, a > x]
  in  quicksort smallerOrEqual ++ [x] ++ larger

関数定義

シグネチャ(定義)+実装

Add1:: Int -> Int --型シグネチャ
Add1 n = n + 1    --実装

カリー化関数

複数引数の関数も1つの引数の関数の合成にできる

部分適用

複数引数の関数に1つ以上の引数を与えることで関数の引数の数をかえる
(f 1)などしてつかう

高階関数

引数に関数をとる、関数を出力する、あるいはその両方を満たす関数
zipWithなど

zipWith'::(a->b->c)->[a]->[b]->[c]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

ラムダ式

関数リテラル
最強のチューリング完全

\x -> \y -> \z -> x + y + z
\x y z -> x + y + z

畳み込み

説明不要
中間値記法使ったほうがわかりやすいし、木を書くともっとわかりやすい
右と左があるけどfoldlはうんち(遅延評価なのでスタックオーバーフローする)なのでfold'(正確評価,Data.List)つかってね

関数適用

カッコめんどくさいときに
$を使い給え
優先順位最低なのに注意

f(g(h(x)))
f $ g $ h $ x

関数合成

さっきの例は関数合成できる(.)

f.g.h $ x

こう書くとf,g,hが合成されたのちxが適用される
部分適用(max 50など)は関数合成よりも優先度が高いので注意

モジュール

import Data.List
import Data.List (nub, sort) --一部の関数だけimport
import Data.List hiding nub  --一部の関数以外import
import qualitified Data.Map as Map --M.関数名で呼び出しさせるようにする(重複の回避)

モジュールは以下のように作る

module Geometry
( sphereVolume --公開する関数名
, sphereArea
) where

--実装

新しい型の定義

data Bool = False | True  --いずれかになる
data Circle = Float Float --いずれももつ

deriving (Show)などとかけば自動的にその型クラスのインスタンスになる
(実装を書く必要があるがShowは自動実装)
Circleは引数に数値をとる
これを値コンストラクタという
値コンストラクタは関数と同様に扱うことができる(部分適用など)
モジュールとして公開する場合はShape(..)とする

レコード構文

データ構造をもっと見やすく

data Person = Person { firstName :: String
                     , lastName :: String
                     , age :: Int } deriving (Show)

型コンストラクタ

値コンストラクトをもっと抽象化する
型引数によって実装

data Maybe a = Nothing | Just a

データ宣言に型クラス制約は決して付けないこと(コーディング規約)

インスタンスの自動導出

deriving (Show)とかOrdの場合列挙した順になる

型シノニム

別名

type String = [Char]
type AssocList k v = [(k,v)] --型シノニムも型引数を取れる

型宣言の再帰的な定義

型宣言は再帰的に定義できる

infixr 5 :-: --結合性の定義 演算子の優先順位を定義する *が7, +が6
data List a = Empty | a :-: (List a) deriving (Show, Read, Eq, Ord)

パターンマッチとは型コンストラクタをマッチさせること(x:-:xsとなる)

型クラスの定義

ある型がある型クラスのインスタンスであるとはその型クラスが定義するメソッドが型に対して使えrつということ

class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool
  x == y = not (x /= y)  --デフォルト実装(相互再帰)
  x /= y = not (x == y)

インスタンスは次のように定義

data TrafficLight = Red | Yellow | Green
instance Eq TrafficLight where
  Red == Red = True
  Green == Green = True
  Yellow == Yellow = True
  _ == _ = False

パターンマッチで定義
相互再帰によりどちらか片方定義すればもう片方が導出される

多相型(Maybeのような具体的な値でないもの)を型引数にしたい場合は次のようにする

instance (Eq m) => Eq (Maybe m) where
  Just x == Just y = x == y
  Nothing ==Nothing = True
  _ == _ = False

Maybe mは部分適用で型引数を1つ取る型コンストラクタが具体系になる
mがEqのインスタンスである必要があるため型制約をつける

サブクラス化

型クラスの型引数を制限

class (Eq a) => Num a where
  ...

型クラスNumの定義ができる方をEqのインスタンスに限定

Functor

型クラスとして関手は実装される

class Functor f where
  fmap :: (a -> b) -> f a -> f b

つまり型引数fは対象関数、fmapは射関数
またHask圏はデカルト閉圏なので関手は射で表せる
(->)はFunctorのインスタンスってこと

Kind(種類)

型コンストラクタに関しても型を考えることができるぜ
具体系:* Intとか
具体系を取って具体系を返す型コンストラクタ * -> * Maybeとか
Maybe IntはIntが適用された具体系
Functor fは * -> * (圏論でいう対象関数なので当然)

do記法

IOアクションに於けるSyntax Sugar
普通の手続きっぽくかける

main = do
  putStrLn "Write First Name" --標準出力
  firstName <- getLine --標準入力
  putStrLn "Write Last Name"
  lastName <- getLine
  let bigFistName = map toUpper firstName
      bigLastName = map toUpper lastName
  putStrLn $ "hey " ++ bigFistName ++ " "
                    ++ bigLastName
                    ++ ", how are you?"

<-で変数に束縛
IOアクションでない純粋な関数での束縛はletを使う(インデントは揃える)

do記法は実際的には式なのでどこでも使用できる(letと一緒)

ファイルの読み書き

System.IOのreadFile, writeFile, appendFile関数を使う
基本的に直感的名前をしている

コマンドライン引数

System.EnvironmentのgetArgs, getProgNameをつかう(後者はプログラムの名前を得る)

乱数

random (mkStdGen 100)で可能
100を変えないと全く同じ値がでる
返ってくるのは3つのタプルで最初の要素がお望みのもの、次の要素次の乱数生成に使う

アプリカティブファンクタ

ファンクタの強いやつ
どちらかと言うとモナドの弱いやつ

class (Functor f) => Applicative f where
  pure :: a -> f a --return
  (<*>) :: f (a -> b) -> f a -> f b --bind

既存の型から新しい型へ(newtype)

dataよりも高速だが1つの値コンストラクタしか持てない

newtype CharList = CharList { getCharList :: [Char]} deriving (Show, Eq)  --レコード構文

型クラスインスタンスを作るときに使う
例:タプルの第一要素の変更をFunctorに

newtype Pair b a = Pair { getPair :: (b,a)}
instance Functor (Pair c) where
  fmap f (Pair (x,y)) = Pair ( f x, y)

newtypeすることによってパターンマッチできるようにする
dataで定義された型は呼び出された際に使わない部分も評価されるが、
newtypeの場合は評価されない(dataよりも怠惰)
newtype宣言でレコード構文を使うと、元の型と相互変換する関数が生成される

モノイド

二項演算とその演算に対する単位元からなる構造

class Monoid m where
  mempty :: m  --単位元
  mappend :: m -> m -> m  --二項演算
  mconcat :: [m] -> m  --モノイド対象のリストに対する演算
  mconcat = foldr maapend mempty  --デフォルト実装

モノイド則を満たす必要がある
単位元律、交換法則、結合法則
モノイドはFoldableなので、Data.Foldableのfold関数で畳み込める(はず)
Preludeのfoldはリストだけだぞ気をつけろ!

モナド

自己関手の圏におけるモノイド対象だよ。何か問題でも?
任意の自己関手T: X -> X は合成において閉じている
下記の自然変換
eta: I_X -> T mu: T2 -> T (T,mu,eta)のトリプルにおいて、下記の図を可換にするもの
Tmu etaT Teta
T3 ——–> T2 IT——>T2<——–TI
| | || | || |
| muT |muT || | mu || |
|/ Tmu |/ || |/ || |/
T2———> T T=======T =========T

class Monad m where
  return :: a -> m a  --join T eta a
  (>>=) :: m a -> (a -> m b) -> m b --クライスリ圏のリフト
  (>>) :: m a -> m b -> m b  --必ずm b を返す
  x >> y = x >>= \_ -> y

  fail :: String -> m a
  fail msg = error msg

>>=で同じモナド同士の結合ができる
文脈の結合と言うべきか
do記法を用いればlet式以外では文脈が維持される

MonadPlusとguard関数

MonadPlusでモナドかつモノイドが定義できる
mzeroが単位元、mplusが二項演算
リストはMonadPlusのインスタンスにできる
guard関数はフィルタリングに使える
guardが失敗すれば全部失敗、成功すれば>>で何か取り出せる

guard (5 > 2) >> return "cool"

リスト内包表記のフィルタリングの機能を実装してる

モナド

return x >>= f = f x  --左恒等性
m >>= return = m  --右恒等性
(m >>= f) >>= g = m >>= (\x -> f x >>= g)  --結合則

<=<を使うと便利

(<=<) :: (Monad m) => (b -> m c) -> (a -> m b) -> (a -> mc)
f <=< g = (\x -> g x >>= f)

普通の値からモナドを返す関数の結合に使える

いろんなモナド

IO, List, Maybeなど

  • Writer ログの追記 writer (x, log)で追記
    do記法で使ったほうが良さそう
    tellでログだけ追記できる
    リストで使う際は気をつける(くっそ遅くなる)
    差分リストを使うと良い

  • Reader 関数のこと(書くのが面倒)

  • State s -> (a,s)
    sは状態の型、aは状態付き計算の結果の型
    do記法を使うがよろし
    runStateで値を取り出す(a,s)の形
    evalStateで値だけ、execStateで状態だけ取り出せる
    do式内ではget, putで状態を操れる
    stateでStateモナドを返す関数を作れる

  • Either 例外処理に
    エラーの理由をLeftで追記

モナド変換子

複数のモナドを同時に使いたいときに
モナドモナドを扱う
通常のモナドにTを付けたもの(StateT,ReaderT,ListT,WriterT)
使い方は通常通り
モナド変換子が付いたものの中で他のモナドが使えるようになる

f:: s-> IO(Int,s)
f s = return (1,s)

a:: StateT s IO Int
a = StateT f  --関数から生成

main = do
  print =<< f ()
  print =<< runStateT a () --StateTを評価

実際的にはモナドモナドのreturnである(liftと一緒)

lift

モナド変換子を作る
モナドモナドにおけるjoin
StateTの中にIOを入れるイメージ
あるいはモナドスタックを考え、関数を持ち上げるイメージ

lift :: (Monad m) => m a -> t m a

使用例

a :: StateT String IO ()
a = do
    v <- get
    lift $ print v  --StateモナドvからIOモナドを作っている

main = do
  runStateT a "hello"

複数のモナドモナドした場合liftは必要な数やる(当たり前)
liftIOは一気に一番上まで行く

liftM

関数をモナドにくるんで適用している
関数を持ち上げるイメージ
引数が2つの場合はliftM2
>>=<*>と実質的に同じ

もっとモナドモナド

モナドモナドなら色々あるはず……

class MMonad t where
  lift :: Monad m => m a -> t m a
  squash :: (Monad m, MMonad t) => t (t m) a -> t m a
  hoist :: (Monad m, MFunctor t) => (forall a. m a -> n a) -> t m b -> t n b

Control.Monad.Morph
mmorphはモナドの性質を保存する自然変換であるモナドモーフィズムのこと

filterM

条件式とリストを取って、リストを返す関数

filterM :: (a -> Bool) -> [a] -> [a]

foldM

モナド版畳み込み

foldM :: (a -> b -> m a) -> a -> [b] -> m a

モナディック関数の合成

<=<を使えば良い

残り:GHC拡張関連、rank2types,category,allowなど

目指すべき中級プログラマとはなんのなのか?

どうも、るじゃんどるです。

昔から趣味のプログラミングをやっていたんですが、 最近になって本格的にプログラマになりたいと思ったので それに必要な勉強をしようと思います。

お前が目指すプログラマのジャンルは何なの?

コード書いてるだけで幸せを感じるのでなんでも良いといえばなんでも。 知識はフルスタックレベルを目指す。

現在のスペックは?

一言で言えばクソ雑魚。

使用可能なプログラミング言語

C99 : H8, AVRのプログラムに使用。2足歩行ロボットや時計などの電子工作に主に使っていた。
C++99 : 簡単な3Dの格闘ゲームRPGを作成。もはや昔のこと過ぎて半ば忘れかけている。
Python3 : クローリング、スクレイピング機械学習数値計算など。最近はもっぱらこれを使っている。
Swift3.0 : 小説家になろうのアプリを作成するも、お金がなく公開できず。

ちなみにC,C++が99なのは学んだとき*1にそれが主流だったせい。

知識

応用情報程度の知識。

目標とすべき知識、技術レベルはどこなのか?

中級プログラマと言ってもその幅は広いので、個人的な中級プログラマの知識、技術レベルを列挙してみる。

  • 複数の言語を扱える。
  • 使用している言語の仕様を理解している*2
  • 使用している言語がどのように処理されているか理解している。
  • クソコードを書かない。
  • テストが書ける。
  • リファクタリングができる。
  • バージョン管理システムが扱える。
  • データベースについて理解している。(SQL, NoSQLのどちらについても)
  • オブジェクト指向でプログラミングできる。
  • アセンブラが読める。
  • 計算機の構造を理解している。
  • データ構造とアルゴリズムについて理解している。
  • ネットワークについて理解している。
  • サーバについて理解している。
  • 使用している言語のコンパイラを実装できる。
  • OSを作成できる。
  • アプリケーション・アーキテクチャに精通している。
  • 関数型言語を扱える。
  • デザインパターンに精通している。
  • チームで開発できる。
  • 使用している言語の有名なライブラリやフレームワークを扱える。
  • デバッグができる。
  • ドキュメントが書ける。
  • コミュニケーション能力がある。
  • 英語ができる。

目指せ!中級プログラマ

ということで上の知識と技術がつくまで勉強します。
勉強した内容の解説をこのブログに載せる予定。
目下Haskellの勉強中なので、それで簡単なWebAPIでも作るか……
終わったらC/C++99を14にアップデートしなきゃ。

上の中級プログラマのできなきゃいけないことに異議申し立てがあればコメントで教えてください。

*1:10年前のことである。当時小学生だった自分にお高いプログラミングの本を買うお金があるはずもなく、近くの図書館に借りに行くしかなかった。

*2:ダジャレではない