理系学生日記

おまえはいつまで学生気分なのか

忍者TOOLS

プログラミング Haskell の 6 章を読みました

引き続き、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