Real World Haskell 3. 型定義、ストリーミング関数 再帰型
再帰型の例にある List 型を使ってリストっぽいことをやってみた。
data List a = Cons a (List a) | Nil deriving (Eq, Ord, Show) cons a b = Cons a b car (Cons x _ ) = x cdr (Cons _ xs) = xs strToLs [] = Nil strToLs (x:xs) = cons x (strToLs xs) lsToStr Nil = "" lsToStr (Cons x xs) = x:lsToStr xs
ghci> cons 'a' Nil Cons 'a' Nil ghci> let abc =cons 'a' $ cons 'b' $ cons 'c' Nil ghci> abc Cons 'a' (Cons 'b' (Cons 'c' Nil)) ghci> car abc 'a' ghci> cdr abc Cons 'b' (Cons 'c' Nil) ghci> let str = strToLs "Hello" ghci> str Cons 'H' (Cons 'e' (Cons 'l' (Cons 'l' (Cons 'o' Nil)))) ghci> car str 'H' ghci> cdr str Cons 'e' (Cons 'l' (Cons 'l' (Cons 'o' Nil))) ghci> cdr $ cdr str Cons 'l' (Cons 'l' (Cons 'o' Nil)) ghci> lsToStr str "Hello"
deriving に Eq, Ord を追加したので比較が出来る。
ghci> let str = strToLs "Hello" ghci> let str2 = strToLs "Hello" ghci> let str3 = strToLs "Hello!" ghci> str==str2 True ghci> str==str3 False ghci> strToLs "1" > strToLs "2" False ghci> strToLs "1" < strToLs "2" True ghci> str > str3 True ghci> str< str3 False
p61「猫の足跡のような囲み記事の説明」
組み込まれているリスト型と同じ。「多相型」だからいろんな型のデータが入るよ、ということ。
-- file: ch03/ListADT.hs fromList (x:xs) = Cons x (fromList xs) fromList [] = Nil ghci> fromList [1,2,3] Cons 1 (Cons 2 (Cons 3 Nil)) ghci> fromList "abc" Cons 'a' (Cons 'b' (Cons 'c' Nil)) ghci> fromList [Nothing,Just "hello"] Cons Nothing (Cons (Just "hello") Nil)
Tree型
data Tree a = Node a (Tree a) (Tree a) | Empty deriving (Show) -- Tree を表示する showTree Empty = "" showTree (Node a b c) = a ++ "\n" ++ (showTree b) ++ (showTree c) -- Node の要素を取り出す treeNode (Node node _ _) = node treeLeft (Node _ left _) = left treeRight (Node _ _ right) = right replace _ _ Empty = Empty replace old new node | treeNode node == old = Node new (replace old new (treeLeft node)) (replace old new (treeRight node)) | otherwise = Node (treeNode node) (replace old new (treeLeft node)) (replace old new (treeRight node)) treeMap _ Empty = Empty treeMap f node = Node (f (treeNode node)) (treeMap f (treeLeft node)) (treeMap f (treeRight node)) simpleTree = Node "parent" (Node "left child" Empty Empty) (Node "right child" Empty Empty)
ghci> simpleTree Node "parent" (Node "left child" Empty Empty) (Node "right child" Empty Empty) ghci> putStr $ showTree $ simpleTree parent left child right child
ghci> putStr $ showTree $ treeMap (\str->"<<"++str++">>") simpleTree <<parent>> <<left child>> <<right child>>
data Tree a = Node a (Tree a) (Tree a) | Empty deriving (Eq, Ord, Show) gtNode (Node n _ _) = n gtLeft (Node _ l _) = l gtRight (Node _ _ r) = r -- データ挿入 insert :: (Ord a) => a -> Tree a -> Tree a insert x node | node == Empty = Node x Empty Empty | gtNode node == x = node | gtNode node < x = Node (gtNode node) (insert x (gtLeft node)) (gtRight node) | gtNode node >= x = Node (gtNode node) (gtLeft node) (insert x (gtRight node)) -- データ検索 search :: (Ord a) => a -> Tree a -> Maybe a search x node | node == Empty = Nothing | gtNode node == x = Just (gtNode node) | gtNode node < x = (search x (gtLeft node)) | gtNode node >= x = (search x (gtRight node)) lsToTree :: (Ord t) => [t] -> Tree t -> Tree t lsToTree [] tree = tree lsToTree (x:xs) tree = lsToTree xs (insert x tree) t = lsToTree ["hello","world","good","morning","Hey !!"] Empty
