Using the most general typeclass function types

Question

I'm trying to write a simple genetic algorithm in Haskell. I figured the first step should be to make a typeclass for individuals that are 'genetic', like so:

class Genetic a where
    fitness :: (Ord b) => a -> b

This seems reasonable to me - I don't necessarily want to restrict fitness functions to a type like Float or Double, and conceptually all a fitness function should do is provide an ordering of the individuals.

However, when I implement this typeclass for a String wrapper:

data DNA = DNA String
instance Genetic DNA where
    fitness (DNA s) = length s

I see the following error in GHC:

Could not deduce (b ~ Int)
from the context (Ord b)
  bound by the type signature for fitness :: Ord b => DNA -> b

Is this not how I should define typeclass functions? Do I have to restrict the function to a specific concrete type, or provide another type variable to the typeclass constructor?

This is a common problem. Your signature means that the caller gets to choose the orderable type, so fitness must be able to fabricate a value of any orderable type and return it. Note, Void (the type with no values) is orderable, so this is impossible. You probably want to parameterize Genetic on the order space: class (Ord b) => Genetic b a where fitness :: a -> b — luqui
@luqui Thanks, I think I get it. Trying that out, it seems vanilla Haskell doesn't like multi-type-parameter typeclasses. Who'd have thought. — Daniel Buckmaster
@DanielBuckmaster yes but the MultiParamTypeclasses extension is pretty common to use — Daniel Gratzer
@jozefg Fair enough, I was just surprised that it was an extension. — Daniel Buckmaster
@DanielBuckmaster Haskell 98 (or 2010) is a pretty darn conservative language, most of the crazy stuff you see happening today such as lens or cloud haskell are pretty heavily dependent on language extensions that tie them to GHC. — Daniel Gratzer

leftaroundabout leftaroundabout · Accepted Answer · 2013-06-13T23:59:13

Luqui explained what the problem is: fitness would need to be able to provide any Ord instance the caller might request, when what you really want is some specific one that suits the type best.

This is IMO a very nice application for associated type synonyms:

{-# LANGUAGE TypeFamilies, FlexibleInstances, FlexibleContexts #-}

class (Ord (Fitness a)) => Genetic a where
  type Fitness a :: *
  fitness :: a -> Fitness a

data DNA = DNA String
instance Genetic DNA where
  type Fitness DNA = Int
  fitness (DNA s) = length s

Using the most general typeclass function types

1 Answers