01

18

[Haskell] 第5回 演習問題と解答例

2013.01.18(21:05)

関数型プログラミング言語 社内学習会 第5回 高階関数 演習問題と解答例
講師と有志がこしらえた問題を解いてみた

{-# OPTIONS -Wall -Werror #-}

module Exercise5 where
import Test.HUnit
import Test.QuickCheck
import Debug.Trace

-- | 演習問題1
-- | 関数を受け取り、それをN回適用する関数
applyNtimes1,applyNtimes2,applyNtimes3,applyNtimes4 :: Int->(a->a)->a->a
-- | 再帰版
applyNtimes1 0 _ s = s
applyNtimes1 n f s = applyNtimes1 (n-1) f (f s)
-- | 関数fを初期値sに繰り返し適用してできたリストのn番目
applyNtimes2 n f s = iterate f s !! n
-- | 関数fがn個入ったリストを関数合成した関数を作る
applyNtimes3 n f = foldr (.) id (replicate n f)
applyNtimes4 n f = foldl (.) id (replicate n f)

-- | ユニットテスト
applyNtimesTest :: Test
applyNtimesTest = test [
    applyNtimes1 (0::Int) (+3) (4::Int) ~=? 4,
    applyNtimes1 (3::Int) (+3) (4::Int) ~=? 13,
    applyNtimes1 (5::Int) (*2) (1::Int) ~=? 32,
    applyNtimes1 (5::Int) ("HAHA " ++) "HEY" ~=? "HAHA HAHA HAHA HAHA HAHA HEY",
    applyNtimes2 (0::Int) (+3) (4::Int) ~=? 4,
    applyNtimes2 (3::Int) (+3) (4::Int) ~=? 13,
    applyNtimes3 (0::Int) (+3) (4::Int) ~=? 4,
    applyNtimes3 (3::Int) (+3) (4::Int) ~=? 13,
    (succ . succ . succ . id) (1::Int) ~=? 4,
    foldr (.) id [succ,succ,succ] (1::Int) ~=? 4,
    foldl (.) id [succ,succ,succ] (1::Int) ~=? 4,
    applyNtimes4 (0::Int) (+3) (4::Int) ~=? 4,
    applyNtimes4 (3::Int) (+3) (4::Int) ~=? 13,
    True ~=? True
 ]

-- | quickCheck
prop_applyNtimes :: Int->Int->Property
prop_applyNtimes n s = (0<n) && (n<10)
                ==> applyNtimes1 n (+3) s == applyNtimes2 n (+3) s

----------------------------------------------------
-- | 演習問題2
-- | リストのリストを取って、要素のリストを連結する関数
concat1,concat2,concat3,concat4 :: [[a]]->[a]
-- | 再帰版
concat1 [] = []
concat1 (xs:xss) = xs ++ concat1 xss
-- | リスト内包表記版
concat2 xss = [x|xs<-xss,x<-xs]
-- | 左畳込み版
concat3 = foldl (++) []
-- | 右畳込み版
concat4 = foldr (++) []

-- | ユニットテスト
concatTest :: Test
concatTest = test [
    concat1 ([[1,2],[3],[],[4,5]]::[[Int]]) ~=? ([1,2,3,4,5]::[Int]),
    concat1 ["a", "bc", "d"] ~=? "abcd",
    concat1 ([[2,3], [] , [1], [4,5,6]]::[[Int]]) ~=? ([2,3,1,4,5,6]::[Int]),
    concat2 ([[1,2],[3],[],[4,5]]::[[Int]]) ~=? ([1,2,3,4,5]::[Int]),
    concat3 ([[1,2],[3],[],[4,5]]::[[Int]]) ~=? ([1,2,3,4,5]::[Int]),
    concat4 ([[1,2],[3],[],[4,5]]::[[Int]]) ~=? ([1,2,3,4,5]::[Int]),
    True ~=? True
 ]

-- | quickCheck
prop_concat :: [[Int]]->Bool
prop_concat xss = concat1 xss == cc &&
                  concat2 xss == cc &&
                  concat3 xss == cc &&
                  concat4 xss == cc
                  where cc = concat xss

----------------------------------------------------
-- | 演習問題3
-- | 以下の数列はどのような数列か説明せよ
alist :: [Int]
alist = 0 : 1 : zipWith (+) alist (tail alist) 
blist :: [Int]
blist = 0 : scanl (+) 1 blist
-- | これはフィボナッチ数列 [0,1,1,2,3,5,8,13,21,...]
-- | ユニットテスト
ablistTest :: Test
ablistTest = test [
    take 100 alist ~=? take 100 blist,
    True ~=? True
 ]

----------------------------------------------------
-- | 演習問題4
-- | リストの中から与えられた条件を満たす要素の数を返す関数 
count,count' :: (a->Bool)->[a]->Int
-- | 再帰版
count _ [] = 0
count f (x:xs) = if f x then 1 + count f xs
                        else count f xs
-- | リスト内包表記版
count' f xs = length [x|x<-xs,f x]

-- | ユニットテスト
countTest :: Test
countTest = test [
    count (== 1) ([1,2,1,3,4,1,5,1]::[Int]) ~=? 4,
    count (\x -> x `mod` 2 == 0) ([1,2,1,3,4,1,5,1]::[Int]) ~=? 2,
    count id [True,False,True,True] ~=? 3,
    count' (== 1) ([1,2,1,3,4,1,5,1]::[Int]) ~=? 4,
    True ~=? True
 ]
----------------------------------------------------
-- | 演習問題5
-- | insert関数を定義せよ
-- | insert関数とは要素とリストを取り、第一引数を
-- | リストの 「第一引数以下の要素群の最後」に挿入する関数である。
insert,insert' :: Ord a => a->[a]->[a]
-- | 再帰版
insert a [] = [a]
insert a total@(x:xs) = if a<x then a:total
                               else x:insert a xs
-- | breakを使って aより大きい要素が初めて出てくるところの前と後で分けて、aをはさむ
-- | break (> 3) [1,2,3,4,1,2,3,4] == ([1,2,3],[4,1,2,3,4])
insert' a xs = f ++ [a] ++ s
               where (f,s) = break (>a) xs

-- | ユニットテスト
insertTest :: Test
insertTest = test [
-- | ソートされたリストに対して用いるとソートされたリストが手に入る。
    insert (61::Int) ([0,10,20,30,40,50,60,70,80,90]::[Int]) ~=? ([0,10,20,30,40,50,60,61,70,80,90]::[Int]),
    insert' (61::Int) ([0,10,20,30,40,50,60,70,80,90]::[Int]) ~=? ([0,10,20,30,40,50,60,61,70,80,90]::[Int]),
-- | ソートされていないリストだと、要素より大きい要素の前に挿入される。
    insert (27::Int) ([0,10,20,30,20,10,0,10,20,30]::[Int]) ~=? ([0,10,20,27,30,20,10,0,10,20,30]::[Int]),
    insert' (27::Int) ([0,10,20,30,20,10,0,10,20,30]::[Int]) ~=? ([0,10,20,27,30,20,10,0,10,20,30]::[Int]),
    True ~=? True
 ]

----------------------------------------------------
-- | 演習問題6
-- | map関数を定義せよ
-- | map f [x1, x2, ...] == [f x1, f x2, ...]
map1,map2,map3 :: (a->b)->[a]->[b]
-- | リスト内包表記版
map1 f xs = [f x|x<-xs]
-- | 再帰版
map2 _ [] = []
map2 f (x:xs) = f x:map f xs
-- | 右畳込み版
-- | map3 f xs = foldr (\y ys->f y:ys) [] xs
map3 f = foldr (\y ys->f y:ys) []
-- | 右畳込み版 trace付き
map4 :: (Show a,Show b) =>(a->b)->[a]->[b]
map4 f = foldr (\y ys -> f y:(trace ("(y,ys)=" ++ show (y,ys)) ys)) []

-- | ユニットテスト
mapTest :: Test
mapTest = test [
    map1 (== 1) ([1,2,1]::[Int]) ~=? [True,False,True],
    map2 (== 1) ([1,2,1]::[Int]) ~=? [True,False,True],
    map3 (== 1) ([1,2,1]::[Int]) ~=? [True,False,True],
    map4 (*2) ([1,2,3]::[Int]) ~=? [2,4,6],
    (take 10 $ map1 even ([1..]::[Int])) ~=? (take 10 $ map even ([1..]::[Int])),
    True ~=? True
 ]

----------------------------------------------------
-- | main
main :: IO ()
main = do
  _ <- runTestTT applyNtimesTest
  quickCheck prop_applyNtimes
  _ <- runTestTT concatTest
  quickCheck prop_concat
  print $ take 10 $ alist
  print $ take 10 $ blist
  _ <- runTestTT ablistTest
  _ <- runTestTT countTest
  _ <- runTestTT insertTest
  _ <- runTestTT mapTest
  return ()


プロフィール

島敏博

Shima Toshihiro 島敏博
信州アルプスハイランド在住。HaskellとElixirが好き。組み込みソフトウェアアーキテクト、C++プログラマ、山歩き、美術館巡り、和食食べ歩き、日本赤十字社救急法指導員、インデックス投資、クラシック音楽、SESSAME会員、状態マシン設計、モデル駆動開発、ソフトウェアプロダクトライン、Rubyist、実践ビジネス英語

■ ツイッター
http://twitter.com/saltheads
■ Facebook
http://www.facebook.com/saltheads
■ Qiita
http://qiita.com/saltheads

印刷する場合は、ブラウザの印刷メニューではなく、このページの上から3cmくらいの青いところにある、「印刷」を押してみてください。少しうまく印刷できます。まだ完全ではないのですが、これで勘弁してください。


カテゴリ
最新記事
月別アーカイブ
最新コメント
検索フォーム
リンク
sessame
RSSリンクの表示