Haskell: When declaring a class, how can I use a type variable that is not immediately in the constructors?

Question

I want to define a function, <-? to check whether an element is in a list/set/map.

module Test where
import qualified Data.Map as Map
import qualified Data.Set as Set

class Memberable a where
    (<-?) :: b -> a -> Bool
instance Memberable [x] where
    (<-?) = elem
instance Memberable (Map.Map k v) where
    (<-?) = Map.member
instance Memberable (Set.Set x) where
    (<-?) = Set.member

The type variable b in the class declaration should be the type of element I want to check. However, this doesn't work for Haskell.

Test.hs:8:13:
    Couldn't match type 'b' with 'x'
      'b' is a rigid type variable bound by
          the type signature for (<-?) :: b -> [x] -> Bool at Test.hs:8:5
      'x' is a rigid type variable bound by
          the instance declaration at Test.hs:7:10
    Expected type: b -> [x] -> Bool
      Actual type: b -> [b] -> Bool
    Relevant bindings include
      (<-?) :: b -> [x] -> Bool (bound at Test.hs:8:5)
    In the expression: elem
    In an equation for '<-?': (<-?) = elem

How can I use b in the class declaration, but still make the types coincider?

Random Dev · Accepted Answer · 2015-06-22 05:44:37Z

9

using `TypeFamilies`

The problem is that you somehow have to connect b with your collection (the elements in it) - there are several ways to do this but I think a rather nice one is using TypeFamilies:

{-# LANGUAGE TypeFamilies #-}

module Test where

import qualified Data.Map as Map
import qualified Data.Set as Set

class Memberable a where
  type ElemT a :: *
  (<-?) :: (ElemT a) -> a -> Bool

instance Eq x => Memberable [x] where
    type ElemT [x] = x
    (<-?) = elem

instance Ord k => Memberable (Map.Map k v) where
    type ElemT (Map.Map k v) = k
    (<-?) = Map.member

instance Ord x => Memberable (Set.Set x) where
    type ElemT (Set.Set x) = x
    (<-?) = Set.member

As you can see I added an additional type member to class that will hold the type of the elements used (so you can use them for your (<-?) in the very next line).

I also added the needed constraints for your instances - those do really come from the used functions like elem, Map.member and Set.member.

using `MultiParamTypeClasses`

here is the one @dfeuer was hinting at (or so I think):

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}

module Test where

import qualified Data.Map as Map
import qualified Data.Set as Set

class Memberable e a where
  (<-?) :: e -> a -> Bool

instance Eq x => Memberable x [x] where
    (<-?) = elem

instance Ord k => Memberable k (Map.Map k v) where
    (<-?) = Map.member

instance Ord x => Memberable x (Set.Set x) where
    (<-?) = Set.member

remark:

I think with this approach you might want to add this FunctionalDependency too, as you clearly have such a dependency between the collection a and it's elements e here ;)

{-# LANGUAGE FunctionalDependencies #-}

class Memberable e a | a -> e where
  (<-?) :: e -> a -> Bool

edited Jun 22, 2015 at 5:44

answered Jun 22, 2015 at 5:33

Random Dev

52.4k9 gold badges95 silver badges120 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

dfeuer Over a year ago

Some mention should be made of the standard higher-kinded approach and perhaps also the MPTC one.

Random Dev Over a year ago

sure - never thought that this should be the default or the only answer ;) - it's just the one that came to mind first (and is reasonable nice IMO) - if you want I can add something - or you can add your own answer ;)

dfeuer Over a year ago

I think the fact that the higher kinded once is standard Haskell makes it notable, although the other approaches are also solid.

dfeuer Over a year ago

You almost surely want fundeps for the mptc. Bedtime for me though!

Random Dev Over a year ago

@dfeuer - you posted this just as I was editing the answer ;) (it just took me some time to check the syntax and lookup the link)

|

Collectives™ on Stack Overflow

Haskell: When declaring a class, how can I use a type variable that is not immediately in the constructors?

1 Answer 1

using `TypeFamilies`

using `MultiParamTypeClasses`

remark:

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

using TypeFamilies

using MultiParamTypeClasses

remark:

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related

using `TypeFamilies`

using `MultiParamTypeClasses`