Haskell - 順序付き二重リンクリスト(代数データ型, 再帰的なデータ構造)

すごいHaskellたのしく学ぼう!
(オーム社)
Miran Lipovača (著)
田中英行村主崇行 (翻訳)
[Kindle版]

開発環境

OS X Mavericks - Apple(OS)
BBEdit - Bare Bones Software, Inc., Emacs (Text Editor)
Haskell (純粋関数型プログラミング言語)
GHC (The Glasgow Haskell Compiler) (処理系)
The Haskell Platform (インストール方法、モジュール等)

C実践プログラミング第3版 (Steve Oualline (著)、望月康司 (監訳) (翻訳)、谷口功 (翻訳)、オライリー・ジャパン)のⅢ部(高度なプログラミング概念)の17章(高度なポインタ)、17-12(プログラミング実習)、実習17-3.をHaskellで解いてみる。

その他参考書籍

17-12(プログラミング実習)、実習17-3.

コード(BBEdit)

Sample.hs

{-# OPTIONS -Wall -Werror #-}

main :: IO ()
main = do
    putStrLn "最初"
    print $ getA doubleList
    print $ previous doubleList
    print $ next doubleList
    print doubleList
    let d1 = doubleListRemove 0 doubleList
    putStrLn "0を削除"
    print d1
    let d2 = doubleListRemove 9 d1
    putStrLn "9を削除"
    print d2
    let d3 = doubleListRemove 5 d2
    putStrLn "5を削除"
    print d3
    let d4 = doubleListRemove 10 d3
    putStrLn "10を削除"
    print d4
    let d5 = doubleListRemove 8 . doubleListRemove 7 . doubleListRemove 6 .
             doubleListRemove 4 . doubleListRemove 3 . doubleListRemove 2 .
             doubleListRemove 1 $ d4
    putStrLn "全て削除"
    print d5
    let d6 = doubleListRemove 5 d5
    putStrLn "5を削除"
    print d6

data A a = NULL | B {left :: A a, right :: A a}

data DoubleList a = Empty | Link a (DoubleList a) (DoubleList a)
    deriving (Eq, Show)

getA :: DoubleList a -> Maybe a
getA Empty = Nothing
getA (Link a _ _) = Just a

previous :: DoubleList a -> DoubleList a
previous Empty = Empty
previous (Link _ p _) = p

next :: DoubleList a -> DoubleList a
next Empty = Empty
next (Link _ _  n) = n

mkDoubleList :: a -> DoubleList a
mkDoubleList x = Link x Empty Empty

doubleListAdd :: (Ord a) => a -> DoubleList a -> DoubleList a
doubleListAdd x Empty = mkDoubleList x
doubleListAdd x (Link a p n) =
    if x > a then
        Link a p (doubleListAdd x n)
    else
        Link a (doubleListAdd x p) n

doubleListRemove :: (Ord a) => a -> DoubleList a -> DoubleList a
doubleListRemove _ Empty = Empty
doubleListRemove x (Link a p n)
    | x < a = Link a (doubleListRemove x p) n
    | x > a = Link a p (doubleListRemove x n)
    | otherwise = addDoubleList p n

addDoubleList :: DoubleList a -> DoubleList a -> DoubleList a
addDoubleList x Empty = x
addDoubleList Empty x = x
addDoubleList p n = Link (f . findMin $ n) p (removeMin n)

f :: Maybe a -> a
f Nothing = undefined
f (Just x) = x

findMin :: DoubleList a -> Maybe a
findMin Empty = Nothing
findMin (Link x Empty _) = Just x
findMin (Link _ p _) = findMin p

removeMin :: DoubleList a -> DoubleList a
removeMin Empty = Empty
removeMin (Link _ p Empty) = p
removeMin (Link x p n) = Link x (removeMin p) n

doubleList :: DoubleList Int
doubleList = foldr doubleListAdd Empty ([0..9] :: [Int])

入出力結果(Terminal, runghc)

$ runghc Sample.hs
最初
Just 9
Link 8 (Link 7 (Link 6 (Link 5 (Link 4 (Link 3 (Link 2 (Link 1 (Link 0 Empty Empty) Empty) Empty) Empty) Empty) Empty) Empty) Empty) Empty
Empty
Link 9 (Link 8 (Link 7 (Link 6 (Link 5 (Link 4 (Link 3 (Link 2 (Link 1 (Link 0 Empty Empty) Empty) Empty) Empty) Empty) Empty) Empty) Empty) Empty) Empty
0を削除
Link 9 (Link 8 (Link 7 (Link 6 (Link 5 (Link 4 (Link 3 (Link 2 (Link 1 Empty Empty) Empty) Empty) Empty) Empty) Empty) Empty) Empty) Empty
9を削除
Link 8 (Link 7 (Link 6 (Link 5 (Link 4 (Link 3 (Link 2 (Link 1 Empty Empty) Empty) Empty) Empty) Empty) Empty) Empty) Empty
5を削除
Link 8 (Link 7 (Link 6 (Link 4 (Link 3 (Link 2 (Link 1 Empty Empty) Empty) Empty) Empty) Empty) Empty) Empty
10を削除
Link 8 (Link 7 (Link 6 (Link 4 (Link 3 (Link 2 (Link 1 Empty Empty) Empty) Empty) Empty) Empty) Empty) Empty
全て削除
Empty
5を削除
Empty
$

慣れるまでは{-# OPTIONS -Wall -Werror #-}の記述を消さずに細かく型を指定していくことに。

Kamimura's blog

2013年12月19日木曜日

Haskell - 順序付き二重リンクリスト(代数データ型, 再帰的なデータ構造)

0 コメント:

コメントを投稿