すごいH本 part47 - fugafuga.write

再帰的なデータ構造

データ型の定義時に再帰構造を作ることができる

例としてオリジナルのリスト型を作りながら見ていく

*Main> [5]
[5]
*Main> 5 : []
[5]
*Main> [4,5,6,7]
[4,5,6,7]
*Main> 4 : 5 : 6 : 7 : []

リストデータ型のデータ構造としては、

空リスト または 要素とリスト(空リストでも可) を `:` で結合したもの

となる。

data List a = Empty | Cons a (List a) deriving (Show, Read, Eq, Ord)

レコード構文で書き直すとこうなる。

data List a = Empty | Cons { listhead :: a, listTail :: List a }
  deriving (Show, Read, Eq, Ord)

Cons は : と同義の値コンストラクタ。値とリストを取ってリストを返す。

*Main> Empty
Empty
*Main> 5 `Cons` Empty
Cons {listhead = 5, listTail = Empty}
*Main> 4 `Cons` (5 `Cons` Empty)
Cons {listhead = 4, listTail = Cons {listhead = 5, listTail = Empty}}

リストを改善する

記号文字だけ使って関数に名前をつけると自動的に中置関数になる。値コンストラクタもデータ型を返す関数なので同じルールで宣言できる。ただし、値コンストラクタを中置関数にする場合、値コンストラクタの名前は:で始まる必要がある。

infixr 5 :-:
data List a = Empty | a :-: (List a) deriving (Show, Read, Eq, Ord)

infixr 5 :-: は結合性の宣言と呼ばれるもの。必須ではない。この宣言で演算子の結合順位や、左結合 or 右結合を指定する。

例の場合、infixr の r で右結合。結合順位は5。

他の例としては、infixl 7 * や infixl 5 + がある。この場合は、* の方が結合順位が高く、どちらとも左結合(infixl)である。

左結合なので 4 * 3 * 2 が (4 * 3) * 2 となる。

* の方が結合が強い(数字が大きい)ので、5 + 4 * 3 が 5 + (4 * 3) となる。

*Main> 3 :-: 4 :-: 5 :-: Empty
3 :-: (4 :-: (5 :-: Empty))
*Main> let a = 3 :-: 4 :-: 5 :-: Empty
*Main> 100 :-: a
100 :-: (3 :-: (4 :-: (5 :-: Empty)))

オリジナルのリストの連結(++)を作る

infixr 5 ^++
(^++) :: List a -> List a -> List a
Empty ^++ ys = ys
(x :-: xs) ^++ ys = x :-: (xs ^++ ys)

実行

*Main> let a = 3 :-: 4 :-: 5 :-: Empty
*Main> let b = 6 :-: 7 :-: Empty
*Main> a ^++ b
3 :-: (4 :-: (5 :-: (6 :-: (7 :-: Empty))))

結合できている。

パターンマッチは値コンストラクタであれば何に対してでも使える。 (x :-: xs)というパターンマッチを使っているがこれは値コンストラクタなので可能となっている。 8 や 'a' なども、数値型や文字型の値コンストラクタなのでパターンマッチができている。 [] も同じ理由でパターンマッチができる。