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

Question

Я пытаюсь сделать некоторую абстракцию в 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

или

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

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

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

Вероятно, вы захотите выбрать последний вариант для класса 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]