このページは M.Hiroi が Haskell の勉強で作成した簡単なプログラムをまとめたものです。元ネタは P-99: Ninety-Nine Prolog Problems で、拙作のページ Yet Another Prolog Problems や Yet Another SML/NJ Problems などの Haskell バージョンになります。同じような問題しかありませんが、あしからずご了承くださいませ。
リストの要素がただひとつか調べる述語 single を定義してください。
single :: [a] -> Bool
*Main> single [] False *Main> single [1] True *Main> single [1, 2] False
リストの要素がひとつ以上あるか調べる述語 pair を定義してください。
pair :: [a] -> Bool
*Main> pair [] False *Main> pair [1] True *Main> pair [1, 2] True
リスト xs はリスト ys よりも長いか調べる述語 longer xs ys を定義してください。
longer :: [a] -> [a] -> Bool
*Main> longer [1,2,3] [4,5] True *Main> longer [1,2,3] [4,5,6] False *Main> longer [1,2,3] [4,5,6,7] False *Main> longer [1,2,3] [] True *Main> longer [] [1,2,3] False
リストの最後尾を求める関数 last_pair と、最後尾の要素を取り除く関数 butlast を定義してください。なお、Haskell には butlast と同じ働きをする関数 init が用意されています。また、last_pair と同じではありませんが、最後の要素を求める関数 last があります。
last_pair :: [a] -> [a] butlast :: [a] -> [a]
*Main> last_pair [1,2,3,4] [4] *Main> last_pair [1] [1] *Main> last_pair [] *** Exception: last_pair empty list *Main> butlast [1,2,3,4] [1,2,3] *Main> butlast [1] [] *Main> butlast [] *** Exception: butlast empty list
リストの先頭から n 個の要素を取り出す関数 take n xs を定義してください。なお、Haskell には同じ関数 take が定義されているので、ここでは関数名を take' としました。
take' :: Int -> [a] -> [a]
*Main> take' 0 [1,2,3,4,5] [] *Main> take' 3 [1,2,3,4,5] [1,2,3] *Main> take' 5 [1,2,3,4,5] [1,2,3,4,5] *Main> take' 6 [1,2,3,4,5] [1,2,3,4,5]
リストの先頭から n 個の要素を取り除く関数 drop n xs を定義してください。なお、Haskell には同じ関数 drop が定義されているので、ここでは関数名を drop' としました。
drop' :: Int -> [a] -> [a]
*Main> drop' 0 [1,2,3,4,5] [1,2,3,4,5] *Main> drop' 3 [1,2,3,4,5] [4,5] *Main> drop' 5 [1,2,3,4,5] [] *Main> drop' 6 [1,2,3,4,5] []
リストの末尾から n 個の要素を取り出す関数 takeR n xs を定義してください。
takeR :: Int -> [a] -> [a]
*Main> takeR 0 [1,2,3,4,5] [] *Main> takeR 2 [1,2,3,4,5] [4,5] *Main> takeR 5 [1,2,3,4,5] [1,2,3,4,5] *Main> takeR 6 [1,2,3,4,5] [1,2,3,4,5]
リストの末尾から n 個の要素を取り除く関数 dropR n xs を定義してください。
dropR :: Int -> [a] -> [a]
*Main> dropR 1 [1,2,3,4,5] [1,2,3,4] *Main> dropR 0 [1,2,3,4,5] [1,2,3,4,5] *Main> dropR 5 [1,2,3,4,5] [] *Main> dropR 6 [1,2,3,4,5] []
リスト xs を長さ n の部分リストに分割する関数 group n xs を定義してください。なお、この関数は Haskell のモジュール Data.List に定義されている関数 group とまったく異なる動作です。ご注意ください。
group :: Int -> [a] -> [[a]]
*Main> group 2 [1,2,3,4,5,6] [[1,2],[3,4],[5,6]] *Main> group 3 [1,2,3,4,5,6] [[1,2,3],[4,5,6]] *Main> group 1 [1,2,3,4,5,6] [[1],[2],[3],[4],[5],[6]] *Main> group 6 [1,2,3,4,5,6] [[1,2,3,4,5,6]] *Main> group 4 [1,2,3,4,5,6] [[1,2,3,4],[5,6]]
2 つのリスト xs, ys の要素 x, y を取り出し、タプル (x, y) にまとめてリストに格納して返す関数 zip xs ys を定義してください。リストは短いほうに合わせるものとします。なお、Haskell には同じ関数 zip が定義されているので、ここでは関数名を zip1 としました。
zip1 :: [a] -> [b] -> [(a, b)]
*Main> zip1 [1,2,3] [4,5,6] [(1,4),(2,5),(3,6)] *Main> zip1 [1,2,3] [4,5] [(1,4),(2,5)] *Main> zip1 [1,2] [4,5,6] [(1,4),(2,5)] *Main> zip1 [1..] [4,5,6,7] [(1,4),(2,5),(3,6),(4,7)]
zip したリストを元に戻す関数 unzip xs を定義してください。2 つのリストはタプルに格納して返すものとします。なお、Haskell には同じ関数 unzip が定義されているので、ここでは関数名を unzip1 としました。
unzip1 :: [(a, b)] -> ([a], [b])
*Main> unzip1 [(1, 2), (3, 4), (5, 6)] ([1,3,5],[2,4,6])
キーと値をタプル (key, value) にまとめ、それを格納したリストを「連想リスト (assocation list) 」といいます。連想リストからキーを探索し、対応する値を求める関数 assoc key alist と、述語 pred が真を返すキーを探す関数 assoc_if pred alist を定義してください。関数名は Lisp / Scheme から拝借しました。なお、Haskell には assoc と同じ働きをする関数 lookup が用意されています。
assoc :: Eq a => a -> [(a, b)] -> Maybe b assoc_if :: (a -> Bool) -> [(a, b)] -> Maybe b
*Main> assoc 1 [(1,10), (2,20), (3,30), (4,40)] Just 10 *Main> assoc 4 [(1,10), (2,20), (3,30), (4,40)] Just 40 *Main> assoc 5 [(1,10), (2,20), (3,30), (4,40)] Nothing *Main> assoc_if even [(1,10), (2,20), (3,30), (4,40)] Just 20 *Main> assoc_if odd [(1,10), (2,20), (3,30), (4,40)] Just 10 *Main> assoc_if (\x -> x `mod` 5 == 0) [(1,10), (2,20), (3,30), (4,40)] Nothing
リスト xs の中から述語 pred が真を返す最初の要素を求める関数 find_if pred xs を定義してください。なお、Haskell のモジュール Data.List には同じ働きをする関数 find が用意されています。
find_if :: (a -> Bool) -> [a] -> Maybe a
*Main> find_if even [1,2,3,4,5,6] Just 2 *Main> find_if odd [1,2,3,4,5,6] Just 1 *Main> find_if (\x -> x `mod` 3 == 0) [1,2,3,4,5,6] Just 3 *Main> find_if (\x -> x `mod` 7 == 0) [1,2,3,4,5,6] Nothing
リスト xs の中から述語 pred が真を返す最初の要素の位置を求める関数 position_if pred xs を定義してください。なお、リストの要素は 0 から数え始めるものとします。なお、Haskell のモジュール Data.List には同じ働きをする関数 findIndex が用意されています。
position_if :: (a -> Bool) -> [a] -> Maybe Int
*Main> position_if odd [1,2,3,4,5,6] Just 0 *Main> position_if even [1,2,3,4,5,6] Just 1 *Main> position_if (\x -> x `mod` 3 == 0) [1,2,3,4,5,6] Just 2 *Main> position_if (\x -> x `mod` 7 == 0) [1,2,3,4,5,6] Nothing
リスト xs から述語 pred が真を返す要素の個数を求める関数 count_if pred xs を定義してください。
count_if :: (a -> Bool) -> [a] -> Int
*Main> count_if odd [1,2,3,4,5,6,7] 4 *Main> count_if even [1,2,3,4,5,6,7] 3
リスト xs の中から最大値を求める関数 max_list xs と最小値を求める関数 min_list xs を定義してください。なお、Haskell には同じ働きをする関数 maximum と minimum が用意されています。
max_list :: Ord a => [a] -> a min_list :: Ord a => [a] -> a
*Main> max_list [1,2,3,4,5,6,7,8] 8 *Main> max_list [8,7,6,5,4,3,2,1] 8 *Main> min_list [1,2,3,4,5,6,7,8] 1 *Main> min_list [8,7,6,5,4,3,2,1] 1
リスト xs から重複要素を取り除く関数 removeDup xs を定義してください。なお、Haskell のモジュール Data.List には同じ働きをする関数 nub が用意されています。
removeDup :: Eq a => [a] -> [a]
*Main> removeDup [1,1,2,1,2,3,1,2,3,4,1,2,3,4,5] [1,2,3,4,5] *Main> removeDup [5,4,3,2,1] [5,4,3,2,1]
2 つの集合の和を求める関数 union xs ys を定義してください。なお、Haskell のモジュール Data.List には同じ働きをする関数 union が用意されています。
union :: Eq a => [a] -> [a] -> [a]
*Main> union [1,2,3,4,5] [4,5,6,7,8] [1,2,3,4,5,6,7,8] *Main> union [1,2,3,4] [5,6,7,8] [1,2,3,4,5,6,7,8] *Main> union [1,2,3,4] [1,2,3,4] [1,2,3,4]
2 つの集合の積を求める関数 intersection xs ys を定義してください。なお、Haskell のモジュール Data.List には同じ働きをする関数 intersect が用意されています。
intersection :: Eq a => [a] -> [a] -> [a]
*Main> intersection [1,2,3,4,5] [3,4,5,6,7] [3,4,5] *Main> intersection [1,2,3,4,5] [6,7,8,9,10] [] *Main> intersection [1,2,3,4,5] [1,2,3,4,5] [1,2,3,4,5]
2 つの集合の差を求める関数 difference xs ys を定義してください。なお、Haskell のモジュール Data.List には同じ働きをする演算子 \\ が用意されています。
difference :: Eq a => [a] -> [a] -> [a]
*Main> difference [1,2,3,4,5] [1,2,3,4,5] [] *Main> difference [1,2,3,4,5] [1,3,5] [2,4] *Main> difference [] [1,3,5] []
リスト xs を挿入ソートする関数 insert_sort xs を定義してください。
insert_sort :: Ord a => [a] -> [a]
*Main> insert_sort [5,6,4,7,3,8,2,9,1,0] [0,1,2,3,4,5,6,7,8,9] *Main> insert_sort [0,1,2,3,4,5,6,7,8,9] [0,1,2,3,4,5,6,7,8,9] *Main> insert_sort [9,8,7,6,5,4,3,2,1,0] [0,1,2,3,4,5,6,7,8,9]
リスト xs を述語 pred が真を返すものと偽を返すものの 2 つに分ける関数 partition_if pred xs を定義してください。分割したリストはタプルに格納して返すものとします。なお、Haskell のモジュール Data.List には同じ働きをする関数 partition が用意されています。
partition_if :: (a -> Bool) -> [a] -> ([a], [a])
*Main> partition_if even [1,2,3,4,5,6,7,8,9] ([2,4,6,8],[1,3,5,7,9]) *Main> partition_if odd [1,2,3,4,5,6,7,8,9] ([1,3,5,7,9],[2,4,6,8])
リスト xs をクイックソートする関数 quick_sort xs を定義してください。
quick_sort :: Ord a => [a] -> [a]
*Main> quick_sort [5,6,4,7,3,8,2,9,1,0] [0,1,2,3,4,5,6,7,8,9] *Main> quick_sort [9,8,7,6,5,4,3,2,1,0] [0,1,2,3,4,5,6,7,8,9] *Main> quick_sort [0,1,2,3,4,5,6,7,8,9] [0,1,2,3,4,5,6,7,8,9]
2 つのソート済みのリストをひとつのソート済みのリストにまとめる関数 merge_list xs ys を定義してください。
merge_list :: Ord a => [a] -> [a] -> [a]
*Main> merge_list [1,3,5,7,9] [2,4,6,8,10] [1,2,3,4,5,6,7,8,9,10] *Main> merge_list [1,3,5,7,9] [] [1,3,5,7,9] *Main> merge_list [] [1,3,5,7,9] [1,3,5,7,9] *Main> merge_list [1,3,5,7,9] [2,4,6] [1,2,3,4,5,6,7,9] *Main> merge_list [1,3,5] [2,4,6,8,10] [1,2,3,4,5,6,8,10]
関数 merge_list を使って長さ n のリスト xs をソートする merge_sort n xs を定義してください。
merge_sort :: Ord a => Int -> [a] -> [a]
*Main> merge_sort 10 [5,6,4,7,3,8,2,9,1,0] [0,1,2,3,4,5,6,7,8,9] *Main> merge_sort 10 [9,8,7,6,5,4,3,2,1,0] [0,1,2,3,4,5,6,7,8,9] *Main> merge_sort 10 [0,1,2,3,4,5,6,7,8,9] [0,1,2,3,4,5,6,7,8,9]
リスト : 要素がただひとつか single :: [a] -> Bool single [_] = True single _ = False
Haskell の場合、引数のリストと [ _ ] がマッチングすれば、そのリストの要素は一つしかないことがわかります。length でリストの長さを求める必要はありません。
リスト : 要素がひとつ以上あるか pair :: [a] -> Bool pair (_:_) = True pair _ = False
たとえば、リスト [1] と x:xs を照合すると、x = 1, xs = [ ] になります。したがって、引数のリストと _:_ がマッチングすれば、そのリストの要素は一つ以上あることがわかります。length でリストの長さを求める必要はありません。なお、述語 pair の名前は Scheme の関数 pair? から拝借しました。
リスト : リスト xs は ys よりも長いか longer :: [a] -> [a] -> Bool longer [] _ = False longer _ [] = True longer (_:xs) (_:ys) = longer xs ys
リストの先頭から順番にたどり、途中で ys が空リストになれば xs の方が長いことがわかります。length でリストの長さを求めて比較するよりも、このプログラムの方が効率的だと思います。
リスト : リストの最後尾を求める last_pair :: [a] -> [a] last_pair [] = error "last_pair empty list" last_pair [x] = [x] last_pair (_:xs) = last_pair xs
リスト : 最後尾の要素を取り除く butlast :: [a] -> [a] butlast [] = error "butlast empty list" butlast [_] = [] butlast (x:xs) = x : butlast xs
どちらの関数も引数が空リストの場合は error でエラーを送出します。last_pair は単純な再帰定義でリストの最後尾を求めています。butlast の 2 番目の節は、要素がひとつしかないリストから最後尾の要素を取り除くと空リストになることを表しています。これが再帰の停止条件になります。あとは次の節で butlast を再帰呼び出しして、xs から最後尾の要素を取り除いたリストに、引数のリストの先頭要素 x を追加していくだけです。
リスト : リストの先頭から n 個の要素を取り出す
take' :: Int -> [a] -> [a]
take' n _
| n <= 0 = []
take' _ [] = []
take' n (x:xs) = x : take' (n - 1) xs
n が 0 以下の場合は空リストを返します。途中でリスト xs が空になった場合も空リストを返します。最後の節で take' を再帰呼び出しして、その先頭に要素 x を追加します。
リスト : リストの先頭から n 個の要素を削除する
drop' :: Int -> [a] -> [a]
drop' n xs
| n <= 0 = xs
drop' _ [] = []
drop' n (_:xs) = drop' (n - 1) xs
最初の節で、削除する要素数が 0 以下であればリスト xs をそのまま返します。次の節で、xs が空リストの場合は空リストを返します。最後の節で drop' を再帰呼び出しして、xs から n - 1 個の要素を取り除いたリストを求めます。
リスト : リストの末尾から n 個の要素を取り出す takeR :: Int -> [a] -> [a] takeR n xs = reverse $ take' n $ reverse xs -- 別解 takeR' :: Int -> [a] -> [a] takeR' n xs = let m = length xs in if m > n then drop' (m - n) xs else xs
takeR は reverse と take を使うと簡単です。xs を reverse で反転し、take' で n 個の要素を取り出し、そのリストを reverse で反転するだけです。別解は xs の長さ m を length で求め、drop' で (m - n) 個の要素を取り除きます。これで末尾から n 個の要素を取り除くことができます。
リスト : リストの末尾から n 個の要素を取り除く dropR :: Int -> [a] -> [a] dropR n xs = reverse $ drop' n $ reverse xs -- 別解 dropR' :: Int -> [a] -> [a] dropR' n xs = let m = length xs in if m > n then take' (m - n) xs else []
dropR は reverse と drop を使うと簡単です。xs を reverse で反転し、drop' で n 個の要素を取り除き、残ったリストを reverse で反転するだけです。別解は xs の長さ m を length で求め、take' で (m - n) 個の要素を取り出しています。これで末尾から n 個の要素を取り除くことができます。
リスト : リストの分割 group :: Int -> [a] -> [[a]] group _ [] = [] group n xs = take' n xs : group n (drop' n xs)
関数 group は take と drop を使うと簡単に定義できます。xs が空リストの場合は分割できないので空リストを返します。これが再帰の停止条件になります。xs が空リストでない場合、まず take' で n 個の要素を格納したリストを求めます。次に、n 個の要素を取り除いたリストを drop' で求め、group を再帰呼び出ししてそのリストを分割します。あとはその返り値に take' で取り出したリストを追加するだけです。
リスト : zip zip1 :: [a] -> [b] -> [(a, b)] zip1 (x:xs) (y:ys) = (x, y) : zip1 xs ys zip1 _ _ = []
zip1 はリストの要素 x, y を取り出してタプルにまとめ、それをリスト追加していくだけです。どちらかの引数が空リストになったときが再帰呼び出しの停止条件です。
リスト : unzip unzip1 :: [(a, b)] -> ([a], [b]) unzip1 [] = ([], []) unzip1 ((x, y):xs) = (x:a, y:b) where (a, b) = unzip1 xs -- 別解 1 unzip1' :: [(a, b)] -> ([a], [b]) unzip1' xs = foldr (\(x, y) (a, b) -> (x:a, y:b)) ([],[]) xs -- 別解 2 unzip1'' :: [(a, b)] -> ([a], [b]) unzip1'' xs = ([x | (x, _) <- xs], [y | (_, y) <- xs])
unzip1 は引数が空リストの場合、2 つの空リストを格納したタプルを返します。これが再帰の停止条件になります。次に、unzip1 を再帰呼び出しして、変数 a, b に返り値のリストを受け取ります。あとは、a に x を、b に y を追加してタプルに格納して返すだけです。
別解1 は畳み込み foldr を使ったバージョンです。別解 2 はリスト内包表記を使ったバージョンです。この場合、リスト xs を 2 回アクセスすることに注意してください。
リスト : 連想リストの探索 assoc :: Eq a => a -> [(a, b)] -> Maybe b assoc _ [] = Nothing assoc x ((k, v):xs) | x == k = Just v | otherwise = assoc x xs assoc_if :: (a -> Bool) -> [(a, b)] -> Maybe b assoc_if _ [] = Nothing assoc_if p ((k, v):xs) | p k = Just v | otherwise = assoc_if p xs
assoc, assoc_if ともに引数のリストが空リストの場合は Nothing を返します。そうでなければ、aasoc はタプルの先頭要素 k が x と等しいかチェックします。等しい場合は Just v を返し、そうでなければ assoc を再帰呼び出しして次の要素をチェックします。assoc_if は p k が真の場合に Just k を返し、そうでなければ assoc_if を再帰呼び出しします。
リスト : 述語が真となる要素を探索する find_if :: (a -> Bool) -> [a] -> Maybe a find_if _ [] = Nothing find_if p (x:xs) | p x = Just x | otherwise = find_if p xs
find_if はリストの先頭から順番に調べていき、p x の返り値が真であれば Just x を返します。pred が真となる要素が見つからない場合は Nothing を返します。
リスト : 要素の位置を求める
position_if :: (a -> Bool) -> [a] -> Maybe Int
position_if p xs = iter 0 xs
where
iter _ [] = Nothing
iter i (x:xs)
| p x = Just i
| otherwise = iter (i + 1) xs
-- 別解
position_if' :: (a -> Bool) -> [a] -> Maybe Int
position_if' p xs = assoc_if p (zip1 xs [0..])
position_if は局所関数 iter で要素の位置 i を求めます。リストの先頭から順番に調べていき、p x の返り値が真であれば Just i を返します。p が真となる要素が見つからない場合は Nothing を返します。
別解は zip1 で要素と位置の連想リストを作成し、assoc_if で要素の位置を求めます。[0..] は無限リストになりますが、xs が有限のリストであればプログラムは正常に動作します。
リスト : 要素の個数を求める
count_if :: (a -> Bool) -> [a] -> Int
count_if p xs = iter xs 0
where
iter [] a = a
iter (x:xs) a
| p x = iter xs (a + 1)
| otherwise = iter xs a
-- 別解
count_if' :: (a -> Bool) -> [a] -> Int
count_if' p xs = foldl (\a x -> if p x then a + 1 else a) 0 xs
count_if は局所関数 iter で要素の個数をカウントします。引数 a を累積変数として使います。p x が真の場合、a を +1 して iter を再帰呼び出しします。そうでなければ a の値をそのままにして iter を再帰呼び出しします。リストが空リストの場合は a を返します。別解は畳み込みを行う関数 foldl を使って書き直したものです。
リスト : リストから最大値と最小値を求める max_list :: Ord a => [a] -> a max_list [] = error "max_list empty list" max_list [x] = x max_list (x:xs) = max x (max_list xs) min_list :: Ord a => [a] -> a min_list [] = error "min_list empty list" min_list [x] = x min_list (x:xs) = min x (min_list xs) -- 別解 max_list1 :: Ord a => [a] -> a max_list1 [] = error "max_list: empty list" max_list1 (x:xs) = foldl max x xs min_list1 :: Ord a => [a] -> a min_list1 [] = error "min_list: empty list" min_list1 (x:xs) = foldl min x xs
どちらの関数も再帰呼び出しで最大値 (最小値) を求めます。引数が空リストの場合はエラーを送出します。リストの要素がひとつしかない場合はその値を返します。これが再帰の停止条件になります。それ以外の場合はリストを x:xs で分解し、x と max_list xs (または min_list xs) を比較して、大きいほう (または小さいほう) を返します。別解は foldl で書き直したものです。
リスト : 集合の生成
removeDup :: Eq a => [a] -> [a]
removeDup [] = []
removeDup xs = iter xs []
where
iter [] _ = []
iter (x:xs) ys
| elem x ys = iter xs ys
| otherwise = x : iter xs (x:ys)
-- 別解
removeDup' :: Eq a => [a] -> [a]
removeDup' xs = foldr (\x a -> if elem x a then a else x:a) [] xs
実際の処理は局所関数 iter で行います。第 2 引数のリスト ys に初めて出現した要素を追加し、このリストを使って重複要素をチェックするのがポイントです。第 1 引数が空リストの場合は空リストを返します。そうでなければ、第 1 引数をパターン x : xs で分解し、x が ys に含まれているか関数 elem でチェックします。そうであれば、重複した要素なので集合に追加しません。含まれていなければ、iter を再帰呼び出しして、その返り値のリストに x を追加します。別解は foldr を使ってプログラムしたものです。
リスト : 集合の和 union :: Eq a => [a] -> [a] -> [a] union [] ys = ys union (x:xs) ys | elem x ys = union xs ys | otherwise = x : union xs ys -- 別解 1 union' :: Eq a => [a] -> [a] -> [a] union' xs ys = foldr (\x a -> if elem x ys then a else x:a) ys xs -- 別解 2 union'' :: Eq a => [a] -> [a] -> [a] union'' xs ys = [x | x <- xs, notElem x ys] ++ ys
xs が空リストの場合は ys を返します。これは空集合 (空リスト) と集合 ys の和は ys であることを表しています。次の節でリストを x:xs に分解して、x が ys に含まれていなければ、x を集合に追加します。含まれている場合は集合に追加しません。別解 1 は foldr で書き直したもの、別解 2 はリスト内包表記で書き直したものです。
リスト : 集合の積 intersection :: Eq a => [a] -> [a] -> [a] intersection [] _ = [] intersection (x:xs) ys | elem x ys = x : intersection xs ys | otherwise =intersection xs ys -- 別解 1 intersection' :: Eq a => [a] -> [a] -> [a] intersection' xs ys = foldr (\x a -> if elem x ys then x:a else a) [] xs -- 別解 2 intersection'' :: Eq a => [a] -> [a] -> [a] intersection'' xs ys = [x | x <- xs, elem x ys]
xs が空リストの場合は空リストを返します。これは空集合 (空リスト) と集合 ys の積は空リストであることを表しています。次の節でリストを x:xs に分解して、x が ys に含まれていれば x を集合に追加します。含まれていない場合は集合に追加しません。別解 1 は foldr で書き直したもの、別解 2 はリスト内包表記で書き直したものです。
リスト : 集合の差 difference :: Eq a => [a] -> [a] -> [a] difference [] _ = [] difference (x:xs) ys | elem x ys = difference xs ys | otherwise = x : difference xs ys -- 別解 1 difference' :: Eq a => [a] -> [a] -> [a] difference' xs ys = foldr (\x a -> if elem x ys then a else x:a) [] xs -- 別解 2 difference'' :: Eq a => [a] -> [a] -> [a] difference'' xs ys = [x | x <- xs, notElem x ys]
xs が空リストの場合は空リストを返します。これは空集合 (空リスト) と集合 ys の差は空リストであることを表しています。次の節でリストを x:xs に分解して、x が ys に含まれていなければ x を集合に追加します。含まれている場合は集合に追加しません。別解 1 は foldr で書き直したもの、別解 2 はリスト内包表記で書き直したものです。
リスト : 挿入ソート insert_element :: Ord a => a -> [a] -> [a] insert_element x [] = [x] insert_element x a@(y:ys) | x > y = y : insert_element x ys | otherwise = x : a insert_sort :: Ord a => [a] -> [a] insert_sort [] = [] insert_sort (x:xs) = insert_element x (insert_sort xs) -- 別解 insert_sort' :: Ord a => [a] -> [a] insert_sort' xs = foldr insert_element [] xs
挿入ソートはデータ x をリスト xs に挿入する関数 insert_element x xs を定義すると簡単です。xs はソート済みのリストです。insert_element は引数のリストが空リストの場合は [x] を返します。そうでなければ、x とリストの先頭要素 y を比較します。x が y よりも大きければ insert_element を再帰呼び出しして次の要素と比較します。そうでなければ、その位置に x を挿入するので、x:a を返すだけです。なお、Haskell のモジュール Data.List には同じ働きをする関数 insert が用意されています。
insert_sort は引数が空リストであれば空リストを返します。これが再帰の停止条件になります。そうでなければ、リストを x:xs で分解して insert sort xs を再帰呼び出しします。そして、その返り値のリストに insert_element で x を挿入すればいいわけです。別解は畳み込み foldr を使ったバージョンです。
リスト : リストの分割 partition_if :: (a -> Bool) -> [a] -> ([a], [a]) partition_if _ [] = ([], []) partition_if p (x:xs) = let (a, b) = partition_if p xs in if p x then (x:a, b) else (a, x:b) -- 別解 1 partition_if' :: (a -> Bool) -> [a] -> ([a], [a]) partition_if' p xs = foldr (\x (a, b) -> if p x then (x:a, b) else (a, x:b)) ([],[]) xs -- 別解 2 partition_if'' :: (a -> Bool) -> [a] -> ([a], [a]) partition_if'' p xs = ([x | x <- xs, p x], [x | x <- xs, not (p x)])
最初の節で、リストが空リストならば、空リストを 2 つ格納したタプルを返します。次の節で、partition_if を再帰呼び出しして、その返り値と (a, b) をマッチングさせます。そして、p x が真ならば x を a に追加し、そうでなければ b に追加します。
別解 1 は畳み込み foldr でプログラムしたもの、別解 2 はリスト内包表記でプログラムしたものです。別解 2 はリスト xs を 2 回アクセスすることに注意してください。
リスト : クイックソート
quick_sort :: Ord a => [a] -> [a]
quick_sort [] = []
quick_sort (x:xs) = quick_sort a ++ [x] ++ quick_sort b
where
(a, b) = partition_if (< x) xs
-- 別解
quick_sort' :: Ord a => [a] -> [a]
quick_sort' [] = []
quick_sort' (x:xs) = quick_sort' [y | y <- xs, y < x]
++ [x]
++ quick_sort' [y | y <- xs, y >= x]
引数のリストが空リストであれば空リストを返します。そうでなければ、リストの先頭要素 x を枢軸として、partition_if で x より小さい要素と x 以上の要素に分けます。あとは quick_sort を再帰呼び出しして、その結果を [x] をはさんで演算子 ++ で連結するだけです。別解はリスト内包表記を使ったバージョンです。リストを二分割するとき、2 回アクセスすることに注意してください。
リスト : リストのマージ merge_list :: Ord a => [a] -> [a] -> [a] merge_list [] ys = ys merge_list xs [] = xs merge_list a@(x:xs) b@(y:ys) | x <= y = x : merge_list xs b | otherwise = y : merge_list a ys
xs が空リストの場合は ys を返し、ys が空リストの場合は xs を返します。次に、リストの先頭要素 x と y を比較します。x <= yであれば x をリストに追加します。そうでなければ y をリストに追加します。
リスト : マージソート
merge_sort :: Ord a => Int -> [a] -> [a]
merge_sort _ [] = []
merge_sort 1 (x:_) = [x]
merge_sort 2 (x:y:_) = if x > y then [y, x] else [x, y]
merge_sort n xs =
merge_list (merge_sort m xs) (merge_sort (n - m) (drop' m xs))
where
m = div n 2
引数 n はリスト xs の長さを表します。リストが空リストの場合は空リストを返します。要素が一つしかない場合は [x] を返します。2 つある場合は要素 x と y を比較し、x > y であれば [y, x] を、そうでなければ [x, y] を返します。それ以外の場合は、リスト xs を二分割して merge_sort を再帰呼び出しし、その結果を merge_list でマージします。
リストを二分割していくのではなく、要素が 1 つのリストを作って、それを順番にマージしていくこともできます。次のリストを見てください。
リスト : マージソート (別解)
merge_sort' :: Ord a => [a] -> [a]
merge_sort' xs = iter1 (map (:[]) xs)
where
iter1 [x] = x
iter1 xs = iter1 (iter2 xs)
iter2 [] = []
iter2 [x] = [x]
iter2 (x:y:zs) = merge_list x y : iter2 zs
実際の処理は局所関数 iter1 と iter2 で行います。最初に、map で要素をリストに格納して、それを iter1 に渡します。iter1 はリストの要素がひとつになるまで、iter2 を繰り返し呼び出します。iter2 は先頭から順番にリストを 2 つ取り出して、それを merge_list でマージします。そして、その結果をリストに格納して返します。
それでは実行してみましょう。
*Main> merge_sort' [5,6,4,7,3,8,2,9,1,0] [0,1,2,3,4,5,6,7,8,9] *Main> merge_sort' [0..9] [0,1,2,3,4,5,6,7,8,9] *Main> merge_sort' [9,8..0] [0,1,2,3,4,5,6,7,8,9]