Returning something from another type class B in function of type class A in Haskell

Question

I'm doing a fun project in which I'm trying to redo some basic data types and concepts from Java. Currently I'm tackling Iterators.

My approach is the following: (1) Translate Interfaces to Typeclasses (2) Declare custom data types and instances for actual implementations

So I created the following type classes:

class Iterator it where
    next :: it e -> (it e, e)
    hasNext :: it e -> Bool

class Iterable i where
    iterator :: Iterator it => i e -> it e

class Iterable c => Collection c where
    add :: c e -> e -> c e

Yes, I'm trying to translate the concept of Iterators (which in this case is simply a box around the actual list).

Here is my implementation of a simple List:

data LinkedList e = Element e (LinkedList e) | Nil
    deriving (Show, Eq)

instance Collection LinkedList where
    add Nil e = Element e Nil
    add (Element x xs) e = Element x $ add xs e

I've excluded other functions like remove, contains, addAll for simplification.

Here is the Iterator:

data LinkedListIterator e = It (LinkedList e)

instance Iterator LinkedListIterator where
    hasNext (It Nil) = False
    hasNext (It _) = True
    next (It (Element x xs)) = (It xs, x)

Finally, an instance for Iterable LinkedList is missing. This is what I do:

instance Iterable LinkedList where
    iterator list = It list

The iterator function wraps the list into a LinkedListIterator and returns that. Here GHC claims an error:

Could not deduce (it ~ LinkedListIterator)
from the context (Iterator it)
  bound by the type signature for
             iterator :: Iterator it => LinkedList e -> it e

  `it' is a rigid type variable bound by
       the type signature for
         iterator :: Iterator it => LinkedList e -> it e

Expected type: it e
  Actual type: LinkedListIterator e

which I do not quite understand. There is an instance of Iterator for LinkedListIterator, so why is the expected Type "it e" not compatible with the actual type "LinkedListIterator e" (which, as far as I understand, is an Iterator e). What does the tilde (~) mean anyway? What is a rigid type variable?

EDIT: I changed the title from Translating Java Types into Haskell types: type deduction fail due to rigid type variable to Returning something from another type class B in function of type class A in Haskell since I believe that my actual problem is related to the return-something-of-type-class-B-from-type-class-A-issue in the iterator-function.

SOLUTION: Thanks to the answers I now changed my code to the version below. However, I had a fun time reading the Typeclassopedia and can only recommend it. As said, one should learn haskell idioms.

data Iterator c e = Next (Iterator c e, e) | Empty
    deriving (Show, Eq)

next :: Iterator c e -> (Iterator c e, e)
next (Next (i, e)) = (i, e)

hasNext :: Iterator c e -> Bool
hasNext Empty = False
hasNext _ = True

class Iterable i where
    iterator :: i e -> Iterator (i e) e

instance Iterable LinkedList where
    iterator Nil = Empty
    iterator (Element x xs) = Next (iterator xs, x)

Answer 1

iterator :: Iterator it => i e -> it e

This means the caller can choose it to be whatever they want, subject to it implementing Iterator. Another way of looking at it is that it's a promise by iterator to work for all types it that implement Iterator.

Your implementation provides a LinkedListIterator, no matter what the caller asks for.

The compiler cannot prove that they are the same thing (because the caller could demand a different Iterator implementation), so issues an error.

This is different from Java, where the caller chooses the classes of the inputs, and the callee chooses the class of the output. In Haskell, the caller chooses the types of the input and the output.

~ means type equality.

---

Some broader points. (And I appreciate that you are trying to translate Java idioms into Haskell, but imo you need to learn Haskell idioms.)

1. Sometimes you don't want to return a value that implements a typeclass, you just want to return a value.

   If instead of Iterator being a typeclass, it was a datatype...

   data Iterator e = Iterator {next    :: (Iterator e, e),
                               hasNext :: Bool}
   

   ...then you could just return a value of type Iterator and not have to worry about different typeclass implementations.

   Laziness means that successive values from the iterator won't be generated (and exceptions won't be thrown) until they're asked for. As long as you don't old on to an old iterator value, these values can be garbage collected as you iterate along, so we still use constant space.

2. A better definition of Iterator would be

   data Iterator e = Iterator {next :: Maybe (Iterator e, e)}
   

   This is better because it makes it harder for you to ask for the next value from the iterator without first checking to see that there is a next value.

3. My second definition of Iterator looks a bit like your definition of LinkedList, and also like the definition of standard Haskell lists (which are themselves linked lists). And indeed it is idiomatic to use Haskell lists as an intermediate data structure where necessary for iteration.

4. Read about the Foldable and Traversable typeclasses in the Typeclassopedia. In fact, read the Typeclassopedia, it's a good introduction to some of the more scary-sounding typeclasses.