数据构造函数中的重复

Question

我可以定义一个二叉树数据结构：

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

现在我想创建一棵树，这样每个Node都有10个子树。我可以写出10个(Tree a)s，但是有没有更好的方法呢？我想这种类型的家庭可能会有所帮助，但我不确定。

Answer 1

看起来你想要一棵树，它的分支因子是在类型级别上决定的，可以是任何自然数。这在GADT中相当简单：

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是使用GADT(例如here)对同质长度索引向量进行编码的标准方法。因此，树中的节点是一个类型为a的元素和一个长度为k的向量，其中向量的每个元素都是一个子树。

二叉树是简单的

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

而构建过程很简单

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

推断的类型将是Num a => Tree ('S ('S 'Z)) a。

但是如果你真的需要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)