Understanding data structure in Haskell
I have a homework problem (topic: "functional data structures"). Please understand that I do not want anyone to do my homework. I just have a problem understanding the structure of this:
data Heap e t = Heap {
empty :: t e,
insert :: e -> t e -> t e,
findMin :: t e -> Maybe e,
deleteMin :: t e -> Maybe (t e),
merge :: t e -> t e -> t e,
contains :: e -> t e -> Maybe Int
}
In my understanding, "empty" "insert", etc. are functions that can be applied to heap data. Now I just want to understand what this "heap" looks like. So I was printing things like:
a = Heap 42 42
But I am getting errors that I cannot work with.
Maybe this is a stupid question and I just got stuck on this question for no reason, but now it is killing me. thanks for the help
source to share
If you really want to understand this type, there are a few props you need to understand first.
types and values (and functions)
First, you need to understand what types and values are. I'm going to assume that you understand this. You understand, for example, the separation between "hello"
as a value and its type, String
and you clearly understand what that means when I say a = "hello" :: String
and:
a :: String
a = "hello"
If you don't understand this, you need to research values and types in Haskell. There are tons of books that can help here, like this one I helped the author: http://happylearnhaskelltutorial.com
I'm also going to assume that you understand what functions and curries are, and how to use both of them.
polymorphic types
Second, since your example contains type variables, you need to understand what they are. That is, you need to understand what polymorphic types are. So, for example, Maybe a
or Either a b
, and you need to understand how Maybe String
different from Maybe Int
and what Num a => [a]
and even things like Num a => [Maybe a]
.
Again, there are many free or paid books out there that can help, the example above also covers this.
Algebraic data types
Algebraic data types follow. This is a pretty amazingly cool feature that Haskell has. Haskell-like languages like Elm and Idris have those like others like Rust. It allows you to define types of your own . It's not just things like Structs in other languages, and yes, they can even contain functions.
Maybe
is actually an example of algebraic data types. If you understand this, you will find out that:
data Direction = North | South | East | West
defines a data type called Direction
, the values of which can only be one of North
, South
, East
or West
and you will know that you can also use variables such as polymorphic type above parametrizes their types as follows:
data Tree a = EmptyNode | Node (Tree a) (Tree a)
which uses both optionality (as in the sum type Direction
above) and parameterization.
In addition to this, you can also have multiple types in each value. These are called Product types, and Haskell algebraic data types can be expressed as a combination of the types of sums that Product types can contain. For example:
type Location = (Float, Float)
data ShapeNode = StringNode Location String | CircleNode Location Float | SquareNode Location Float Float
That is, each value can be one of StringNode
, CircleNode
or SquareNode
, and in each case there is a different set of fields for each value. To create StringNode
, for example, you need to pass the value of the constructor as follows: StringNode (10.0, 5.3) "A String"
.
Again, freely available books will go into more detail on these things, but we are moving towards a deeper understanding of Haskell.
Finally, to fully understand your example, you need to know about ...
post types
The record types are similar to the product types above, except that the fields are marked as anonymous. So you can define the data type of the node form like this:
type Location = (Float, Float)
data ShapeNode
= StringNode { stringLocation :: Location, stringData :: String }
| CircleNode { circleLocation :: Location, radius :: Float }
| SquareNode { squareLocation :: Location, length :: Float, height :: Float }
Each field is named and you cannot repeat the same name within data values.
All you need in addition to this to understand the above example is to understand that your example contains all of these things along with the fact that you have functions as the values of your record field in that datatype which you have.
It's a good idea to thoroughly understand your understanding and not skip any steps, then you can more easily follow these things in the future. :) I wish you the best of luck!
source to share
Heap
is a six-element entry. To create a value of this type, you must supply all six elements. Assuming you have the appropriate values and functions, you can create a value like this:
myHeap = Heap myEmpty myInsert myFindMin myDeleteMin myMerge myContains
It doesn't seem like Haskell's idiomatic design, however. Why not define generic data-independent functions or, if they need to be bundled together, a typeclass?
source to share