title: Haskell - container of container and instance declration
body: <p>Short version from a Haskell newbie: suppose I have a class Container where the Container has <code>* -&gt; *</code> kind. I want to put that into another container and still make the second container an instance of the original class like in:</p>
  
  <pre><code>data Container2 a container = Container2 (container a)
  
  instance Container (Conrainer2 a) where ...
  </code></pre>
  
  <p>But it seems this is not possible as GHC always generates errors like:</p>
  
  <pre><code>Kind mis-match
  
      The first argument of `Container' should have kind `* -&gt; *',
      but `Container2 a' has kind `(* -&gt; *) -&gt; *'
  </code></pre>
  
  <p>Is it possible to workaround that?</p>
  
  <p>Long version: I am toying with the following code modeling an iterator interface in Java:</p>
  
  <pre><code>module Main where
  
  data NextResult a iter = Stop | More a (iter a)
  
  class Iter iter where
    next :: iter a -&gt; NextResult a iter
  
  -- Convert iterator to a list
  toList :: (Iter c) =&gt; c a -&gt; [a]
  toList iter = case next iter of
    Stop -&gt; []
    More value iter2 -&gt; value : toList iter2 
  
  -- List itself is iterator
  instance Iter [] where
    next [] = Stop
    next (x:xs) = More x xs
  
  main = let iter = [1,2,3,4,5] in print $ toList iter
  </code></pre>
  
  <p>With GHC 7.4.1 this compiles and prints the expected <code>1 2 3 4 5</code>. Now I want to defined a transforming iterator that constructs a new iterator from a function and an iterator. For that I added the following lines:</p>
  
  <pre><code>data TransformedIter from to iter = TransformedIter (from-&gt;to) (iter from)
  
  instance Iter (TransformedIter from to) where
    next (TransformedIter f iter) = case next iter of
      Stop -&gt; Stop
      More value iter2 -&gt; More (f value) (TransformedIter f iter2)
  </code></pre>
  
  <p>But that generated the error:</p>
  
  <pre><code>Main.hs:21:16:
      Kind mis-match
      The first argument of `Iter' should have kind `* -&gt; *',
      but `TransformedIter from to' has kind `(* -&gt; *) -&gt; *'
      In the instance declaration for `Iter (TransformedIter from to)'
  </code></pre>
  
  <p>I tried to workaround that, but the result was always a type error of one or another kind. So how to model such transformation in Haskell?</p>
  
  <h1>Update</h1>
  
  <p>I misunderstood how instance declaration works. Based on the suggestion below I flipped the order of TransformedIter types and ended up with:</p>
  
  <pre><code>module Main where
  
  data NextResult a iter = Stop | More a (iter a)
  
  class Iter iter where
    next :: iter a -&gt; NextResult a iter
  
  toList :: (Iter c) =&gt; c a -&gt; [a]
  toList iter = case next iter of
    Stop -&gt; []
    More value iter2 -&gt; value : toList iter2 
  
  instance Iter [] where
    next [] = Stop
    next (x:xs) = More x xs
  
  main = let iter = [1,2,3,4,5] in print $ toList iter
  
  data TransformedIter iter from to = TransformedIter (from-&gt;to) (iter from)
  
  instance Iter (TransformedIter iter from) where
    next (TransformedIter f iter) = case next iter of
      Stop -&gt; Stop
      More value iter2 -&gt; More (f value) (TransformedIter f iter2)
  </code></pre>
  
  <p>However that produced another error:</p>
  
  <pre><code>Main.hs:22:40:
      No instance for (Iter iter)
        arising from a use of `next'
      In the expression: next iter
      In the expression:
        case next iter of {
          Stop -&gt; Stop
          More value iter2 -&gt; More (f value) (TransformedIter f iter2) }
      In an equation for `next':
          next (TransformedIter f iter)
            = case next iter of {
                Stop -&gt; Stop
                More value iter2 -&gt; More (f value) (TransformedIter f iter2) }
  </code></pre>
  
  <p>I changed the instance declaration to:</p>
  
  <pre><code>instance Iter (Iter iter =&gt; TransformedIter iter from) where
  </code></pre>
  
  <p>That generated another error:</p>
  
  <pre><code>Main.hs:21:10:
      Illegal instance declaration for `Iter
                                          (Iter iter =&gt; TransformedIter iter from)'
        (All instance types must be of the form (T a1 ... an)
         where a1 ... an are *distinct type variables*,
         and each type variable appears at most once in the instance head.
         Use -XFlexibleInstances if you want to disable this.)
      In the instance declaration for `Iter (Iter iter =&gt;
                                             TransformedIter iter from)'
  </code></pre>
  
  <p>And after I added -XFlexibleInstances I got:</p>
  
  <pre><code>Main.hs:21:10:
      Illegal polymorphic or qualified type:
        Iter iter =&gt; TransformedIter iter from
      In the instance declaration for `Iter (Iter iter =&gt;
                                             TransformedIter iter from)'
  </code></pre>
  
  <p>So I still do not see how to declare TransformedIter to be an instance of Iter. Any clues?</p>
  
  <h1>Update 2</h1>
  
  <p>Using GADTs GHC extension I managed to define TransformedIter:</p>
  
  <pre><code>module Main where
  
  data NextResult a iter = Stop | More a (iter a)
  
  class Iter iter where
    next :: iter a -&gt; NextResult a iter
  
  toList :: (Iter c) =&gt; c a -&gt; [a]
  toList iter = case next iter of
    Stop -&gt; []
    More value iter2 -&gt; value : toList iter2 
  
  instance Iter [] where
    next [] = Stop
    next (x:xs) = More x xs
  
  data TransformedIter iter from to where
    TransformedIter :: Iter iter =&gt; 
                       (from-&gt;to) -&gt; (iter from) -&gt; TransformedIter iter from to
  
  instance Iter (TransformedIter iter from) where
    next (TransformedIter f iter) = case next iter of
      Stop -&gt; Stop
      More value iter2 -&gt; More (f value) (TransformedIter f iter2)
  
  twice = (*) 2
  
  main = let iter = TransformedIter twice [1,2,3,4,5] in print $ toList iter
  </code></pre>
  
  <p>That compiles and prints the expected 2 4 6 8 10. But is this extension really necessary?</p>