How is it possible to write a class with two template parameters, where one is a list/array of the other?

Question

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.

Answer 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 ...