12

30

[Haskell] 最小の要素を返すminを持つスタック

2012.12.30(19:46)

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

問題3.2 pushとpopに加えて、最小の要素を返すminを持つスタックをどのようにデザインしますか?
ただしpush,pop,min関数はすべてO(1)の実行時間になるようにしてください。

リストを使えばpushとpopがO(1)でできることは明らか。
しかしminは、popするたびに変わる可能性がある。minが呼ばれるたびに
調べなおしていたのではO(1)では返せない

たとえば、1,2,3,4,5 をこの順にスタックにいれると
スタックの一番上から順に [5,4,3,2,1]
となり、minは要素がある限り1である

たとえば、5,4,3,2,1 をこの順にスタックにいれると
スタックの一番上から順に [1,2,3,4,5]
となり、minは最初は1であり、1回popすると
スタックの一番上から順に [2,3,4,5]
となり、minは2であり、以下同様に3,4,5と変化する

minをリストを巡回しないで求める問題である

前半で普通のスタックと、そのHUnitテスト、quickCheckを実装し
後半でminを追加したスタックと、そのHUnitテスト、quickCheckを実装した

--{-# OPTIONS -Wall -Werror #-}

module MinStack where
import Test.HUnit
import Test.QuickCheck

-- | ------------------- 問題1 ----------------------
-- | まずは普通のスタック

-- | 空のスタック
empty :: [a]
empty = []

-- | スタックへpush
push :: a->[a]->[a]
push = (:)

-- | スタックからpop
-- | (先頭の値,残りのスタック)のタプルを返す
pop :: [a]->(a,[a])
pop [] = error "no data on the stack"
pop (x:xs) = (x,xs)

-- | リストの要素を先頭から順にスタックにpushする
-- | pushList pushしたい値のリスト スタック
pushList :: [a]->[a]->[a]
pushList [] stack = stack
pushList (x:xs) stack = pushList xs (push x stack)

-- | スタックから要素を全部popしてリストに入れる
popList :: [a]->[a]
popList [] = []
popList stack = popList xs ++ [x]
      where (x,xs) = pop stack

-- | ユニットテスト
stackTest :: Test
stackTest = test [
              (popList $ pushList [1] empty) ~=? [1],
              (popList $ pushList [1,2,3] empty) ~=? [1,2,3],
              (popList $ pushList [1..100] empty) ~=? [1..100],
              [1]==[1] ~=? True,
              True ~=? True
    ]

-- | quickCheck
prop_stack :: [Int]->Bool
prop_stack s = (popList $ pushList s empty) == s

main1 :: IO ()
main1 = do
  let a = ([1,2,3,4]::[Int])
  print a
  let stack1 = push 5 $ empty
  let stack2 = push 3 $ push 4 stack1
  print stack2
  print $ pop stack2
  print $ pop $ snd $ pop stack2
  print $ pop $ snd $ pop $ snd $ pop stack2
  print $ pushList [1..10] empty
  print $ popList $ pushList [1..10] empty
  print $ pushList [10,9..1] empty
  print $ popList $ pushList [10,9..1] empty
  _ <- runTestTT stackTest
  quickCheck prop_stack
  return ()

-- | ------------------- 問題2 ----------------------
-- | 問題3.2 pushとpopに加えて、最小の要素を返すminを持つスタックを
-- | どのようにデザインしますか?
-- | ただしpush,pop,min関数はすべてO(1)の実行時間になるようにしてください。
-- | 普通のスタックを拡張し、要素の最小値を取り出すことができるスタックを作る

-- | 空のminスタック
-- | (値のスタック,最小値のスタック)
minEmpty :: ([a],[a])
minEmpty = ([],[])

-- | minスタックへpush
-- | (値のスタック,最小値のスタック)
-- | 値が最小値のスタックの先頭よりも等しいか小さかったら、最小値のスタックへpush
minPush :: (Ord a,Show a) => a->([a],[a])->([a],[a])
minPush a (stack,minStack) = ((:) a stack,eqOrSmall a minStack)
   where eqOrSmall a []           = [a]
         eqOrSmall a stack@(x:xs) = if a<=x then ((:) a stack) else stack

-- | minスタックからpop
-- | (値のスタック,最小値のスタック)
-- | 値が最小値のスタックの先頭と同じだったら、最小値のスタックからpop
minPop :: (Ord a,Show a)=>([a],[a])->(a,([a],[a]))
minPop ([],_) = error "no data in the stack"
minPop (_,[]) = error "no data in the stack"
minPop ((x:xs),minStack@(y:ys)) = (x,(xs,result))
   where result = if x==y then ys else minStack

-- | minスタックから最小の要素の値を得る
-- | (値のスタック,最小値のスタック)
-- | 最小値のスタックの先頭が、最小値
minValue :: (Ord a,Show a)=>([a],[a])->a
minValue ([],_) = error "no data in the stack"
minValue (_,[]) = error "no data in the stack"
minValue (_,(y:ys)) = y

-- | リストの要素を先頭から順にminスタックにpushする
-- | pushMinList スタックに積みたい値のリスト (値のスタック,最小値のスタック) 
pushMinList :: (Ord a,Show a)=>[a]->([a],[a])->([a],[a])
pushMinList [] tuple = tuple
pushMinList (x:xs) tuple = pushMinList xs (minPush x tuple)

-- | minスタックから要素を全部popしてリストに入れる
popMinList :: (Ord a,Show a)=>([a],[a])->[a]
popMinList ([],_) = []
popMinList tuple = popMinList result ++ [x]
      where (x,result) = minPop tuple

-- | ユニットテスト
minStackTest :: Test
minStackTest = test [
        (popMinList $ minPush 1 $ minEmpty) ~=? [1],
        (popMinList $ minPush 5 $ minPush 4 $ minPush 3 $
                      minPush 2 $ minPush 1 $ minEmpty) ~=? aList,
        (popMinList $ pushMinList aList minEmpty) ~=? aList,
        (popMinList $ pushMinList bList minEmpty) ~=? bList,
        (popMinList $ pushMinList cList minEmpty) ~=? cList,
        (minValue $ minPush 1 $ minEmpty) ~=? 1,
        (minValue $ minPush 2 $ minPush 1 $ minEmpty) ~=? 1,
        (minValue $ minPush 1 $ minPush 2 $ minEmpty) ~=? 1,
        (minValue $ pushMinList aList minEmpty) ~=? minimum aList,
        (minValue $ pushMinList bList minEmpty) ~=? minimum bList,
        (minValue $ pushMinList cList minEmpty) ~=? minimum cList,
        True ~=? True
    ] where aList = ([1..100]::[Int])
            bList = ([100,99..1]::[Int])
            cList = ([3,5,2,6,4,1,7]::[Int])

-- | quickCheck
-- | リストの最小値は、リストをminスタックにpushしたものの最小値と同じ。
prop_minStack :: [Int]->Property
prop_minStack s = (length s > 0) 
                  ==> (minimum s == (minValue $ pushMinList s minEmpty))

main2 :: IO ()
main2 = do
  _ <- runTestTT minStackTest
  quickCheck prop_minStack
  --let a = ([1,2,3,4]::[Int])
  --print a
  let stack1 = minPush 5 $ minEmpty
  let stack2 = minPush 3 $ minPush 2 stack1
  print stack2
  print $ minValue stack2
  --
  let (v3,stack3) = minPop stack2
  print v3
  print stack3
  print $ minValue stack3
  --
  let (v4,stack4) = minPop stack3
  print v4
  print stack4
  print $ minValue stack4
  --
  let (v5,stack5) = minPop stack4
  print v5
  print stack5
  --
  let aList = ([1..5]::[Int])
  print $ pushMinList aList minEmpty
  print $ popMinList $ pushMinList aList minEmpty
  print $ aList == (popMinList $ pushMinList aList minEmpty)
  print $ minimum aList
  print $ minValue $ pushMinList aList minEmpty
  print $ minimum aList == (minValue $ pushMinList aList minEmpty)
  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リンクの表示