12

30

[Haskell] リストの末尾からk番目の要素を求める

2012.12.30(11:50)

世界で闘うプログラミング力を鍛える150問
http://www.amazon.co.jp/dp/4839942390/
の問題2.2をHaskellで解いてみた。

単方向連結リストにおいて、末尾から数えてk番目の要素を見つけるアルゴリズムを実装してください。

ランナーテクニックを使って2つの問題を解いてみた。問題2.2は後半で解いた。
{-# OPTIONS -Wall -Werror #-}

module Runners where
import Test.HUnit
import Test.QuickCheck

-- | ------------------- 問題1 ----------------------
-- | 「ランナーテクニック」
-- | リストを複数のポインタで同時に巡回することテクニック。たとえば、
-- | 同じリストを1つずつ巡回するポインタと2つずつ巡回するポインタを用意し
-- | 後者が最後まで到達したときに、前者は後半の先頭を指している
runner :: [a]->[a]->[a]
runner xs [] = xs
runner (_:xs) (_:_:ys) = runner xs ys
runner [] [_] = []
runner [] (_:_) = []
runner (_:_) [_] = []

-- | 長さが偶数であるリストの後半を得る関数
secondHalf :: [a]->[a]
secondHalf x = runner x x

-- | 長さが偶数であるリストの後半を得る関数
-- | 長さがわかっていれば後半を求めるのは簡単
secondHalf' :: [a]->[a]
secondHalf' x = drop (halfLength x) x
                where div2 :: Int->Int
                      div2 n = truncate ((fromIntegral n :: Float) / 2.0)
                      halfLength xs = div2 $ length xs

-- | ユニットテスト
secondHalfTest :: Test
secondHalfTest = test [
      secondHalf "" ~=? "",
      secondHalf "ab" ~=? "b",
      secondHalf "abcdef" ~=? "def",
      secondHalf ['\x00'..'\xff']  ~=? ['\x80'..'\xff'],
      --secondHalf [1,2]  ~=? [2],
              True ~=? True
    ]

-- | quickCheck
-- | prop_secondHalf :: (Eq a)=>[a]->Property
-- | 関数的にはこういう型制約のものをテストしたいが、
-- | quickCheck的には型を具体化しないとテストできない。
prop_secondHalf1 :: [Int]->Property
prop_secondHalf1 s = 
                    ((even $ length s) == True) ==>
                    ((secondHalf s) == (secondHalf' s))
prop_secondHalf2 :: String->Property
prop_secondHalf2 s = 
                    ((even $ length s) == True) ==>
                    ((secondHalf s) == (secondHalf' s))

main1 :: IO ()
main1 = do
  putStrLn $ secondHalf "ab"
  putStrLn $ secondHalf "abcdef"
  _ <- runTestTT secondHalfTest
  -- verboseCheck prop_secondHalf
  quickCheck prop_secondHalf1
  quickCheck prop_secondHalf2
  return ()

-- | ------------------- 問題2 ----------------------
-- | 「ランナーテクニック」
-- | 単方向連結リストにおいて、末尾から数えてk番目の要素を見つけるアルゴリズムを実装してください。
-- | 2つのリストをそれぞれ1つずつ巡回して、片方が尽きたときもう片方の先頭が答え。
stepRunner :: [a]->[a]->a
stepRunner (x:_) [] = x
stepRunner (_:xs) (_:ys) = stepRunner xs ys
stepRunner [] _ = error "error"

-- | リスト[a]の末尾からk番目の要素を返す関数
nthToLast :: Int->[a]->a
nthToLast k s = stepRunner s (drop k s)

-- | ユニットテスト
nthToLastTest :: Test
nthToLastTest = test [
      nthToLast 1 "abcd" ~=? 'd',
      nthToLast 2 "abcde" ~=? 'd',
      nthToLast 3 "abcdef" ~=? 'd',
      nthToLast 4 "abcd" ~=? 'a',
      nthToLast 3 "abc" ~=? 'a',
      nthToLast 2 "ab" ~=? 'a',
      nthToLast 1 "a" ~=? 'a',
      nthToLast 1 ([1]::[Int]) ~=? 1,
      nthToLast 2 ([1,2]::[Int]) ~=? 1,
      nthToLast 1 ([1,2]::[Int]) ~=? 2,
              True ~=? True
    ]

main2 :: IO ()
main2 = do
   print $ nthToLast 2 "abcde"
   print $ nthToLast 3 "abcdef"
   print $ nthToLast 1 ([1,2,3]::[Int])
   print $ nthToLast 3 ([1,2,3,4,5,6]::[Int])
   _ <- runTestTT nthToLastTest
   return ()

main :: IO ()
main = do
   main1
   main2


プロフィール

島敏博

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リンクの表示