バージョン管理：ghcup使ってる

marbull

Haskellでは，慣習として，引数がリストである場合には名前の末尾にsを付けて複数の値を含んでいる可能性を示す．数値のリストは，ns，任意の値のリストは，xs

marbull

Haskellでは，式を評価する前に型が検査されるので，評価の際には型エラーが起きない．この意味でHaskellプログラムは，型安全である．

marbull

:: という記号は、「の型を持つ。」と読む。

marbull

型クラスは、OOPのクラスとは同じではないということに注意。

marbull

Stringは[Char]の単なる別名

marbull

factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n -1)

marbull

Haskellプログラマはx:xsというパターンを、再帰関数と一緒によく使う。

marbull

条件式

abs :: Int -> Int
abs n = if n >= 0 then n else - n

ガード付きの等式

abs :: (Ord p, Num p) => p -> p
abs n
  | n >= 0 = n
  | otherwise = - n

marbull

ガード付きの等式は条件式と比べて、条件が多くなった時に読みやすい点が優れている。

marbull

多くの関数は、パターンマッチを使うことで簡潔かつ直感的に定義できる。

marbull

not :: Bool -> Bool
not True = False
not False = True

marbull

ラムダ式はカリー化された関数の形式的な意味づけに利用できる。
「関数を返す関数」を定義するときに、カリー化された結果ではなく本来の関数が結果として返される。
一度しか参照されない関数の名前付けを避けるためにも利用できる。

marbull

add :: Int -> Int -> Int
add x y = x + y

add :: Int -> (Int -> Int)
add = \x -> (\y -> x + y)

marbull

バッククオートによる中置記法は，関数呼び出しだけでなく，関数定義でも使える．それによりコードが読みやすくなる時がある．

myCompare :: (Ord a) => a -> a -> Ordering
a `myCompare` b
  | a > b = GT
  | a == b = EQ
  | otherwise = LT

marbull

Haskellは計算を実行するステップをコンピュータに示さない．ほしい結果が何であるかを直接定義する．そのために再帰的な方法をよく使う．

marbull

-- 再帰的に定義したmaximum'関数
maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list!"
maximum' [x] = x
maximum' (x : xs) = max x (maximum' xs)

