Haskell入門(再帰)
-- リストの最大の要素を返す -- リストの(先頭の要素)と(2番目以降の最大の要素)のうち、大きいものを返す maximum' :: (Ord a) => [a] -> a maximum' [] = error "empty list" maximum' [x] = x maximum' (x:xs) = max x (maximum' xs)
-- xをn個繰り返すリストを返す replicate' :: Int -> a -> [a] replicate' n x | n <= 0 = [] | otherwise = x : replicate' (n - 1) x
-- リストの先頭のn個を返す take' :: Int -> [a] -> [a] take' n _ | n <= 0 = [] take' _ [] = [] take' n (x:xs) = x : take' (n - 1) xs
reverse' :: [a] -> [a] reverse' [] = [] reverse' (x:xs) = reverse' xs ++ [x]
-- 与えられたものの無限リストを作る repeate' :: a -> [a] repeate' x = x : repeate' x
zip' :: [a] -> [b] -> [(a, b)] zip' _ [] = [] zip' [] _ = [] zip' (x:xs) (y:ys) = (x, y) : zip' xs ys
elem' :: (Eq a) => a -> [a] -> Bool elem' a [] = False elem' a (x:xs) | a == x = True | otherwise = elem' a xs
クイックソート
リストの先頭の要素以下のもの(smallerOrEqual)と
先頭の要素より大きいもの(larger)をそれぞれ
再帰呼び出しでソートして結合する。
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