Implementation of list concat and subclass condition

[Peter M|ller Neergaard]

I am doing a graduate student project with the aim of veryfying the result
of Bird, Jones and de Moor that lazy languages has the same time complexity
as impure Lisp on a problem proposed by Pippenger (The problem is solved in
a strictly higher complexity by a pure Lisp than in an impure Lisp program).

To this end I am using Haskell for some practical verifications of the
result.  I have encountered two problems:

1) The implementation of list concatenation ++.  In the Haskell report it is
   stated that ++ in general is an operator on monads.  In the case of
   lists, ++ works as list concatenation.  However, I cannot find any place
   describing whether the implementation of ++ is supposed to be better than
   the straight-forward: 
     [] ++ ys = ys 
     (x:xs) ++ ys = x : (xs ++ ys)

2) My intention is to count the number of ``primitive'' operations by
   annotating each value with a state and define some functions equivalent
   to the basic list operations doing the counting.  For this purpose I
   would like to introduce a state class
     class State s where
       zeroState        :: s
       addStates        :: s -> s -> s
   and a class where a value is annotated with a state, ie where some
   instance of state is a subclass of every instance of a annotated
   value. I can---partly---accomplish this by the declaration
     data State s => Annotation s a = Ann (a, s)
   I want to be able to add a state to annotated value, eg
     addStat    :: State s => s -> v -> v
     addStat s' (Ann (a,s'')) = Ann(a, addStates s' s'') 
   Ideally, I would like to declare it as a class, eg
     class AnnotatedValue v where
       addStat  :: State s => s -> v -> v
   but this---naive---definition eventually conflicts because the state s is
   universal quantified and thus can be any state and not the specific
   instance of State being a subclass of AnnotatedValue.  Is there a way to
   work around this to express that for each instance of AnnotatedValue,
   there associated a specific instance State?

Thanks in advance

Peter Mxller Neergaard
   

-- 
                                  __   _
Peter Mxller Neergaard           /  \-' )      ,,,  WWW: http://www.diku.dk/
Dept. of Computer Science       | |  ()|||||||[:::)            students/turtle/
University of Copenhagen         \__,-._)      '''  
E-mail: turtle @ diku.dk        
        ``Will all these memories be lost in time, like tears in rain?''