Hi Oleg, I like the polymorphic list indexed by Ints... there do seem to be a couple of differences between this and the list indexed by natural numbers. The list indexed by integers cannot determine the type of the return value through induction on the class... in other words it cannot determine the return type of the lookup function until runtime: you can see this in the class instance for 'tke'

instance (TH a (a,b), TH W b) => TH W (a,b) where tke (W 0) th@(h,t) f = f h th tke (W n) (h,t) f = tke (W$ n-1) t f

On the other hand indexing by natural numbers allows the compiler to know the return type (and avoid the use of existentials) because it is determined at compile time... you can see this because the recursion termination is done by the type signatures in the instance not the pattern guards of the function. instance Relation r => RIndex Zero (a `RCons` r) a where rIndex Zero (x `RCons` _) = x instance RIndex Idx r b => RIndex Idx (a `RCons` r) b where rIndex (Suc n) (_ `RCons` xs) = rIndex n xs It looks like most of this stuff has been done before... but I don't think there is any of it in the ghc libraries. I needed this code for a real application, and could not find anything suitable so I rolled my own. What do people think - is there a case for getting this stuff in the libs, should we write a functional pearl? does anyone have any comments about the code I posted, or how it could be improved? To finish, here are some new definitions for map,zip and unzip class Relation r => RMap t r where rMap :: t -> r -> r instance RMap t RNil where rMap _ RNil = RNil instance (RMapFn t a,RMap t r) => RMap t (a `RCons` r) where rMap t (x `RCons` xs) = rMapFn t x `RCons` rMap t xs class RMapFn t a where rMapFn :: t -> a -> a data RMapId = RMapId instance RMapFn RMapId a where rMapFn RMapId a = a class (Relation r1,Relation r2,Relation r3) => RZip r1 r2 r3 | r1 r2 -> r3 where rZip :: r1 -> r2 -> r3 instance RZip RNil RNil RNil where rZip _ _ = RNil instance RZip r1 r2 r3 => RZip (a `RCons` r1) (b `RCons` r2) ((a,b) `RCons` r3) where rZip (x `RCons` xs) (y `RCons` ys) = (x,y) `RCons` rZip xs ys class (Relation r1,Relation r2,Relation r3) => RUnZip r1 r2 r3 | r1 -> r2 r3 where rUnZip :: r1 -> (r2,r3) instance RUnZip RNil RNil RNil where rUnZip _ = (RNil,RNil) instance RUnZip r1 r2 r3 => RUnZip ((a,b) `RCons` r1) (a `RCons` r2) (b `RCons` r3) where rUnZip ((x,y) `RCons` xys) = (x `RCons` xs,y `RCons` ys) where (xs,ys) = rUnZip xys and finally a lookup that indexes by the left type of a pair and returns the right type & value stored in a polymorphic list: class Relation r => RLookup r l v | r l -> v where rLookup :: r -> l -> v instance Relation r => RLookup ((l,v) `RCons` r) l v where rLookup ((_,v) `RCons` _) _ = v instance RLookup r l v => RLookup ((l',v') `RCons` r) l v where rLookup (_ `RCons` r) l = rLookup r l Regards, Keean Schupke.