несколько параметров типа в классах типа Haskell

Я пытаюсь сделать некоторую абстракцию в Haskell98, но не знаю, как это сделать.

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

toList :: a -> [b]

Но я не знаю, как определить класс для этого метода. Я выдвинул следующие три идеи:

class ToList a b where
    toList :: a -> [b]

class ToList a where
    toList :: a -> [b]

class ToList a where
    toList :: a b -> [b]

Первый не работает, потому что Haskell98 не поддерживает несколько классов параметров.

Второй не работает, потому что b зависит от a и не может быть реализован для каждого b.

Третий тоже не работает, потому что я не знаю, как создать экземпляр класса с типом, где «b» не является последним параметром типа.

data HTree a b = Nil | Node a b (HTree a b) (HTree a b)

toList Nil = []
toList Node x y l r = toList l ++ [(x,y)] ++ toList r

or

toList Nil = []
toList Node x y l r = toList l ++ [x] ++ toList r

Как бы я сделал что-то подобное?


typeclass haskell
person Thomas Danecker    schedule 21.11.2008    source источник

Ответы (3)


arrow_upward
9
arrow_downward

См. также Data.Foldable в стандартная библиотека, которая предоставляет функцию toList для любого экземпляра Foldable. Foldable для создания экземпляра требуется немного изощренности, но это было бы хорошей практикой. В качестве бонуса ваш тип HTree почти точно такой же, как пример экземпляра в документации.

Кроме того, я рекомендую изменить ваш HTree на:

data HTree a = Nil | Node a (HTree a) (HTree a)

А затем использовать HTree (a,b) вместо HTree a b. Эту версию с одним параметром будет легче компоновать со стандартными типами и экземплярами, и она более точно отражает суть происходящего, поскольку она одинаково зависит от обоих параметров. Это также Functor, и определение такого экземпляра сделает работу с этим типом действительно приятной.

person luqui    schedule 23.11.2008

arrow_upward
4
arrow_downward

Я бы рекомендовал классы типов не так полезны, как они сначала кажется - если предполагаемый класс имеет только один метод интерфейса, рассмотрите вместо этого объявление типа функции. Я тоже пришел из OO и обнаружил, что потратил слишком много времени, пытаясь заставить «класс» означать то, что я думал, когда на самом деле я должен был использовать «данные».

Гораздо проще просто написать функцию toList, а затем «поднять» ее для работы с вашей структурой данных. На самом деле, знаменитый Еще один учебник по Haskell проходит обширный упражнение, показывающее, как это делается, и использует двоичное дерево в качестве примера. Самое замечательное в выполнении подъема то, что он различает, что важно - структура типа данных, а не реализация toList' - поэтому, как только подъем будет выполнен для выполнения "обхода типа данных по порядку", вы можете использовать подъем для делать что угодно - toList, печать, что угодно. Поддержка toList не является важной частью структуры данных, поэтому ее не должно быть в объявлении класса — важной частью является то, как проходить структуру данных.

person Chris    schedule 21.11.2008

arrow_upward
-1
arrow_downward

Вероятно, вы захотите выбрать последний вариант для класса ToList и создать (HTree a) экземпляр ToList. Тогда toList имеет тип (HTree a b) -> [b], а не, например, (HTree a b) -> [(a,b)]. Я предполагаю, что вы думаете о типе a как о «ключе», а b как о типе значения.

class ToList a where
    toList :: a b -> [b]

data HTree a b = Nil | Node a b (HTree a b) (HTree a b)

instance ToList (HTree a) where
    toList Nil = []
    toList (Node x y l r) = toList l ++ [y] ++ toList r

test = toList (Node "a" 1 (Node "b" 2 Nil Nil) Nil)
-- test == [2,1]
person mattiast    schedule 22.11.2008