リストの自由度
Haskellのリストの自由度のこと、ちょっと見直してみました。
リストの決まりごとは：
同じ型の要素しか保持できない。
[1, 2, 3] -- ok
[1, 'a', 3.4] -- NG
逆に、型が同じであればいくつあってもかまわない。
[ ], [1], [2, 3], [1..] :: [Int]
この２つのルールで、ネストの深さの違うリストは同じ型にはならないことがわかります。
[a] != [ [a] ]
それと同時に：
[ [1], [ [2, 3], [4] ], 0]
なんていうリストも許されないことがわかります。つまり、リストを使ってツリー構造を表現する場合は全ての枝の深さが同じじゃないといけないということですね…
でも、以上の条件を守りさえすれば、リストの深さはどれだけ深くても問題なさそうですよね？
それでちょっと思ったのですが、リストの深さを返す関数というのはHaskellではどうやって書けばいいでしょう？まず最初に思いついたのは：
depth :: a -> Int
depth [ ] = 1
depth (x:xs) = 1 + max $ map (depth (x:xs))
みたいなコードなわけですが、型宣言ではaをとる関数としたdepthですが、コードはa = [b]とはっきりと宣言してしまってますよね...これだと depth[ [4] ]なんてやったときに、最初の再帰(depth [4])はうまくいくのでしょうが、その次にdepth 4となったときにパラメタの型がリストじゃないので動かないですね…
僕の知っている限りでは、Haskellでは関数のパラメタの型が不定であることは許されていなかったと思います。ということで、単純に関数でリストの深さを返すコードを書くことはおそらく不可能？（違ってたら教えてください。）とおもわれます。
もうちょっと考えて思ったのは、showのことです。
show [1] = "[1]"
show [ [1], [2, 3] ] = "[ [1], [2, 3] ]"
とリストの深さにかかわらずちゃんと動きますね…
どうなってるのか調べてみたら、showはShowクラスを使って成り立っているようです。要するに、showできる全ての型は皆Showのクラスインスタンスということで、さまざまな型の違いを乗り越えて、表示をすることができるということらしいです。
ということは、Showに似たようなアプローチでクラスを定義して、全てのクラスをそのインスタンスにすれば、depthみたいな関数が表現できるかもしれません：
class Nestable a where
depth :: a -> Int
instance Nestable [ ] where
depth [a] = 1 + (depth a)
:
と、ここまでは簡単そうなのですが、残り全てのクラス型に対してこれをやるのはちょっと骨が折れそうですね...デフォルトクラスインスタンスなんてのはできるんだろうか…
これがよく見かけるTree型だったら、値もツリー構造自身もその型定義の範疇なので、こういった問題はないですね…:
module Main where import Data.Function (on) data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a) depth :: Tree a -> Int depth Empty = 0 depth (Leaf a) = 1 depth (Node b1 a b2) = 1 + *1
リストでこうゆうことはできないもんですかねぇ…これは、つまり、深さが可変なデータ構造を表現するのにはリストは向いていないということなのでしょうか...
ではでは。
