CODEWITHSUNDEEP
haskellconstraintstypeclassfunctional-dependencies
Belserich
Belserich

Reputation: 23

Haskell not getting my functional dependency

I am trying to create a queue type class that implements basic queue behavior. My code is as follows:

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}

data QueueA a = QueueA { front :: [a], rear :: [a] }

class Queue a b | a -> b where

  empty         :: a
  null          :: a -> Bool
  head          :: a -> Maybe b
  tail          :: a -> Maybe a
  toList        :: a -> [b]
  (|>)          :: a -> b -> a

instance Queue (QueueA a) where      

  empty = QueueA [] []

  null (QueueA [] []) = True
  null _ = False

  head (QueueA [] []) = Nothing
  head (QueueA (x:xs) _) = Just x

  tail (QueueA [] []) = Nothing
  tail (QueueA (x:xs) (y:ys)) = Just $ QueueA (xs ++ [y]) ys

  toList (QueueA x y) = x ++ y

  (|>) (QueueA x y) e = if (length x > length y) then QueueA (init $ e : x) ((last x) : y) else QueueA (e : x) y

Unfortunately, when I try to compile the code ghc tells me the following:

queue.hs:15:10: error:
    • Expecting one more argument to ‘Queue (QueueA a)’
      Expected a constraint,
        but ‘Queue (QueueA a)’ has kind ‘* -> Constraint’
    • In the instance declaration for ‘Queue (QueueA a)’
   |
15 | instance Queue (QueueA a) where 
   |          ^^^^^^^^^^^^^^^^

I don't really get the message though. All I know is that the pattern for the Queue in my instance declaration must be right, because it is exactly as I specified it in my data type above. I've tried several variations of my instance declaration, to no avail. Am I simply overlooking something? How do I make this compilable?

Upvotes: 2

Views: 154

Answers (2)

chepner
chepner

Reputation: 532103

You don't need multiple parameters for the class. Instead, the class should take a higher-order type as its argument, not a concrete type.

class Queue t where
    empty :: t a
    null :: t a -> Bool
    head :: t a -> Maybe a
    tail :: t a -> Maybe (t a)
    toList :: t a -> [a]
    (|>) :: t a -> a -> t a

QueueA itself has a Queue instance, not QueueA a.

instance Queue QueueA where
  -- same as above

Upvotes: 2

Joseph Sible-Reinstate Monica
Joseph Sible-Reinstate Monica

Reputation: 48662

Instances need the same number of parameters as the corresponding class. However, you created a class with 2 parameters and a corresponding instance with just 1. To make it compile, you can do instance Queue (QueueA a) a where instead of instance Queue (QueueA a) where. (You'll also need the FlexibleInstances extension.)

Upvotes: 4

Related Questions