Haskell - container of container and instance declration

Question

Short version from a Haskell newbie: suppose I have a class Container where the Container has * -> * kind. I want to put that into another container and still make the second container an instance of the original class like in:

data Container2 a container = Container2 (container a)

instance Container (Conrainer2 a) where ...

But it seems this is not possible as GHC always generates errors like:

Kind mis-match

    The first argument of `Container' should have kind `* -> *',
    but `Container2 a' has kind `(* -> *) -> *'

Is it possible to workaround that?

Long version: I am toying with the following code modeling an iterator interface in Java:

module Main where

data NextResult a iter = Stop | More a (iter a)

class Iter iter where
  next :: iter a -> NextResult a iter

-- Convert iterator to a list
toList :: (Iter c) => c a -> [a]
toList iter = case next iter of
  Stop -> []
  More value iter2 -> 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

With GHC 7.4.1 this compiles and prints the expected 1 2 3 4 5. 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:

data TransformedIter from to iter = TransformedIter (from->to) (iter from)

instance Iter (TransformedIter from to) where
  next (TransformedIter f iter) = case next iter of
    Stop -> Stop
    More value iter2 -> More (f value) (TransformedIter f iter2)

But that generated the error:

Main.hs:21:16:
    Kind mis-match
    The first argument of `Iter' should have kind `* -> *',
    but `TransformedIter from to' has kind `(* -> *) -> *'
    In the instance declaration for `Iter (TransformedIter from to)'

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?

Update

I misunderstood how instance declaration works. Based on the suggestion below I flipped the order of TransformedIter types and ended up with:

module Main where

data NextResult a iter = Stop | More a (iter a)

class Iter iter where
  next :: iter a -> NextResult a iter

toList :: (Iter c) => c a -> [a]
toList iter = case next iter of
  Stop -> []
  More value iter2 -> 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->to) (iter from)

instance Iter (TransformedIter iter from) where
  next (TransformedIter f iter) = case next iter of
    Stop -> Stop
    More value iter2 -> More (f value) (TransformedIter f iter2)

However that produced another error:

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 -> Stop
        More value iter2 -> More (f value) (TransformedIter f iter2) }
    In an equation for `next':
        next (TransformedIter f iter)
          = case next iter of {
              Stop -> Stop
              More value iter2 -> More (f value) (TransformedIter f iter2) }

I changed the instance declaration to:

instance Iter (Iter iter => TransformedIter iter from) where

That generated another error:

Main.hs:21:10:
    Illegal instance declaration for `Iter
                                        (Iter iter => 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 =>
                                           TransformedIter iter from)'

And after I added -XFlexibleInstances I got:

Main.hs:21:10:
    Illegal polymorphic or qualified type:
      Iter iter => TransformedIter iter from
    In the instance declaration for `Iter (Iter iter =>
                                           TransformedIter iter from)'

So I still do not see how to declare TransformedIter to be an instance of Iter. Any clues?

Update 2

Using GADTs GHC extension I managed to define TransformedIter:

module Main where

data NextResult a iter = Stop | More a (iter a)

class Iter iter where
  next :: iter a -> NextResult a iter

toList :: (Iter c) => c a -> [a]
toList iter = case next iter of
  Stop -> []
  More value iter2 -> value : toList iter2 

instance Iter [] where
  next [] = Stop
  next (x:xs) = More x xs

data TransformedIter iter from to where
  TransformedIter :: Iter iter => 
                     (from->to) -> (iter from) -> TransformedIter iter from to

instance Iter (TransformedIter iter from) where
  next (TransformedIter f iter) = case next iter of
    Stop -> Stop
    More value iter2 -> More (f value) (TransformedIter f iter2)

twice = (*) 2

main = let iter = TransformedIter twice [1,2,3,4,5] in print $ toList iter

That compiles and prints the expected 2 4 6 8 10. But is this extension really necessary?

Just flip the arguments like data Container2 container a = Container2 (container a). When you have instance Iter f it anticipates that you can write f a for an iterators over elements a, while if you have type F = TransformedIter from to then F a isn't an iterator over elements of a, it's an iterator over elements to from the inner iterator a. — J. Abrahamson
Also, this class already exists in Haskell as Foldable. In particular, any Foldable t has toList :: t a -> [a] which lets you build your iterator. — J. Abrahamson
Thanks @J. Abrahamson , I understood what was wrong with the type ordering. But I now I got another error, see the updated version. — Igor Bukanov
Try instance Iter iter => Iter (TransformedIter iter from) where: the constraints come first. — J. Abrahamson
If your problem is solved, the appropriate thing to do is add an answer to your own question (and go ahead and accept it) instead of modifying the question to include the answer. That way, future visitors will know at a glance where the problems end and the solutions begin! =) — Daniel Wagner

Igor Bukanov Igor Bukanov · Accepted Answer · 2014-11-21T22:15:00

The answer was given in the comments by J. Abrahamson, now I have finally a version that works without using any GHC extensions (I used wrong syntax to context in the instance declaration previously):

module Main where

data NextResult a iter = Stop | More a (iter a)

class Iter iter where
  next :: iter a -> NextResult a iter

toList :: (Iter c) => c a -> [a]
toList iter = case next iter of
  Stop -> []
  More value iter2 -> value : toList iter2 

instance Iter [] where
  next [] = Stop
  next (x:xs) = More x xs

data TransformedIter iter from to = TransformedIter (from->to) (iter from)

instance Iter iter => Iter (TransformedIter iter from) where
  next (TransformedIter f iter) = case next iter of
    Stop -> Stop
    More value iter2 -> More (f value) (TransformedIter f iter2)

twice = (*) 2

main = let iter = TransformedIter twice [1,2,3,4,5] in print $ toList iter

That prints 2 4 6 8 10

Haskell - container of container and instance declration

Update

Update 2

1 Answers