fugafuga.write

日々のログ



すごいH本 part18

map と filter ふたたび

10万以下の数のうち3829で割り切れる最大の数を探す

largestDivisible :: Integer
largestDivisible = head (filter p [100000,99999..])
  where p x = x `mod` 3829 == 0

実行結果

*Main> largestDivisible
99554

10000 より小さい全ての奇数の平方数の和

*Main> sum (takeWhile (<10000) (filter odd (map (^2) [1..])))
166650

内包表記で書く

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

コラッツ数列を扱う

  • 任意の自然数から開始する
  • 数が1なら、終了
  • 数が偶数なら、2で割る
  • 数が奇数なら、3倍して1足す
  • 新しい値でこのアルゴリズムを繰り返す

1から100までの数のうち、長さ15以上のコラッツ列の開始数になるものはいくつあるか?

まず数列を作る関数を書く

chain :: Integer -> [Integer]
chain 1 = [1]
chain n
  | even n = n : chain (n `div` 2)
  | odd n  = n : chain (n * 3 + 1)

実行結果

*Main> chain 3
[3,10,5,16,8,4,2,1]

chainを使って求める

numLongChains :: Int
numLongChains = length (filter isLong (map chain [1..100]))
  where isLong xs = length xs > 15

実行結果

*Main> numLongChains
66

map に複数の引数を与える

*Main> let listOfFuns = map (*) [0..]
*Main> (listOfFuns !! 4) 5
20

!!はリストの要素を取得する演算子

(4*) 5になってる

所感

関数が長くなってくると読むのに時間がかかるようになってきた。 部分適用のおかげで関数を扱うための柔軟性が上がっていることを実感してきている。

いやー、楽しいな。

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

  • 作者: MiranLipovaca
  • 出版社/メーカー: オーム社
  • 発売日: 2017/07/14
  • メディア: Kindle版
  • 購入: 4人 クリック: 9回
  • この商品を含むブログを見る

すごいH本 part17

便利な関数

map

関数とリストを受け取ってその関数をリスト全ての要素に適用して新しいリストを生成する。

*Main> :t map
map :: (a -> b) -> [a] -> [b]

実装

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

実行

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

リストの内包表記でも同じことができるが、map を使うほうが読みやすくなる。

[x + 3 | x <- [1,2,3,4,5]]

filter

述語とリストを受け取り、そのリストの要素のうち、述語をみたすもののみからなるリストを返す。

*Main> :t filter
filter :: (a -> Bool) -> [a] -> [a]

実装

filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' p (x:xs)
  | p x       = x : filter' p xs
  | otherwise = filter' p xs

実行結果

*Main> filter' (>5) [1,2,3,4,5,6]
[6]
*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' even [1,2,3,4,5]
[2,4]

クイックソートの関数をfilter使って書き直す

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

内包表記つかうか、map, filter 関数使うかは読みやすいかどうかで決めてよい。

所感

map, filter なんかは Ruby で出てきたりするのでなんとなくわかる。が Haskell で書くのは慣れが必要だと感じる。

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

  • 作者: MiranLipovaca
  • 出版社/メーカー: オーム社
  • 発売日: 2017/07/14
  • メディア: Kindle版
  • 購入: 4人 クリック: 9回
  • この商品を含むブログを見る

すごいH本 part16

高階関数を実装する

高階関数は関数を引数として受け取ることができるし、返り値として関数を返すこともできる。

関数を受け取ってそれを2回適用する高階関数

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

実行結果

*Main> applyTwice (+3) 10
16
*Main> applyTwice (++ "HOOOOO") "FOOOO"
"FOOOOHOOOOOHOOOOO"
*Main> applyTwice ("Strong" ++) "Zero"
"StrongStrongZero"
*Main> applyTwice (multThree 2 2) 9
144
*Main> applyTwice (3:) [1]
[3,3,1]

引数を1つ受け取って1つの値を返す関数を部分適用で作り出し、 それを applyTwice の1つ目の引数に設定している。

zipWith を実装する

zipWith は2つのリストを引数に取り、2つのリストの各要素に関数を適用することで、2つのリストを1つに結合する。

よくわからんのでまず関数の型シグネチャを見てみる

*Main> :t zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

実装

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ [] _ = [] -- リスト a が空
zipWith' _ _ [] = [] -- リスト b が空
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

実行結果

*Main> zipWith' (+) [1,2,3] [4,5,6]
[5,7,9]
*Main> zipWith' max [1,2,3] [4,5,6]
[4,5,6]
*Main> zipWith' (++) ["aa","bb","cc"] ["xx","yy","zz"]
["aaxx","bbyy","cczz"]
*Main> zipWith' (*) (replicate 5 2) [1..]
[2,4,6,8,10]
*Main> zipWith' (zipWith' (*)) [[1,2,3],[3,5,6],[2,3,4]] [[3,2,2],[3,4,5],[5,4,3]]
[[3,4,6],[9,20,30],[10,12,12]]

