Блог

Главная - Вопросы по программированию - Повторение в конструкторе данных

Повторение в конструкторе данных

#haskell

#haskell

Вопрос:

Я могу определить структуру данных двоичного дерева:

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

Теперь я хочу создать дерево таким образом, чтобы каждое Node из них имело 10 поддеревьев. Я мог бы сделать это, выписав 10 (Tree a) секунд, но есть ли более разумный способ? Я думаю, что семейства типов могут здесь помочь, но я не уверен.

Комментарии:

1. Использование такого дерева может быть громоздким. Простым решением было бы просто сохранить список дочерних data Tree a = Leaf | Node a [Tree a] элементов и установить ограничение в 10 дочерних элементов во время выполнения. Более сложный ответ будет использовать целые числа уровня типа для ограничения второго аргумента Node списками длины 10.

2. Следующее заклинание должно произноситься с языком, плотно прижатым к щеке: type Triple t = (t, t, t); data Tree t = Tea | Timber t (Tree t) (Triple (Triple (Tree t))) .

Ответ №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 (найденный, например, здесь ). Тогда узел в дереве является элементом типа 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 узлов, выписывать десять '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)