title: Returning something from another type class B in function of type class A in Haskell
body: <p>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.</p>
  
  <p>My approach is the following:
  (1) Translate Interfaces to Typeclasses
  (2) Declare custom data types and instances for actual implementations</p>
  
  <p>So I created the following type classes:</p>
  
  <pre><code>class Iterator it where
      next :: it e -&gt; (it e, e)
      hasNext :: it e -&gt; Bool
  
  class Iterable i where
      iterator :: Iterator it =&gt; i e -&gt; it e
  
  class Iterable c =&gt; Collection c where
      add :: c e -&gt; e -&gt; c e
  </code></pre>
  
  <p>Yes, I'm trying to translate the concept of Iterators (which in this case is simply a box around the actual list).</p>
  
  <p>Here is my implementation of a simple List:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>I've excluded other functions like remove, contains, addAll for simplification.</p>
  
  <p>Here is the Iterator:</p>
  
  <pre><code>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)
  </code></pre>
  
  <p>Finally, an instance for Iterable LinkedList is missing. This is what I do:</p>
  
  <pre><code>instance Iterable LinkedList where
      iterator list = It list
  </code></pre>
  
  <p>The iterator function wraps the list into a <code>LinkedListIterator</code> and returns that. Here GHC claims an error:</p>
  
  <pre><code>Could not deduce (it ~ LinkedListIterator)
  from the context (Iterator it)
    bound by the type signature for
               iterator :: Iterator it =&gt; LinkedList e -&gt; it e
  
    `it' is a rigid type variable bound by
         the type signature for
           iterator :: Iterator it =&gt; LinkedList e -&gt; it e
  
  Expected type: it e
    Actual type: LinkedListIterator e
  </code></pre>
  
  <p>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, <em>is</em> an Iterator e). What does the tilde (<code>~</code>) mean anyway? What is a rigid type variable?</p>
  
  <p><strong>EDIT:</strong> I changed the title from <code>Translating Java Types into Haskell types: type deduction fail due to rigid type variable</code> to <code>Returning something from another type class B in function of type class A in Haskell</code> 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.</p>
  
  <p><strong>SOLUTION:</strong> Thanks to the answers I now changed my code to the version below. However, I had a fun time reading the <a href="http://www.haskell.org/haskellwiki/Typeclassopedia" rel="nofollow">Typeclassopedia</a> and can only recommend it. As said, one should learn haskell idioms.</p>
  
  <pre><code>data Iterator c e = Next (Iterator c e, e) | Empty
      deriving (Show, Eq)
  
  next :: Iterator c e -&gt; (Iterator c e, e)
  next (Next (i, e)) = (i, e)
  
  hasNext :: Iterator c e -&gt; Bool
  hasNext Empty = False
  hasNext _ = True
  
  class Iterable i where
      iterator :: i e -&gt; Iterator (i e) e
  
  instance Iterable LinkedList where
      iterator Nil = Empty
      iterator (Element x xs) = Next (iterator xs, x)
  </code></pre>