関数プログラマの道具箱

-- 関数プログラマがたった1つの値に対する演算をしたいことはない。
-- たいていは、数や文字や他の型のデータの集まりを受け取り、その集合を
-- 変換して結果を得たいものである。

-- 関数とリストを受け取り、その関数をリストのすべての要素に適用する
map' :: (a -> b) -> [a] -> [b]
map' _ [] = []
map' f (x:xs) = f x : map f xs

-- 述語とリストを受け取り、そのリストの要素のうち、述語を見たすもののみからなるリストを返す
filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' p (x:xs)
  | p x = x : filter p xs
  | otherwise = filter p xs

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

-- 10万以下の数のうち3829で割れる最大の数をサーチ
largestDivisible :: Integer
largestDivisible = head (filter p [100000,99999..])
  where p x = x `mod` 3829 == 0

-- 任意の自然数から開始する
-- 数が1ならば、終了
-- 数が偶数なら、2で割る
-- 数が奇数なら、3倍して1を足す
-- 新しい値でこのアルゴリズムを繰り返す
-- このアルゴリズムで得られた数列をコラッツの数列といい、
-- ここではその過程をリストで表示する
chain :: Integer -> [Integer]
chain 1 = [1]
chain n
  | even n = n : chain (n `div` 2)
  | odd n = n : chain (n * 3 + 1)

-- 1から100までのうち、長さ15以上のコラッツ列の開始数になるものはいくつあるか
numLongChains :: Int
numLongChains = length (filter isLong(map chain [1..100]))
  where isLong xs = length xs > 15

結果

Main> map (+3) [1,5,3,1,6]
[4,8,6,4,9]
Main> map (++ "!") ["BIFF", "BANG", "POW"]
["BIFF!","BANG!","POW!"]
Main> map (replicate 3) [3..6]
[[3,3,3],[4,4,4],[5,5,5],[6,6,6]]
Main> map (map (^2)) [[1,2], [3,4,5,6], [7,8]]
[[1,4],[9,16,25,36],[49,64]]
Main> map fst [(1,2),(3,5),(6,3),(2,6),(2,5)]
[1,3,6,2,2]
Main> filter (<3) [1,5,3,2,1,6,4,3,2,1]
[1,2,1,2,1]
Main> filter (>3) [1,5,3,2,1,6,4,3,2,1]
[5,6,4]
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']) " u LaUgH aT mE BeCaUsE I aM diFfeRent"
"uagameasadifeent"
Main> filter (`elem` ['A'..'Z']) "i LAuGh at you bEcause u R all the same"
"LAGER"
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]
Main> quicksort [1,2,3,4,5]
[1,2,3,4,5]
Main> quicksort [3,4,500,2,3,1,0,-1]
[-1,0,1,2,3,3,4,500]
Main> largestDivisible
99554
Main> takeWhile (/=' ') "elephants know how to party"
"elephants"
Main> sum (takeWhile (<10000) (filter odd (map (^2) [1..])))
166650
Main> sum (takeWhile (<10000) [m | m <- [n^2 | n <- [1..]], odd m])
166650
Main> chain 10
[10,5,16,8,4,2,1]
Main> chain 23
[23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]
Main> numLongChains
66
Main> numLongChains
66
Main> :t numLongChains
numLongChains :: Int
Main> let listOfFuns = map (*) [0..]
Main> (listOfFuns !! 4) 5
20