最後のは難しいけど型考えたら「そうかー」となる。

flip を実装する

引数を入れ替えた関数を返すやつらしい

型シグネチャ

*Main> :t flip
flip :: (a -> b -> c) -> b -> a -> c

実装

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

実装その2

flip' :: (a -> b -> c) -> b -> a -> c
flip' f y x = f x y

その2の方がシンプルになっている。関数がカリー化されていることを上手く使っているらしい。

用途がよくわからんので実行してゆく

*Main> zip [1,2,3,4,5] "hello"
[(1,'h'),(2,'e'),(3,'l'),(4,'l'),(5,'o')]
*Main> flip' zip [1,2,3,4,5] "hello"
[('h',1),('e',2),('l',3),('l',4),('o',5)]
*Main> zipWith div [2,2..] [10,8,6,4,2]
[0,0,0,0,1]
*Main> zipWith (flip' div) [2,2..] [10,8,6,4,2]
[5,4,3,2,1]

なるほど、そういうことかというのはわかるが使い所が不明

所感

いまいちflipがよくわからん。関数を変形できるところにメリットがあるのか?

偉い人教えてください...

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

  • 作者: MiranLipovaca
  • 出版社/メーカー: オーム社
  • 発売日: 2017/07/14
  • メディア: Kindle版
  • 購入: 4人 クリック: 9回
  • この商品を含むブログを見る

すごいH本 part15

高階関数

引数に関数を受け取ったり、関数を返すような関数を高階関数という。

Haskell を学ぶ上でとても大事な考え方らしい。

カリー化関数

カリー化関数とは複数の引数を取る代わりに、常にちょうど1つの引数を取る関数です。

カリー化関数が呼び出されると、その次の引数を受け取る関数を返す。

*Main> max 2 5
5
*Main> (max 2) 5
5

(max 2)5 を引数として受け取る関数を返している。今までみてきた Haskell の関数はすべてカリー化されていて、複数の引数をとる関数も1つの引数をとる関数の組み合わせとして表現されている。

部分適用

複数引数を取る関数に1つだけ引数を渡すと、部分適用された関数が得られる。

これが

*Main> :t max
max :: Ord a => a -> a -> a

こういうこと

*Main> :t max
max :: Ord a => a -> (a -> a)

(a -> a)という関数を返している。

例として、引数を3つ取りそれらを乗算した結果を返す関数を書く

multThree :: Int -> Int -> Int -> Int
multThree x y z = x * y * z

実行結果

*Main> multThree 9 5 1
45

部分適用してみる

*Main> let multTwoWithNine = multThree 9
*Main> multTwoWithNine 2 5
90

関数のシグネチャはこうなる

*Main> :t multThree
multThree :: Int -> Int -> Int -> Int
*Main> :t multTwoWithNine
multTwoWithNine :: Int -> Int -> Int

セクション

中置関数にもセクションという機能を使って部分適用することができる。

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

中置関数の片側に値を書いて括弧でくくると部分適用となる。

実行結果

*Main> divideByTen 200
20.0
*Main> 200 / 10
20.0
*Main> (/10) 200
20.0

所感

高階関数もカリー化も部分適用もなんとなくわかった。しかし実際これらがどのように役に立つのかが実感できていないのでなんとも。という感じ。

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

  • 作者: MiranLipovaca
  • 出版社/メーカー: オーム社
  • 発売日: 2017/07/14
  • メディア: Kindle版
  • 購入: 4人 クリック: 9回
  • この商品を含むブログを見る

すごいH本 part14

クイックソートを実装する

ソートアルゴリズムはこんな感じ

  1. リストから任意の数を選ぶ(この数字をピボットと呼ぶ)
  2. ピボットより大きい数字を右側に、ピボット以下の数字を左側に移動する
  3. ピボットを除いた左右のリストに対して、1. 2. の手順を繰り返していく

実装

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] ++ quicksort larger

実行結果

*Main> quicksort [2,5,8,1,3,0]
[0,1,2,3,5,8]

再帰で考える

  • 基底部を見つける
  • 部分問題を再帰的に解く

この2つを正しく選んだなら全体として何が起こるかの詳細を考える必要がない。

所感

中学生レベルの数学の知識しかないが、演繹的というのだろうか。理論が先にあってそれが広がっているという感じで処理を書いていく感覚が得られた。まず、問題を分解していくというところでつまづくと何も始まらないという難しさも同時にあるように思える。最初の章に書いてあったが、Haskell はエレガントであるというところの意味が少しわかった。もうすでに問題は解けている。自明である。このような美しさがあるように感じた。

今日はここまで。

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

  • 作者: MiranLipovaca
  • 出版社/メーカー: オーム社
  • 発売日: 2017/07/14
  • メディア: Kindle版
  • 購入: 4人 クリック: 9回
  • この商品を含むブログを見る