forall quantifier

[Andreas Rossberg]

Ketil Z. Malde wrote:
> 
> I have a function declared as:
> 
>   anova2 :: (Fractional c, Ord b)
> 	    => [a->b] -> (a->c) -> [a] -> [Anova1 c]
> 
> where the first parameter is a list of classifiers.  I could simplify
> it, I guess, to something like
> 
>   classify :: Eq b => [a->b] -> [a] -> [[[a]]]
                                            ^^^
Isn't this one list too many?

>   classify cs xs = ...
> 
> where for each classifying function in cs, I would get the xs
> partitioned accordingly.  E.g.
> 
>   classify [fst,snd] [(1,0), (1,2), (2,0)] 
> 
> would yield
> 
>   [ [(1,0), (1,2)], [(2,0)] -- classified by `fst`
>   , [(1,0), (2,0)], [(1,2)]] -- classified by `snd`
> 
> Now, obviously, the problem is that fst and snd, being passed in a
> list, needs to be of the same type; this complicates classifying a
> list of type [(Int,Bool)], for instance?.

What you'd need would be an existential type of the form

    classify :: [exists b. Eq b => a->b] -> [a] -> [[a]]

Such a type is not available directly in Haskell, but only through an 
auxilary data type:

   data Classifier a = forall b. Eq b => Classifier (a -> b)

Using that you should be able to implement

    classify :: [Classifier a] -> [a] -> [[a]]

Cheers,

   - Andreas

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

"Computer games don't affect kids; I mean if Pac Man affected us
  as kids, we would all be running around in darkened rooms, munching
  magic pills, and listening to repetitive electronic music."
  - Kristian Wilson, Nintendo Inc.