4

I have a problem with a homework (the topic is : "functional data structures"). Please understand that I don't want anyone to solve my homework. I just have a problem with 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" and so on are functions which can applied to "Heap"-type data. Now I just want to understand how that "Heap"thing looks like. So I was typing things like :

  a = Heap 42 42

But I get errors I can't really work with.

Maybe it is a dumb question and I'm just stuck at this point for no reason, but it is killing me at the moment. Thankful to any help

Improve this question
2
  • 3
    Heap e t does not look as a type to represent a heap, but to represent a heap implementation. That is, it is a bunch of functions to operate on heaps, or rather, on some generic container. Commented Jun 25, 2017 at 12:34
  • 1
    @chi oh well ok I got it now. That wasn't that hard :D Commented Jun 25, 2017 at 14:45

2 Answers 2

Reset to default
4

If you truly wish to understand that type, you need to understand a few requisites first.

types and values (and functions)

Firstly, you need to understand what types and values are. I'm going to assume you understand this. You understand, for example, the separation between "hello" as a value and its type, String and you understand clearly what it means when I say a = "hello" :: String and:

a :: String
a = "hello"

If you don't understand that, then you need to research values and types in Haskell. There are a myriad of books that can help here, such as this one, which I helped to author: http://happylearnhaskelltutorial.com

I'm also going to assume you understand what functions and currying are, and how to use both of them.

polymorphic types

Secondly, as your example contains type variables, you'll need to understand what they are. That is, you need to understand what polymoprhic types are. So, for example, Maybe a, or Either a b, and you'll need to understand how Maybe String is different to Maybe Int and what Num a => [a] and even things like what Num a => [Maybe a] is.

Again, there are many free or paid books that can help, the example above covers this, too.

algebraic data types

Next up is algebraic data types. This is a pretty amazingly cool feature that Haskell has. Haskell-like languages such as Elm and Idris have it as well as others like Rust, too. It lets you define your own data types. These aren't just things like Structs in other languages, and yeah, they can even contain functions.

Maybe is actually an example of an algebraic data types. If you understand these, you'll know that:

data Direction = North | South | East | West

defines a data type called Direction whose values can only be one of North, South, East or West, and you'll know that you can also use the polymorhpic type variables above to parameterise your types like so:

data Tree a = EmptyNode | Node (Tree a) (Tree a)

which uses both optionality (as in the sum type of Direction above) as well as parameterization.

In addition to this, you can also have multiple types in each value. These are called product types, and Haskell's algebraic datatypes can be expressed as a combination of Sum types that can contain Product types. 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 are a different set of fields given to each value. To create a StringNode, for example, you'd need to pass the values of it constructor like this: StringNode (10.0, 5.3) "A String".

Again, the freely available books will go into much more detail about these things, but we're moving in the direction of getting more than a basic understanding of Haskell now.

Finally, in order to fully understand your example, you'll need to know about...

record types

Record types are the same as product types above, except that the fields are labelled rather than being anonymous. So, you could define the shape node data type like this, instead:

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 can't repeat the same name inside data values.

All that you need in addition to this to understand the above example is to realise your example contains all of these things together, along with the fact that you have functions as your record field values in the data type you have.

It's a good idea to thoroughly flesh out your understanding and not skip any steps, then you'll be able to follow these kinds of things much more easily in the future. :) I wish you luck!

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Wow that answer is great ! Thank you for taking time for that :) It helps a lot
I'm really glad. It's the kind of answer I wish I had when I was beginning. People who help often skip things and miss stuff out, or do handy-wavey explanations. This is understandable, but it doesn't help much. Each of the four topics I outlined above are whole topics on their own that deserve being learnt thoroughly, but a beginner has no way of knowing what they're missing unless someone tells them. I firmy believe beginners need to read more than most resources allow. Having said that, there are some great books around nowdays.
"This is a pretty amazingly cool feature of Haskell and some other pure functional languages like Elm, Idris and others." Minor note, but this isn't at all limited to pure functional languages, and given Rust I'd say it isn't just functional languages at all.
@AlexeyRomanov Sure thing. I wasn't saying which languages didn't have the feature, I was saying some of the languages that did have the feature. I wasn't implying the feature doesn't exist elsewhere. Perhaps I'll adjust it so that's clearer.
1

Heap is a record with six elements. In order to create a value of that type, you must supply all six elements. Assuming that you have appropriate values and functions, you can create a value like this:

myHeap = Heap myEmpty myInsert myFindMin myDeleteMin myMerge myContains

The doesn't seem like idiomatic Haskell design, however. Why not define generic functions independent of the data, or, if they must be bundled together, a typeclass?

Improve this answer

1 Comment

True. +1. That's how most (well-written) Haskell libraries look like; (e.g. QuickCheck, Hedgehog, and others) Just types and functions working on these types, bundled together in modules, if possible without using type classes (one reason for this is because of the orphan instances).

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.