-- maximum' [2,5,1]
-- max 2 (maxium' [5,1])
-- max 2 (max 5 (maximum' [1]))
-- max 2 (max 5 1)
-- max 2 5
-- 5

maximum'を，[2,5,1]で呼び出すと，最初の２パターンには合致しない．
３パターン目に合致して，（x:xs）のとおり，2:[5,1]となる．（1回目）
次は，maximum' [5, 1]で呼び出される，最初の２パターンには合致しない．
３パターン目に合致して，（x:xs）のとおり，5:[1]となる．（２回目）
次は，maximum' [1]で呼び出される，２パターン目に合致して, 1が返る．

max 5 1 となり，５が返る，max 2 5となり，5が返る．

marbull

reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x : xs) = reverse' xs ++ [x]

-- reverse' [3,2,1]
-- reverse' [2,1] ++ [3]
-- (reverse' [1] ++ [2]) ++ [3]
-- ((reverse' [] ++ [1]) ++ [2]) ++ [3]
-- (([] ++ [1]) ++ [2]) ++ [3]
-- ([1] ++ [2]) ++ [3]
-- [1,2,3]

marbull

zip' :: [a] -> [b] -> [(a, b)]
zip' _ [] = []
zip' [] _ = []
zip' (x : xs) (y : ys) = (x, y) : zip' xs ys

-- zip' [1,2,3] ['a','b','c']
-- (1, 'a') : zip' [2,3] ['b','c']
-- (1, 'a') : (2, 'b') : zip' [3] ['c']
-- (1, 'a') : (2, 'b') : (3, 'c') : zip' [] []
-- (1, 'a') : (2, 'b') : (3, 'c') : []

marbull

elem' :: (Eq a) => a -> [a] -> Bool
elem' a [] = False
elem' a (x : xs)
  | a == x = True
  | otherwise = a `elem'` xs

-- elem' 1 [3,2,1]
-- elem' 1 (3 : [2,1]) 1 /= 3
-- 1 `elem'` [2,1]
-- 1 elem'` (2 : [1]) 1 /= 2
-- 1 `elem'` [1]
-- 1 `elem'` (1 : []) 1 == 1 -> True

marbull

-- 負でない整数の階乗を返す関数
fac :: Int -> Int
fac n = product [1 .. n]

-- 上記を再帰的に定義したfac'関数
fac' :: Int -> Int
fac' 0 = 1
fac' n = n * fac' (n - 1)

-- fac' 3
-- 3 * fac' 2
-- 3 * (2 * fac' 1)
-- 3 * (2 * (1 * fac' 0))
-- 3 * (2 * (1 * 1))
-- 3 * (2 * 1)
-- 3 * 2
-- 6

marbull

product' :: Num a => [a] -> a
product' [] = 1
product' (n : ns) = n * product' ns

-- product' [2,3,4]
-- 2 * product' [3,4]
-- 2 * (3 * product' [4])
-- 2 * (3 * (4 * product' []))
-- 2 * (3 * (4 * 1))
-- 24

marbull

insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y : ys)
  | x <= y = x : y : ys
  | otherwise = y : insert x ys

-- insert 3 [1,2,4,5]
-- 1 : insert 3 [2,4,5]
-- 1 : 2 : insert 3 [4,5]
-- 1 : 2 : 3 : [4,5]
-- [1,2,3,4,5]

isort :: Ord a => [a] -> [a]
isort [] = []
isort (x : xs) = insert x (isort xs)

-- isort [3,2,1,4]
-- insert 3 (insert 2 (insert 1 (insert 4 [])))
-- insert 3 (insert 2 (insert 1 [4]))
-- insert 3 (insert 2 [1,4])
-- insert 3 [1,2,4]
-- [1,2,3,4]

marbull

drop' :: Int -> [a] -> [a]
drop' 0 xs = xs
drop' _ [] = []
drop' n (_ : xs) = drop' (n -1) xs

-- drop' 2 [1,2,3,4,5]
-- drop' 1 [2,3,4,5]
-- drop' 0 [3,4,5]
-- [3,4,5]

marbull

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n - 2) + fib (n - 1)

-- fib 5 = fib 3 + fib 4
-- fib 4 = fib 2 + fib 3
-- fib 3 = fib 1 + fib 2
-- fib 2 = fib 0 + fib 1
-- fib 1 = 1
-- fib 0 = 0

marbull

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

-- qsort [4,2,1,3]
-- qsort [2,1,3] ++ [4]
-- qsort [1] ++ [2] ++ qsort [3] ++ [4]
-- [1] ++ [2] ++ [3] ++ [4]

marbull

even' :: Int -> Bool
even' 0 = True
even' n = odd' (n - 1)

odd' :: Int -> Bool
odd' 0 = False
odd' n = even' (n - 1)

-- even' 5 = odd' 4
-- odd' 4 = even' 3
-- even' 3 = odd' 2
-- odd' 2 = even' 1
-- even' 1 = odd' 0
-- odd' 0 = False

marbull

evens :: [a] -> [a]
evens [] = []
evens (x : xs) = x : odds xs

odds :: [a] -> [a]
odds [] = []
odds (_ : xs) = evens xs

-- evens "abcdef"
-- 'a' : odds "bcdef"
-- 'a' : evens "cdef"
-- 'a' : 'c' : odds "def"
-- 'a' : 'c' : evens "ef"
-- 'a' : 'c' : 'e' : odds "f"
-- 'a' : 'c' : 'e' : evens ""
-- 'a' : 'c' : 'e' : []
-- "ace" == ['a', 'c', 'e']

marbull

再帰の秘訣

product

第一段階：型を定義する

product :: [Int] -> Int

第二段階：場合分けをする
引数の型には，それぞれ標準的な場合分けの方法がある。

リスト　　　：空リストと空ではないリスト
負でない整数：０と（0以外を表す）n
真理値　　　：TrueとFalse

product []     =
product (n:ns) =

第三段階：場合分けの簡単なほうを定義する

product []     = 1
product (n:ns) =

-- 場合分けの簡単なほうがたいてい基底部になる

第四段階：場合分けの複雑なほうを定義する

product []     = 1
product (n:ns) = n * product ns

-- 場合分けの複雑なほうがたいてい再帰部になる

第五段階：一般化し単純にする
関数productは特定の数値型に依存しているわけではないので，型を整数から任意の数値型へ一般化できる

product :: Num a => [a] -> a

定義を単純にすることも考える。productに使われているような再帰は，プレリュード関数foldrで置き換えることができる。関数foldrを使うと，関数productは等式一つで再定義できる。

product = foldr (*) 1

関数productの最終的な定義は以下のようになる。

product :: Num a => [a] -> a
product = foldr (*) 1

drop

第一段階：型を定義する

drop :: Int -> [a] -> [a]

第二段階：場合分けをする

drop 0 []     =
drop 0 (x:xs) =
drop n []     =
drop n (x:xs) =

第三段階：場合分けの簡単なほうを定義する

drop 0 []     = []
drop 0 (x:xs) = x:xs
drop n []     = []
drop n (x:xs) =

第四段階：場合分けの複雑なほうを定義する

drop 0 []     = []
drop 0 (x:xs) = x:xs
drop n []     = []
drop n (x:xs) = drop (n-1) xs

第五段階：一般化し単純にする

drop 0 xs
drop n []     = []
drop n (x:xs) = drop (n-1) xs

drop :: Int -> [a] -> [a]
drop 0 xs
drop _ []     = []
drop n (_:xs) = drop (n-1) xs

init

第一段階：型を定義する

init :: [a] -> [a]

第二段階：場合分けをする

init (x:xs) =

第三段階：場合分けの簡単なほうを定義する

nit (x : xs)
  | null xs = []
  | otherwise =

第四段階：場合分けの複雑なほうを定義する

init (x : xs)
  | null xs = []
  | otherwise = x ++ "," ++ init xs

第五段階：一般化し単純にする

init :: [a] -> [a]
init [_] = []
init (x:xs) = x : init xs

marbull

divideByTen :: (Floating a) => a -> a
divideByTen = (/ 10)

marbull

isUpperAlphanum :: Char -> Bool
isUpperAlphanum = (`elem` ['A' .. 'Z'])

marbull

applyTwice :: (a -> a) -> a -> a
applyTwice f x = f (f x)

marbull

クロージャを使用したい場合は，常に，引数をもっとも汎用的なものから順に並べる必要がある