LYH 7.7 再帰的なデータ構造
代数(的)データ型の3種類を言え。( 1 )
リストは ( 2 ) または ( 3 ) のいずれかの値を取るデータ構造である。
代数データ型を使って独自のリスト型 List a を実装せよ。( 4 )
( 4 ) をレコード構文を用いて書け。( 5 )
Cons とは ( 6 ) を言い換えたものである。Haskell標準の ( 6 ) は、値とリストをとってリストを返す ( 7 ) である。( 6 ) には、( 8 ) と ( 9 ) の2つのフィールドがあるといえる。
リストの改善
記号文字だけを使って関数に名前をつけると ( 10 ) になる。値コンストラクタも ( 11 ) であるので同様。
ただし、値コンストラクタの名前は ( 12 ) で始まる必要がある。
結合性宣言を infixr 5 とした上で、Cons a (List a) と同等の値コンストラクタ a :-: (List a) を定義せよ。( 13 )
結合性宣言は必須ではないので、これを除けば Cons a (List a) と同等という意味。結合性宣言を省略した演算子はすべて infixl 9 となる。
標準のリストにおける ++ と同等の、独自のリスト型List aにおける ^++ の定義を書け。ただし、結合性宣言の数字は 5 である。( 14 )
パターンマッチとは、( 15 ) をマッチさせることに他ならない。なので、( 14 ) のコードにおいて ( 16 ) というパターンマッチを使うことができる。
パターンマッチは ( 15 ) であれば何に対してでも使えるので、(今まで :-: などの中置コンストラクタについてパターンマッチさせてきたが)通常の前置コンストラクタもパターンマッチできる他、( 17 ) や ( 18 ) といったものもパターンマッチできる。これらは数値型や文字型の ( 15 ) だからからである。
木を植えよう
二分木のデータ型Tree aを実装せよ。ただしShow型のインスタンスであるものとする。( 19 )
二分木を作るための2つの関数を実装せよ。( 20 )
ある要素が二分木に属しているか判定する関数を作れ。( 21 )
リストから要素を1つずつ辿って値を生成する操作は畳み込みを使うのが便利である。畳み込みを用いて、リストnumsから生成された木numsTreeを作れ。( 22 )
解答
1. 列挙型、直積型、直和型
2. 空リスト
3. 要素とリストを: で結合したもの
4.
data List a = Empty | Cons a (List a) deriving (Show, Read, Eq, Ord)
5.
data List a = Empty | Cons { listhead :: a, listTail :: List a }
deriving (Show, Read, Eq, Ord)
6. :
7. 値コンストラクタ
8. a型
9. List a型
10. 中置換数
11. データ型(= 引数をとって新しい型の値を生成する)を返す関数
12. : (コロン)
13.
infixr 5 :-: data List a = Empty | a :-: (List a) deriving (Show, Read, Eq, Ord)
14.
infixr 5 ^++ (^++) :: List a -> List a -> List a Empty ^++ ys = ys (x :-: xs) ^++ ys = x :-: (xs ^++ ys)
15. 値コンストラクタ
16. (x :-: xs)
17. 8 (具体的な数値型であれば何でもよい)
18. 'a' (具体的な文字型であれば何でも良い)
19.
data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)
20.
singleton :: a -> Tree a singleton x = Node x EmptyTree EmptyTree treeInsert :: (Ord a) => a -> Tree a -> Tree a treeInsert x EmptyTree = singleton x treeInsert x (Node a left right) | x == a = Node x left right | x < a = Node a (treeInsert x left) right | x > a = Node a left (treeInsert x right)
21.
treeElem :: (Ord a) => a -> Tree a -> Bool treeElem x EmptyTree = False treeElem x (Node a left right) | x == a = True | x < a = treeElem x left | x > a = treeElem x right
22.
numsTree :: Tree Int numsTree = foldr treeInsert EmptyTree nums