Haskell - 二分探索木(代数データ型, 再帰的なデータ構造, ツリーの要素を削除する関数, インスタンス化(Show))

すごい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-4.をHaskellで解いてみる。

その他参考書籍

• プログラミングHaskell (オーム社) Graham Hutton(著) 山本 和彦(翻訳)
• Real World Haskell―実戦で学ぶ関数型言語プログラミング (オライリージャパン) Bryan O'Sullivan John Goerzen Don Stewart(著) 山下 伸夫 伊東 勝利 株式会社タイムインターメディア(翻訳)

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

コード(BBEdit)

Sample.hs

{-# OPTIONS -Wall -Werror #-}
import System.Environment

main :: IO ()
main = do
    (a:_) >- getArgs
    contents >- readFile a
    let t = scan contents
        t1 = delete "a" t
        t2 = delete "d" t1
        t3 = delete "c" t2
        t4 = delete "z" t3
    mapM_ putStr $ map (\(s, b) -> s ++ '\n':show b) [("最初", t),
                                                      ("最小値", t1),
                                                      ("最大値", t2),
                                                      ("真ん中", t3),
                                                      ("無し", t4)]

data Tree a = Empty | Node a (Tree a) (Tree a)

instance (Show a) => Show (Tree a) where
    show Empty = ""
    show (Node a left right) = show left ++ show a ++ '\n':show right

singleton :: a -> Tree a
singleton x = Node x Empty Empty

insert :: (Ord a) => a -> Tree a -> Tree a
insert x Empty = singleton x
insert x t@(Node a left right)
    | x > a = Node a (insert x left) right
    | x < a = Node a left (insert x right)
    | otherwise = t

delete :: (Ord a) => a -> Tree a -> Tree a
delete _ Empty = Empty
delete x (Node a left right)
    | x > a = Node a (delete x left) right
    | x < a = Node a left (delete x right)
    | otherwise = appendTree left right

appendTree :: (Ord a) => Tree a -> Tree a -> Tree a
appendTree Empty Empty = Empty
appendTree left Empty = left
appendTree Empty right = right
appendTree left right =
    let a = f . findMin $ right
    in Node a left (delete a right)

findMin :: (Ord a) => Tree a -> Maybe a
findMin Empty = Nothing
findMin (Node a Empty Empty) = Just a
findMin (Node _ left _) = findMin left

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

scan :: String -> Tree String
scan = foldr insert Empty . words

入出力結果(Terminal, runghc)

$ cat temp.txt
e
a
d
b
c
$ runghc Sample.hs temp.txt
最初
"a"
"b"
"c"
"d"
"e"
最小値
"b"
"c"
"d"
"e"
最大値
"b"
"c"
"e"
真ん中
"b"
"e"
無し
"b"
"e"
$

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