繰り返し

Question

私は、バイナリツリーデータ構造を定義することができます。

data Tree a = Leaf | Node a (Tree a) (Tree a) 

は今、私は、各Nodeは10サブツリーを有するようなツリーを作成します。私は1(Tree a)を書き出すことでそうすることができましたが、より合理的な方法がありますか？私はタイプの家族がここで助けるかもしれないと思っているが、私は確信していない。

Answer 1

分岐レベルがタイプレベルで決定され、任意の自然数である可能性があります。これはGADTsとかなり簡単である：

data Nat = Z | S Nat 

data Vec (n :: Nat) a where 
    Nil :: Vec 'Z a 
    (:>) :: a -> Vec n a -> Vec ('S n) a 
infixr 5 :> 

data Tree k a = Leaf | Node a (Vec k (Tree k a)) 

VecがGADTsと均質長インデックスベクトルを符号化するための標準的な方法（例えばhere見出さ）。ツリー内のノードはタイプaの要素と長さがkのベクトルです。ここで、ベクトルの各要素はサブツリーです。

バイナリツリーは、単に

type BinaryTree = Tree ('S ('S 'Z)) 

と構築している推論された型はNum a => Tree ('S ('S 'Z)) aなります

単に

tree = Node 1 (Node 2 (Leaf :> Leaf :> Nil) :> Leaf :> Nil) 

です。

しかし、あなたが本当に10個のノードが必要な場合は、10 'Sを書くことは、まだあまりにも退屈なので、あなたがタイプリテラルを使用することもできます。

import qualified GHC.TypeLits as TL 

... 

type family N (n :: TL.Nat) :: Nat where 
    N 0 = 'Z 
    N n = 'S (N (n TL.- 1)) 

type Tree10 = Tree (N 10) 

これは、あなたが好きな分岐率であなたの木を与えるだけでなく、しかし、あなたがさらに分岐ファクタの多型であり、関数を記述することができ、GHCはすべて無料で、次のあなたを与える：

-- With StandaloneDeriving, DeriveFunctor, DeriveFoldable, DeriveTraversable 
deriving instance Functor (Vec k) 
deriving instance Foldable (Vec k) 
deriving instance Traversable (Vec k) 

deriving instance Functor (Tree k) 
deriving instance Foldable (Tree k) 
deriving instance Traversable (Tree k)