すごいHaskell楽しく学ぼう 05.2

書籍「すごいHaskell楽しく学ぼう」の学習メモです。

関数プログラマの道具箱

map関数

Haskellではパターンマッチと再帰処理で簡単にMapをシンプルに実装しています。

1
2
3
map' :: (a -> b) -> [a] -> [b]
map' _ [] = []
map' f (x:xs) = f x : map f xs

1
2
3
4
5
6
7
8
*Main> map' (+1) [1,2,3,4,5]
[2,3,4,5,6]
*Main> map' (++ "!") ["AAA", "BBB", "CCC"]
["AAA!","BBB!","CCC!"]
*Main> map' (replicate' 2) [5..8]
[[5,5],[6,6],[7,7],[8,8]]
*Main> map' (map' (^2)) [[1,2],[3,4,5,6],[7,8]]
[[1,4],[9,16,25,36],[49,64]]

Haskellはmap関数を使わずに、リスト内包表記でもかける場合がある。

1
2
3
4
5
*Main> [x+1 | x<-[1,2,3,4,5]]
[2,3,4,5,6]
*Main> [x+1 | x<-[1,2,3,4,5], x < 5]
[2,3,4,5]
*Main>

filter関数

1
2
3
4
5
6
7
-- 述語(predicate)は、true|falseを返す関数
--
filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' p (x:xs)
| p x = x : filter' p xs
| otherwise = filter' p xs

この時点ではまだラムダ式が出てきていないので、letを使って関数をnotNull変数に束縛して、それをfilterで使っています。

1
2
3
4
5
6
7
8
9
10
11
*Main> filter' (>3) [1,5,3,2]
[5]
*Main> filter (==3) [1,2,3,4,5]
[3]
*Main> filter even [1..10]
[2,4,6,8,10]
*Main> let notNull x = not (null x) in filter notNull [[1,2,3],[],[3,4,5],[2,2]\
,[],[],[]]
[[1,2,3],[3,4,5],[2,2]]
*Main> filter' (`elem` ['a'..'z']) "ABCabc123ABCabc123"
"abcabc"

filterとリスト内包表記

1
2
3
4
5
*Main> filter (<15) (filter even [1..20])
[2,4,6,8,10,12,14]

*Main> [x | x <- [1..20], x < 15, even x]
[2,4,6,8,10,12,14]

map,filterとリスト内包表記のどちらを使うかは明確なルールがなく、単純に読みやすい方を使えばよいそうです。上記の場合は、リスト内包表記のほうがすっきりしていると感じます。

mapとfilterのさらなる例

1
2
3
4
-- 10万以下の数で、3829で割り切れる最大値を計算
largestDivisible :: Integer
largestDivisible = head (filter p [100000, 99999..])
where p x = mod x 3829 == 0
1
2
*Main> largestDivisible
99554

takeWhile

渡した指定関数を満たす間ループします。このtakeWhile関数の例は、SQLを書いているようなので、宣言型言語の考え方が分かりやすい例でした。

1
2
3
4
5
6
*Main> takeWhile (/= ' ') "elephants know how to party"
"elephants"
*Main> takeWhile (<10) (filter odd (map (^2) [1..]))
[1,9]
*Main> sum (takeWhile (<10000) (filter odd (map (^2) [1..])))
166650

リスト内包表記の場合は、入れ子状態になるとかなり見づらくなります。

1
2
*Main> sum (takeWhile (<10000) [m | m <- [n^2 | n <- [1..]], odd m])
166650

map関数に複数の引数を与える。

mapで関数のリストを作成し、!!で要素指定し、計算します。

1
2
3
4
5
*Main> let arrayF = map (*) [0..10]
*Main> (arrayF !!2) 3
6
*Main> (arrayF !!5) 5
25

ラムダ式

Haskellのラムダ式は、’\’です。注意するところは、=で本体とつなげるのではなく、->であることです。

1
2
*Main> zipWith (\ a b -> (a * 30 + 3) / b) [5,4,3,2,1] [1,2,3,4,5]
[153.0,61.5,31.0,15.75,6.6]

分からない

以下が等価なのですが分からなかったのですが、x,y,zにそれぞれ、1,2,3を入れて考えると理解できます。addThree xと考えたときあ、addThree 1で部分適用すると、1を保持した関数が返ってきます。これは言い換えると、 \1 -> (\y -> \z -> 1 + y + z)という状態になっています。

1
2
3
4
5
addThree :: Int -> Int -> Int -> Int
addThree x y z = x + y + z

addThree' :: Int -> Int -> Int -> Int
addThree' = \x -> \y -> \z -> x + y + z

まとめ

map,filter高階関数の実装方法とHaskellのラムダ表記を学びました。Haskellの場合は恐ろしく簡素です。また、今回takeWhileがSQLのように見えてきたのですこしコツがつかめてきたのかもしれません。よくよく考えてみると、SQLでデータを取得したり集計するとき、宣言型言語だからどうとかは意識せずに純粋に問題を解いています。またSQLでも小さなサンプルをトライアンドエラーをしながら、大きく組み立てていきます。なのでmapやfilterやtakeWhileをREPLでいろいろ試して、関数型プログラミングを行う上での土台を固めて行けそうです。

すごいHaskell楽しく学ぼう 05.

書籍「すごいHaskell楽しく学ぼう」の学習メモです。今回は、「第5章:高階関数」でカリー化やmap,reduceのような関数を学んでいきます。結構ボリュームがあるので、各段落の細かいメモを取りながら学習していきます。

