O'Reilly logo

Haskell Cookbook by Yogesh Sajanikar

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

How it works...

We implemented a Leftist Tree here. This is a very good example of immutability, data persistence, and in general, how to implement a data structure in Haskell. We started with a representation for a queueheap, and an invariant Leftist property. A typical leftist tree looks like the one shown in this diagram:

Then, we proceeded to implement a mergeQs function, which is at the heart of the implementation. The operations insert and deleteMin both result in an operation that changes the structure of the tree. This change can violate the leftist property or the heap order. The mergeQs function merges two trees and restores these ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required