引き続き、6 章も読みました。
6 章は「再帰関数」の章で、Haskell における再帰関数の考え方、定義の仕方を学ぶ章です。とはいえ、Haskell の再帰関数が多言語の再帰関数の概念となんら変わることはありませんでした。前章のリスト内包表記と比べると、慣れ親しんだ世界。
いつも通り、練習問題を解きます。
累乗演算子を定義せよ
(^) :: Int -> Int -> Int m ^ 0 = 1 m ^ (n + 1) = m * ((Main.^) m n)
リストの要素がすべて True であるか検査する
and :: [Bool] -> Bool and [] = True and (x : xs) = x && Main.and xs
リストのリストを取り、要素であるリストを連結する
concat :: [[a]] -> [a] concat [] = [] concat (xs : xss) = xs ++ Main.concat xss
指定された要素を n 個持つリストを生成する
replicate :: Int -> a -> [a] replicate 0 a = [] replicate (n + 1) a = a : Main.replicate n a
空でないリストの n 番目の要素を取り出す
(!!) :: [a] -> Int -> a (!!) (x : xs) 0 = x (!!) (x : xs) (n + 1) = (Main.!!) xs n
リストの要素に含まれるか検査する
elem :: Eq a => a -> [a] -> Bool elem a [] = False elem a (x : xs) = a == x || Main.elem a xs
整列されたリストを二つ取り、一つの整列されたリストにして返す関数
merge :: Ord a => [a] -> [a] -> [a] merge [] xs = xs merge xs [] = xs merge (x : xs) (y : ys) | x <= y = x : merge xs (y : ys) | otherwise = y : merge (x : xs) ys
マージソートを実行する関数
halve :: [a] -> ([a], [a]) halve xs = (Prelude.take (length xs `div` 2) xs, drop (length xs `div` 2) xs) msort :: Ord a => [a] -> [a] msort [] = [] msort [x] = [x] msort xs = merge (msort ys) (msort zs) where (ys, zs) = halve xs
数値のリストに対し要素の和を計算する関数 sum
sum :: Num a => [a] -> a sum [] = 0 sum (x : xs) = x + Main.sum xs
リストの先頭から n 個の要素を取り出す関数 take
take :: Int -> [a] -> [a] take 0 xs = [] take (n + 1) (x : xs) = x : Main.take n xs
空でないリストの末尾の要素を取り出す関数 last
last :: [a] -> a last [a] = a last (x : xs) = Main.last xs
