Get First Elements From List Of Tuples

Question

I have a List with this format [ (Int, [(Int, Int, Float)]) ]. Its a list of Nodes and their Edges on a graph. Each tuple of the list contains : (Node, [(startNode, endNode, Weight)]). What id like to do is create a list of all the Nodes. I've tried to this using:

nodes xs = map fst xs

But it does not work and i have no clue why. Any suggestions?

EDIT: To be more specific these are the data structures i am using

data Graph = G [(Node, [Edge])]

data Node = N Integer

type Edge = ( Node, Node, Float )

Answer 1

You need to unwrap the data from the Graph data type to operate on it. The easiest way would be to do something like

mapG :: ([(Node, [Edge])] -> a) -> Graph -> a
mapG f (G nodes) = map f nodes

Then you could just use it as

> let xs = G [(N 1, []), (N 2, [])]
> mapG fst xs
[N 1, N 2]

The type of Graph is not a list, it's a wrapper around a list. You might instead consider just using a type alias since you aren't using any features of Haskell's data types, something more like

type Edge = (Node, Node, Float)
type Node = Integer
type Graph = [(Node, [Edge])]

Then you can easily do

> let xs = [(1, []), (2, [])] :: Graph
> :type xs
xs :: Graph
> map fst xs
[1, 2]

---

So, a quick overview of types in Haskell. There are 4 main ways to declare something that can be used in a type signature: type, newtype, data, and class.

type

The easiest to understand, anything declared as a type is simply an alias. So

type Node = Integer

Is the exact same as Integer itself. It can be used anywhere Integer is used, and vice-versa. All this construct is for is to make your intentions more clear, such as the pre-defined FilePath type that is an alias for String. If you see a function

writeToFile :: String -> String -> IO ()

compared to

writeToFile :: FilePath -> String -> IO ()

You immediately know in the second one that the first argument is the file path without having to look at anything else. Types can also be used to make synonyms for more complex types, such as

type Edge = (Node, Node, Float)

Now you can write Edge everywhere you want this tuple, which is much more succinct and easy to understand. types can also be parameterized

type List a = [a]

By using type, you also get all the typeclass instances for what you're aliasing, so for example you can add two Nodes together with the usual + and get back a Node.

newtype

A slightly beefier version of type, newtypes have to follow a particular form. They have a single constructor of a single type, and are usually used as an alias where you don't want people being able to really see what's inside. For example:

newtype MyInt = MyInt Int

creates a type called MyInt that contains a single value of type Int. This is (almost always) optimized away at compile time, so once the program runs MyInt takes up the same memory as Int, but at compile time MyInt and Int can not be used interchangeably. These become very useful later. Like types, they can be parameterized, but unlike types you don't get instances for free. MyInt does not implement Num by default, so you can't add them together.

data

This is a very complex subject, so I'll gloss over a lot. A data type is something entirely new, not just an alias. It can have 1 or more constructors that take 0 or more arguments each. Bool is a data type that has 2 constructors, each with 0 arguments:

data Bool = False | True

Maybe has two constructors, but one takes an argument:

data Maybe a = Nothing | Just a

And here we see that Maybe is also parameterized. These data types also do not implement the typeclass instances of their contents, since in general this is impossible. You can also provide multiple parameters to data types such as

data Either a b = Left a | Right b

If you had a data type like

data Node = N Integer

Then Integer is not the same type as Node, and vice-versa. In order to convert an Integer into a Node, you have to use the N constructor. You can think of constructors as a special kind of function, you can even ask for their types in GHCi:

> :type Just
Just :: a -> Maybe a

class

This is the most abstract one. Typeclasses don't define a type directly, instead they provide a sort of prototype for what an instance of that typeclass would look like. For example, the Eq typeclass is essentially defined as

class Eq a where
    (==) :: a -> a -> Bool
    (/=) :: a -> a -> Bool
    a /= b = not (a == b)

Here Eq says that a type that implements this class must provide a definition for the function (==), and can optionally provide a definition for (/=), but there is a default implementation in case you don't provide it. data Node could implement this as

instance Eq Node where
    (N a) == (N b) = a == b

---

There is enough information, details, and extensions to the Haskell type system that you could fill a few books, so don't expect this to be comprehensive in any form. There are entire topics that I didn't even mention, but this should be a good primer for you.

---

As for generating edges, that's up to you. I don't know what your graph is being used for or what kind of data you expect to put in it, so I don't think I can really help you there.