カリー化関数

Haskellでは、関数を作ると自動でカリー化されて、ひとつの引数をとる関数となれます。JavaやC言語だと、引数のデフォルト値がないため、引数が2つある関数で、第一引数のみ設定して呼び出すなどができませんが、Haskellの場合は、第一引数を指定すると、次の引数をとる関数型を返します。JavaScriptでクロージャーで、引数をバインドして、関数を返せますが、それを連鎖させる感じです。

1
2
3
4
5
6
7
ES6だとこんな感じ。
((m) => ((n) => 3 * n)(9) * m)(7)

いままでのJavaScriptだと
(function (m) {
return (function (n) { return 3 * n })(9) * m
})(7)

JavaScriptをやっているときは感じなかったのですが、Lispなど関数型言語を勉強しているときにJavaScriptで書いてみるとすごく面倒に感じます。

セクション

10 + 10で、このプラス記号もHaskellでは単なる中間表記の関数で、これに部分で起用する場合は、
(10 +)のようにすればよく、これをセクション呼びます。直観的で特に問題なさそうです。

1
2
3
4
*Main> :t (10 +)
(10 +) :: Num a => a -> a
*Main> (10 +) 5
15

高階実演

関数を二回適用する(apply)関数を作ります。まだラムダ式をやってないので、無名関数として(+3)などを使い、関数を引数として渡す方法を学びました。私の場合、C言語は関数名がポインタが同じ仕組みとしてはイメージしやすいです。

1
2
3
4
5
6
7
8
9
applyTwice :: (a -> a) -> a -> a
applyTwice f x = f (f x)

*Main> applyTwice (+3) 10
16
*Main> applyTwice (++ " HAHA") "HEY"
"HEY HAHA HAHA"
*Main> applyTwice ("AAA" ++) "GOGOGO"
"AAAAAAGOGOGO"

zipWithを実装する

1
2
3
4
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys
1
2
3
4
*Main> zipWith (+) [1,2,3] [1,2,3]
[2,4,6]
*Main> zipWith max [1,2,3] [9,1,5]
[9,2,5]

flipを実装

関数の引数を入れ替えるflip関数を作成します。

1
2
3
flip ' :: (a -> b -> c) -> (b -> a -> c)
flip ' f = g
where g x y = f y x

where節はletの変数バインドと同じで、この場合は、引数x,yをとる関数gを定義しています。以下のようにもっと簡略化が可能ですが、ちょっと読み解くのが難しいです。

1
2
3
4
5
flip2 :: (a -> b -> c) -> (b -> a -> c)
flip2 f x y = f y x

*Main> flip2 zip [1,2,3] "abc"
[('a',1),('b',2),('c',3)]

まとめ

5章は長いのでこの学習メモを分割して書いていきます。5章の最初で、カリー化、部分適用、セクション、高階関数を学習しました。Haskellは関数をREPL上で作るとその関数の型を返しますが、引数が繋がっているのがこの章で分かってきました。

haskell-drill-001

書籍「すごいHaskell楽しく学ぼう」の学習メモです。

関数型言語で小さな問題を修正して反復練習しましょう。

  • 問01. フィボナッチ数列を命令型言語のループを使わずに実装しなさい。
  • 問02. min’関数。引数を2つ持ち、比較して小さな値を返す。
  • 問03. max’関数。引数を2つ持ち、比較して小さな値を返す。
  • 問04. head’またはcarを実装しなさい。
  • 問05. tail’または、cdrを実装しなさい。
  • 問06. factorial 階乗 を実装しなさい。
  • 問07. リストから最大値を取得するmaximum’関数を実装しなさい。
  • 問08. リストから最小値を取得するminimum’関数を実装しなさい。
  • 問09. sum’を実装しなさい。
  • 問10. length’を実装しなさい。
  • 問11. replicateを実装しなさい。

すごいHaskell楽しく学ぼう 04.

書籍「すごいHaskell楽しく学ぼう」の学習メモです。

LandOfLispでいろいろ学んだので、「第4章:Hello再帰!」は問題ないはずです。(Hello recursion!というのは、Hello World!から来てるのでしょうか…)

第4章:Hello再帰!

Haskellは、命令型言語のようにどうやってするかを指定するのではなく、何であるかを宣言して計算します。これはSQLと同様です。

この章では、再帰処理になれるために基本的な関数の実装を自分で入力して試しなさいという感じです。例えば[1,2,3,4,5]の順序を逆にするreverseなどです。

Lispは、Emacsなどで色分けすれば括弧は問題ありませんが、Haskellは、パターンマッチが強力で綺麗に書けますね。

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

1
2
3
4
CL-USER> (defun rev (l)
(cond
((null l) '())
(T (append (rev (cdr l)) (list (car l))))))

無限リストを作る

この章で、takeとrepeatも作りました。さらっと当たり前に無限リストを作っていますが、遅延評価ならではです。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
take' :: Int -> [a] -> [a]
take' n _
| n <= 0 = []
take' _ [] = []
take' n (x:xs) = x : take' (n-1) xs

repeat' :: a -> [a]
repeat' x = x : repeat' x

*Main> take' 5 (repeat' 1)
[1,1,1,1,1]

*Main> take 5 (repeat 1)
[1,1,1,1,1]

まとめ

“第4章:Hello再帰”では、小さめの再帰関数をたくさん写経することができました。練習問題がないので、ここで出てきた関数を全部作る練習問題を自分で用意して、何回も反復練習をすればよさそうです。