Open, type safe and easy to extend component structure in Haskell?

Question

I im trying to implement a small and simple open type component structure in Haskell.
The goal is to easily allow function and type extension by creating new components in other modules while preserving type safety at compile time.

I managed to implement a recursive search function by component type (find, in CompFinder), and it works well in the simple tests i tried. However i need to write trivial instances for CompFinder for non-composite components and multiple instances with the only difference being the component type for the CompFinder CompMix instance.

I am aware of Derive for automatic code generation for instance deriving but I would like a simpler solution if there is one, the compiler doing the code generation in the worst case, if possible.

So the questions are: How can I modify this system to simplify the writing of new Components?
or: How can I tell GHC to automatically generate CompFinder instances since only the type change in the different definitions?

Perhaps by doing something like this:

instance (Component a, CompFinder a T, Component b, CompFinder b T) => CompFinder (CompMix a b) T where
    find (CompMix x y ) = (find x :: [T]) ++ (find y :: [T])

where T would by a type parameter

Or maybe by writing CompFinder so it automatically works for all Components.

This is the full code:

--ghc 7.10
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}

-- Defined in the library module
class Component a

class ComponentMix a where -- Allow recursive component aggregation
    add :: b -> c -> a b c

class (Component a, Component b) => CompFinder a b where -- class that need a new instance for each new component type
    find :: a -> [b]
    find _ = []

-- Defined in the user module
data CompMix a b = CompMix a b deriving (Show, Eq)

instance ComponentMix CompMix where
    add x y = ( CompMix x y )

instance (Component a, Component b) => Component (CompMix a b)

-- Two simple component types that can be defined in another module
data Position = Pos Int Int deriving (Show, Eq, Ord)
data Name = Name String deriving (Show, Eq)          

instance Component Position
instance CompFinder Position Position where -- Trivial instance
    find x = [x]
instance CompFinder Position Name           -- Trivial instance

instance Component Name
instance CompFinder Name Name where -- Trivial instance
    find x = [x]
instance CompFinder Name Position   -- Trivial instance

instance (Component a, CompFinder a Name, Component b, CompFinder b Name) => CompFinder (CompMix a b) Name where
    find (CompMix x y ) = (find x :: [Name]) ++ (find y :: [Name])

instance (Component a, CompFinder a Position, Component b, CompFinder b Position) => CompFinder (CompMix a b) Position where
    find (CompMix x y ) = (find x :: [Position]) ++ (find y :: [Position])

main = print $ (find (CompMix (Name "Henri") (CompMix (Pos 1 2) (Name "Julie") ) ) :: [Position] ) -- Correctly outputs [Pos 1 2]

Answer 1

After looking at some Generic Haskell, I finally found an easier way than automatic derivation to avoid writing each instance for Finder (formerly CompFinder). By doing this way, we only need to define instances of Finder for the structural types defined by the user.

Start with some pragmas

{-# LANGUAGE MultiParamTypeClasses #-} -- allows functions at the type level
{-# LANGUAGE FlexibleContexts #-} -- allows using data types in typeclass declarations

Then define a simple Component wrapper. This way we will write the instance for the Finder only once for all the simple components.

data Component a = Comp a

Then define the Finder class, we will use MultiParamTypeClasses without Functional dependencies because we want to specify the return type to get the desired components:

class Finder s c where -- s is the structure and c the component
    find :: s -> [c]
    find _ = [] -- provides empty list on search fail

We can implement this for our wrapper, first with actual component and searched component matching.

instance {-# OVERLAPABLE #-} Finder (Component a) (Component a) where
    find (Comp o) = [Comp o]

We take advantage of the OVERLAPPABLE pragma to provide an empty list if components differs:

instance Finder (Component a) (Component b) where
    find (Comp o) = []

We can structure our components with a simple Mix (2-Tuple) for instance:

data Mix a b = Mix a b deriving (Show,Eq,Ord)
instance (Finder a (Component c), Finder b (Component c) ) => Finder (Mix a b) (Component c) where
    find (Mix x y) = find x ++ (find y)

Now let's define some components:

data Velocity = Vel Int Int deriving (Show,Eq,Ord)
data Name = Name String deriving (Show,Eq,Ord)

And finally:

myStruct = Mix (Comp $ Name "Julien") (Comp $ Vel 5 2)

-- we can use the return type to ask for a list of components of that type
Prelude> find myStruct :: [Component Name]
  [Comp (Name "Julien")]

Prelude> find myStruct :: [Component Velocity]
  [Comp (Vel 5 2)]

Prelude> find (Comp $ Name "Marie") :: [Component Velocity]
  []

This works with nested Mix too! The only downside is the use of the Component wrapper but it's fine.