1

I would like to solve this problem in Clean (a language very similar to Haskell):

There is a class Node t, with two instances: instance Node EdgeList and instance Node Adjacency. I would like to create a Graph, which is an array or list of Nodes.

The definition of the Graph is:

class Graph t1 t2 | Node t2 where
    resetGraph  :: (t1 t2) -> (t1 t2)
    graphSize   :: (t1 t2) -> Int
    ...

I would like to write the instances. One with array, and one with list. First, I tried with list, but I get an error: t2 not defined

instance Graph [t1] t2 | t2 t1 where
    (resetGraph) :: [t1] -> [t1]
    (resetGraph) x = []
    ...

It will be called for example like this: resetGraph listAdj where listAdj is a list of Adjacency Nodes

If I just write: instance Graph [tt] tt then I get this error: Error: this type variable occurs more than once in an instance type.

Iter Ator
  • 8,226
  • 20
  • 73
  • 164

1 Answers1

1

The first thing to understand here is that when you write

class Graph l t | Node t where
    resetGraph :: (l t) -> l t

you give l kind *->*. Kinds are an abstraction from types. Roughly, kind * means you have a 'complete' type. For example, Int, [Char], a -> String are all of kind *. When a type still 'needs an argument', it has kind *->*. For example, if you have :: Maybe a = Just a | Nothing, then Maybe Int is of kind *, but simply Maybe is of kind *->* because it still needs one argument. So, when writing resetGraph :: (l t) -> l t, the compiler recognises that t is an argument to l, so the only way to give resetGraph kind * (which is necessary for a function), is to give l kind *->* (and t kind *).

The second thing you need to know is that types as [Char], (Int,Int) and a -> Real kan all be written prefix as well: [] Char, (,) Int Int, (->) a Real. You can compare [] to Maybe: it still needs one argument (here Char) to be a complete type. Hence, the type [] has kind *->*. Similarly, (,) has kind *->*->*, because it still needs two types to be complete, as does (->). (Note: this is documented in section 4.5 of the language report).

Combining these two, you should write:

instance Graph [] Adjacency where
    ...

Then, the type of resetGraph is resolved to ([] Adjacency) -> [] Adjacency which is the same as [Adjacency] -> [Adjacency].

For arrays, the prefix notation is {} Adjacency for {Adjacency}.

By the way: something similar to this is done in StdEnv with the class length:

// StdOverloaded.dcl
class length m :: !(m a) -> Int

// StdList.icl
instance length [] where ...
  • Thank you, I understand it better now. For some reason I get an error at `instance Graph [] Node where ...`. The error is: `Node undefined`. Node is defined with two instances. And I get no error at `class Graph t1 t2 | Node t2 where` – Iter Ator Nov 19 '16 at 10:10
  • @IterAtor You're welcome. Sorry about that, I wrote `Node` where I should have written `Adjacency` or `EdgeList`. (The error tells you that `Node` is not a type.) It is fixed now. –  Nov 19 '16 at 10:12
  • But I think I should not use `Adjacency` or `EdgeList` directly, because every function which I will need in `Graph` is defined in `Node` (the functions are defined in both instances) – Iter Ator Nov 19 '16 at 10:14
  • 1
    @IterAtor in that case, you can use `class Graph l where resetGraph :: (l t) -> l t | Node t`, i.e. move the `Node` dependency to the class member (since it doesn't restrict the class variable). –  Nov 19 '16 at 10:16
  • @IterAtor alternatively, define `class Graph l where resetGraph :: l -> l` and instantiate with `instance Graph [a] | Node a`, depending on whether you want to enforce the `Node` context in the `Graph` class or just in that one instance. –  Nov 20 '16 at 16:53