Haskell множественные функторы

Question

Я делаю реализацию кучи Фибоначчи в Haskell, и я не уверен, какой именно способ это сделать.

Например, я хочу заказать узлы. Так что я могу сделать что-то вроде:

instance Ord (FibNode e) where
  f1 `compare` f2 = (key f1) `compare` (key f2)

Это было бы легче сделать, если бы я сделал FibNode монадой. Но в других случаях я хочу свернуть братьев и сестер узла или их детей и т. Д. Итак, определив функтор, где f x = f $ key x не будет работать постоянно.

Помимо определения моего собственного fmapKey, fmapSibs, fmapKids ... есть ли способ сделать это?

Answer 1

Вы не можете сделать конструктор типа экземпляром Functor несколькими способами. Но вы можете создавать различные оболочки нового типа вокруг вашего типа, каждый из которых имеет свой собственный экземпляр Functor. Но на самом деле это не более удобно, чем определение собственных функций fmap.

Answer 2

Куча (Фибоначчи) - это изначально нечистая, деструктивно обновляемая структура данных с определенными асимптотическими гарантиями времени выполнения для различных операций над ней .Я был бы удивлен, если бы вы могли поддержать эти гарантии простым переводом в чистую версию.Мое предложение состоит в том, чтобы сделать ее нечистой структурой данных, используя что-то вроде массивов ST или IO.Это сделало бы намного более прямую реализацию классических алгоритмов.