Использование Data.Heap в Haskell или чтение документов на Haskell для начинающих

Question

Я пытаюсь использовать модуль Haskells Data.Heap, но я не могу даже использовать его с целыми числами. Единственная куча, которую я смог использовать, это «пустая», которая не принимает никаких аргументов.

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

Answer 1

Обычно библиотеки структур данных в Haskell предоставляют fromList функции для преобразования из списка в эту структуру. Data.Heap не является исключением. Но вы получите некоторые сумасшедшие ошибки при попытке использовать его:

Prelude Data.Heap> Data.Heap.fromList [1,2,5,7]

<interactive>:1:0:
    Ambiguous type variables `t', `pol' in the constraint:
      `HeapItem pol t'
        arising from a use of `fromList' at <interactive>:1:0-27
    Probable fix: add a type signature that fixes these type variable(s)

....

Этот главный момент здесь Неоднозначный тип . Существует несколько типов куч, например MaxHeap и MinHeap, которые нельзя вывести из простого вызова fromList. Вы должны указать Haskell, какую кучу вы используете с сигнатурой типа :

Prelude Data.Heap> Data.Heap.fromList [1,2,5,7] :: MinHeap Int
fromList [(1,()),(2,()),(5,()),(7,())]

Другие конструкторы, например singleton, fromAscList и т. Д. Работают аналогично.

Как только вы построили кучу, все остальное легко, например, вставить элемент в кучу

Prelude Data.Heap> let heap = Data.Heap.fromList [1,2,5,7] :: MinHeap Int
Prelude Data.Heap> heap
fromList [(1,()),(2,()),(5,()),(7,())]
Prelude Data.Heap> Data.Heap.insert 3 heap
fromList [(1,()),(3,()),(2,()),(5,()),(7,())]

Чтобы прочитать вершину кучи

Prelude Data.Heap> heap
fromList [(1,()),(2,()),(5,()),(7,())]
Prelude Data.Heap> viewHead heap
Just 1

и т.д.