Type troubles with custom typeclass

Question

I'm having some trouble with types while learning Haskell. I have a typeclass called Stack which obviously should behave like a stack. I have a type Elem which is simply either an Int or a Bool.

Now I want my function to take a Stack of Elem and do some operations with it. The result is not actually important, however I am failing to even acquire the first element of the stack and I have failed to figure out what is wrong for hours now.

import Control.Monad

data Elem = Number Int | Truth Bool deriving Eq

instance Show Elem where
  show (Number i) = show i
  show (Truth b) = show b

class Stack stack where
  push :: a -> stack a -> stack a
  top :: MonadPlus m => stack a -> m (a,stack a)
  empty :: stack a
  isEmpty :: stack a -> Bool

instance Stack [] where
  push a stack = a:stack
  top stack = if isEmpty stack then mzero else return (head stack, tail stack)
  empty = []
  isEmpty stack = if null stack then True else False

step :: Stack stack => String -> stack Elem -> Maybe (stack Elem)
step ex st = let e1 = top st :: Maybe (Elem, stack Elem)
                 --a1 = fmap fst e1
                 --e2 = top (fmap snd e1)
                 --a2 = fmap fst e2
             in Nothing

The error I am getting is

Playground.hs:22:27:
    Could not deduce (stack ~ stack2)
    from the context (Stack stack)
      bound by the type signature for
                 step :: Stack stack => String -> stack Elem -> Maybe (stack Ele
m)
      at Playground.hs:21:9-65
      `stack' is a rigid type variable bound by
              the type signature for
                step :: Stack stack => String -> stack Elem -> Maybe (stack Elem
)
              at Playground.hs:21:9
      `stack2' is a rigid type variable bound by
               an expression type signature: Maybe (Elem, stack2 Elem)
               at Playground.hs:22:23
    Expected type: stack2 Elem
      Actual type: stack Elem
    Relevant bindings include
      st :: stack Elem
        (bound at Playground.hs:22:9)
      step :: String -> stack Elem -> Maybe (stack Elem)
        (bound at Playground.hs:22:1)
    In the first argument of `top', namely `st'
    In the expression: top st :: Maybe (Elem, stack Elem)

I really fail to see why Haskell refuses this (and even refuses simply calling top st in my function without me trying to specify a type).

I hope someone can shed some light on this!

The compiler doesn't know that the stack in the type sig of step is the same stack in Maybe (Elem, stack Elem). You're looking for ScopedTypeVariables, but it means you'll have to change the sig to step :: forall stack. Stack stack => String -> stack Elem -> Maybe (stack Elem). — bheklilr
@bheklilr I do not have access to the forall syntax. It must be possible to somehow get the first element of the stack in my function?! — Marco
Did you put {-# LANGUAGE ScopedTypeVariables #-} at the top of your file? — bheklilr

crockeea crockeea · Accepted Answer · 2015-01-16T22:32:30

As two commenters suggested, you need -XScopedTypeVariables.

The following code compiles for me:

{-# LANGUAGE ScopedTypeVariables #-}

module Foo where

import Control.Monad

data Elem = Number Int | Truth Bool deriving Eq

instance Show Elem where
  show (Number i) = show i
  show (Truth b) = show b

class Stack stack where
  push :: a -> stack a -> stack a
  top :: MonadPlus m => stack a -> m (a,stack a)
  empty :: stack a
  isEmpty :: stack a -> Bool

instance Stack [] where
  push a stack = a:stack
  top stack = if isEmpty stack then mzero else return (head stack, tail stack)
  empty = []
  isEmpty stack = if null stack then True else False

step :: forall stack . Stack stack => String -> stack Elem -> Maybe (stack Elem)
step ex st = let e1 = top st :: Maybe (Elem, stack Elem)
                 --a1 = fmap fst e1
                 --e2 = top (fmap snd e1)
                 --a2 = fmap fst e2
             in Nothing

I'm not sure what you mean about "not having access to the forall syntax", but if you really want to avoid it, you can also write step like this:

step :: Stack stack => String -> stack Elem -> Maybe (stack Elem)
step ex (st :: stack Elem) = let e1 = top st :: Maybe (Elem, stack Elem)
                 --a1 = fmap fst e1
                 --e2 = top (fmap snd e1)
                 --a2 = fmap fst e2
             in Nothing

You'll still need ScopedTypeVariables though.

Type troubles with custom typeclass

1 Answers