01

11

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

2013.01.11(22:01)

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

{-# OPTIONS -Wall -Werror #-}

module Exercise4 where
import Test.HUnit
import Test.QuickCheck

-- | 100以上999以下の3桁の自然数において、
-- | 百の位と一の位の数字が等しい数は全部でいくつあるか
same31,same31' :: Int
same31  = length [x|x<-([100..999]::[Int]),let (a:_:c:_) = show x,a==c]
same31' = length [x|x<-([100..999]::[Int]),div x 100 == mod x 10]

-- | 型エラーを直す
-- | 以下のプログラムには2つのエラー(Hugsでは3つらしい)がある。
-- | エラーを修正し、正しく動くか確かめよ。
n :: Int
n = a `div` length xs
    where
      a = 10
      xs = ([1, 2, 3, 4, 5]::[Int])

-- | フィボナッチ数列のc番目を返す関数
fib,fib' :: Integer->Integer
fib c = head $ drop (fromInteger c::Int) fibList
        where fibList = 0:1:zipWith (\x y->x+y) fibList (tail fibList)
fib' c = fibs 0 1 !! (fromInteger c::Int)
         where fibs a b = a : fibs b (a+b)

-- | リストの要素を全て足す関数
mySum :: [Int] -> Int
mySum = foldl (+) 0

-- | リストの要素を偶数番目の要素と奇数番目の要素のリストに分ける関数
oddEven :: [Int] -> ([Int], [Int])
oddEven list = halves list [] [] 
    where
        halves []       oddList evenList = (oddList,evenList)
        halves [x]      oddList evenList = (oddList++[x],evenList)
        halves (x:y:ys) oddList evenList = halves ys (oddList++[x]) (evenList++[y])

-- | リストの要素を偶数の要素と奇数の要素のリストに分ける関数
oddEven2, oddEven2' :: [Int] -> ([Int], [Int])
oddEven2 list = ([x|x<-list,odd x],[x|x<-list,even x])
oddEven2' list = (filter odd list,filter even list)

-- | ランレングス解凍
-- | ほんとうは[(Int,Int)]->[Int]の出題のほうが良い。
uncompress :: [[Int]] -> [Int]
uncompress list = uncs [] list
      where uncs result []     = result
            uncs result (x:xs) = uncs (result ++ (replicate t r)) xs
                                 where t:r:_ = x
                                       [_] = error "data input error"

-- | Int->Intであるlog2を実装する
log2,log2' :: Int->Int
log2 c
  | c < 1     = error "log input error"
  | otherwise = head [b | (a,b)<-zip (iterate (*2) 1) [-1..], c<a] 
log2' c
  | c < 1     = error "log input error"
  | otherwise = log2x c 0
                where log2x e f
                         | e < 2     = f
                         | otherwise = log2x (div e 2) (succ f)

-- | ユニットテスト
recTest :: Test
recTest = test [
                same31 ~=? 90,
               same31' ~=? 90,
                    n  ~=? 2,
   (fib (0::Integer))  ~=? 0,
   (fib (1::Integer))  ~=? 1,
   (fib (20::Integer))  ~=? 6765,
   (fib (100::Integer)) ~=? 354224848179261915075,
   (mySum [1..4])   ~=? 10,
   (oddEven [1,4,5,6,7,10,11]) ~=? ([1,5,7,11],[4,6,10]),
   (oddEven [1..9])  ~=? ([1,3,5,7,9],[2,4,6,8]),
   (oddEven [1..10]) ~=? ([1,3,5,7,9],[2,4,6,8,10]),
   (uncompress [[3,1],[1,0],[1,1],[4,0],[1,1]]) ~=? [1,1,1,0,1,0,0,0,0,1],
   (log2 (1::Int))   ~=? 0,
   (log2 (2::Int))   ~=? 1,
   (log2 (3::Int))   ~=? 1,
   (log2 (4::Int))   ~=? 2,
   (log2 (7::Int))   ~=? 2,
   (log2 (8::Int))   ~=? 3,
   fmap log2 [1..100] ~=? fmap log2' [1..100],
   True ~=? True
 ]

-- | quickCheck
prop_fib :: Integer->Property
prop_fib c = (0<c) && (c < 100) 
             ==> fib c == fib' c

prop_log2 :: Int->Property
prop_log2 c = (0<c) && (c < 20) 
              ==> d <= c && c < d*2
              where e = log2 c
                    d = 2^e

prop_log2' :: Int->Property
prop_log2' c = (0<c) && (c < 20) 
          ==> log2 c == log2' c

main :: IO ()
main = do
         print $ same31
         print n
         print $ fib (0::Integer)
         print $ fib (1::Integer)
         print $ fib (20::Integer)
         print $ fib (100::Integer)
         print $ mySum [1..4]
         print $ oddEven [1,4,5,6,7,10,11]
         print $ oddEven [1..9]
         print $ oddEven [1..10]
         print $ oddEven2 [1,4,5,6,7,10,11]
         print $ oddEven2 [1..9]
         print $ oddEven2 [1..10]
         print $ oddEven2 [1,3,5,7,9,2,4,6,8,10]
         print $ uncompress [[3,1],[1,0],[1,1],[4,0],[1,1]]
         _ <- runTestTT recTest
         quickCheck prop_fib
         quickCheck prop_log2
         quickCheck prop_log2'
         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リンクの表示