Предельный набор типов с новыми данными, такими как `Tree a` - PullRequest
Новая
       83

Предельный набор типов с новыми данными, такими как `Tree a`

2 голосов
/ 28 июня 2019

Изучая и изучая систему типов в Хаскеле, я обнаружил некоторые проблемы.

1) Давайте рассмотрим полиморфный тип как двоичное дерево: 

 data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving Show

И, например, я хочу ограничить свои соображения только Tree Int, Tree Bool и Tree Char. Конечно, я могу сделать такой новый тип: 

data TreeIWant = T1 (Tree Int) | T2 (Tree Bool) | T3 (Tree Char) deriving Show

Но можно ли было сделать новый ограниченный тип (для однородных деревьев) более элегантным (и без новых тегов, таких как T1, T2, T3) (возможно, с некоторыми расширенными расширениями типов)?

2) Второй вопрос о деревьях с неоднородными значениями. Я могу делать их с обычным Haskell, то есть я могу делать новый тип помощи, содержащий размеченные разнородные значения: 

data HeteroValues = H1 Int | H2 Bool | H3 Char deriving Show

, а затем создайте дерево со значениями этого типа: 

type TreeH = Tree HeteroValues

Но можно ли было сделать новый тип (для разнородных деревьев) более элегантным (и без новых тегов, таких как H1, H2, H3) (возможно, с некоторыми расширенными расширениями типов)? Я знаю про гетерогенный список , возможно, это тот же вопрос?

1 Ответ

2 голосов
/ 28 июня 2019

Для вопроса №2 легко создать «ограниченный» гетерогенный тип без явных тегов, используя GADT и класс типов: 

{-# LANGUAGE GADTs #-}
data Thing where
  T :: THING a => a -> Thing
class THING a

Теперь объявите THING экземпляров для вещей, которые вы хотите разрешить: 

instance THING Int
instance THING Bool
instance THING Char

и вы можете создать Things и списки (или деревья) из Things: 

> t1 = T 'a'       -- Char is okay
> t2 = T "hello"   -- but String is not
... type error ...
> tl = [T (42 :: Int), T True, T 'x']
> tt = Branch (Leaf (T 'x')) (Leaf (T False))
>

С точки зрения имен типов в вашем вопросе, у вас есть: 

type HeteroValues = Thing
type TreeH = Tree Thing

Вы можете использовать тот же класс типов с новым GADT для вопроса № 1: 

data ThingTree where
  TT :: THING a => Tree a -> ThingTree

и у вас есть: 

type TreeIWant = ThingTree

и вы можете сделать: 

> tt1 = TT $ Branch (Leaf 'x') (Leaf 'y')
> tt2 = TT $ Branch (Leaf 'x') (Leaf False)
... type error ...
>

Это все хорошо, пока вы не попытаетесь использовать любое из построенных вами значений. Например, если вы хотите написать функцию для извлечения Bool из, возможно, глупого Thing: 

maybeBool :: Thing -> Maybe Bool
maybeBool (T x) = ...

Вы бы застряли здесь. Без какого-либо «тега» невозможно определить, является ли x Bool, Int или Char.

На самом деле у вас do есть неявный доступный тег, а именно словарь классов типа THING для x. Итак, вы можете написать: 

maybeBool :: Thing -> Maybe Bool
maybeBool (T x) = maybeBool' x

и затем реализовать maybeBool' в вашем классе типов: 

class THING a where
  maybeBool' :: a -> Maybe Bool
instance THING Int where
  maybeBool' _ = Nothing
instance THING Bool where
  maybeBool' = Just
instance THING Char where
  maybeBool' _ = Nothing

и ты золотой!

Конечно, если вы использовали явные теги: 

data Thing = T_Int Int | T_Bool Bool | T_Char Char

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

maybeBool :: Thing -> Maybe Bool
maybeBool (T_Bool x) = Just x
maybeBool _ = Nothing

В итоге получается, что лучшее представление на Хаскелле алгебраической суммы трех типов - это просто алгебраическая сумма трех типов: 

data Thing = T_Int Int | T_Bool Bool | T_Char Char

Попытка избежать необходимости в явных тегах, вероятно, приведет к большому количеству неэлегического шаблона в других местах.

Обновление: Как отметил @DanielWagner в комментарии, вы можете использовать Data.Typeable вместо этого шаблона (фактически, GHC генерирует для вас много шаблона), поэтому вы можете написать: 

import Data.Typeable

data Thing where
  T :: THING a => a -> Thing
class Typeable a => THING a

instance THING Int
instance THING Bool
instance THING Char

maybeBool :: Thing -> Maybe Bool
maybeBool = cast

Поначалу это может показаться "элегантным", но если вы попробуете этот подход в реальном коде, я думаю, вы пожалеете о том, что потеряете возможность сопоставления с шаблоном на конструкторах Thing на сайтах использования (и, следовательно, будете вынуждены заменять цепочки cast с и / или сравнения TypeRep с).

...