Match against type in Haskell typeclass

2
votes

I'm not sure how to phrase this exactly so if someone has a good name for it please let me know.

I'm trying to write a typeclass called Matchable. The idea is a couple different types of regular expressions that I have (RegExp a, ComplexRegex a) should be able to match on input.

So I tried this:

class Matchable a where
  --   regex, input, success
  match :: a -> b -> Bool

But what I really want is to deconstruct the constructor in the typeclass with a type constructor variable or something:

class Matchable a where
  --   regex, input, success
  match :: (B a) -> [a] -> Bool

That way I can have a RegExp Char and a ComplexRegex Char both match on a String. Is there any way to do this? Thanks.

3
haskelltypeclass
It's not totally clear what you want. Can you provide a few type signatures for the different cases of match you'd like to abstract? e.g. matchRegExp :: RegExp Char -> [Char] -> Bool, matchComplexReg :: ComplexRegex ... etc. – jberryman
you likely want either associated types (newer, more verbose) or fundeps (older, less verbose) but it's hard to say without actual code – hao
@jberryman and haoformayor see Alec's answer -- pretty much exactly that – tekknolagi

3 Answers

6
votes

Keeping things simple, why not just make the class variable of Matchable have kind * -> *? (See Functor, Applicative, Monad, Foldable, Traversable for other examples of higher-kinder classes).

class Matchable b where
  --   regex, input, success
  match :: b a -> [a] -> Bool

instance Matchable ComplexRegex where
  -- match :: ComplexRegex a -> [a] -> Bool
  match = error "unimplemented"

instance Matchable RegExp where
  -- match :: RegExp a -> [a] -> Bool
  match = error "unimplemented"

Then, you can match against a String ~ [Char] with either a ComplexRegex Char or a RegExp Char.

2
votes

As an alternative to Alec's solution, you could use associated types. This allows types which don't have kind * -> *, but if it isn't necessary, I'd go with the simpler solution. E.g. imagine that in addition to RegExp a and ComplexRegex a you have StringRegex with is not parametrized, or maybe you can only implement match for ComplexRegex Char and not ComplexRegex a:

class Matchable b where
  type Target b :: *
  --   regex, input, success
  match :: b -> [Target b] -> Bool

instance Eq a => Matchable (ComplexRegex a) where
  type Target (ComplexRegex a) = a
  -- match :: ComplexRegex a -> [a] -> Bool
  match = error "unimplemented"

instance Matchable StringRegex where
  type Target StringRegex = Char
  -- match :: StringRegex -> [Char] -> Bool
  match = error "unimplemented"

-- requires FlexibleInstances
instance Matchable (ComplexRegex Char) where
  type Target (ComplexRegex Char) = Char
  -- match :: ComplexRegex Char -> [Char] -> Bool
  match = error "unimplemented"

Another difference is that your instances can ensure Eq (Target b), instead of putting it into type of match (and you can also make it a requirement: class Eq (Target b) => Matchable b where ...).

1
votes

You're probably looking for higher-kinded types. If you only interested in Char and String and behavior of function depends only on whether it's RegExp or ComplexRegex then you can define next type class:

class Matchable r where
  --   regex, input, success
  match :: r Char -> String -> Bool

Here r is type variable that has kind * -> *. In simple words, it's an incomplete type. Like Maybe. Your function can't have type Maybe -> Int because Maybe is incomplete type but Maybe Bool is complete type. Similar with regular expressions: RegExp and ComplexRegex are both incomplete types. Thanks to Haskell reach type system your functions can be parametrized over incomplete types as well. So later when you define instances, you will write them in the next way:

instance Matchable RegExp where
   ... -- implementation for RegExp goes here

instance Matchable ComplexRegex where
   ... -- implementation for CompltexRegex goes here

You can find -XKindSignatures and -XInstanceSigs language extensions helpful when specifying types of functions and types of types explicitly.