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