Возврат чего-то из другого класса типов B в функцию класса типов A в Haskell

Я делаю забавный проект, в котором пытаюсь переделать некоторые базовые типы данных и концепции из Java. В настоящее время я занимаюсь итераторами.

Мой подход заключается в следующем: (1) перевести интерфейсы в классы типов (2) объявить пользовательские типы данных и экземпляры для реальных реализаций.

Поэтому я создал следующие классы типов:

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

Да, я пытаюсь перевести концепцию итераторов (в данном случае это просто рамка вокруг фактического списка).

Вот моя реализация простого списка:

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

Я исключил другие функции, такие как remove, contains, addAll для упрощения.

Вот итератор:

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)

Наконец, экземпляр для Iterable LinkedList отсутствует. Вот что я делаю:

instance Iterable LinkedList where
    iterator list = It list

Функция итератора оборачивает список в LinkedListIterator и возвращает его. Здесь GHC заявляет об ошибке:

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

чего я не совсем понимаю. Существует экземпляр Iterator для LinkedListIterator, так почему же ожидаемый тип "it e" несовместим с фактическим типом "LinkedListIterator e" (который, насколько я понимаю, является Iterator e) . Что вообще означает тильда (~)? Что такое переменная жесткого типа?

EDIT: я изменил заголовок с Translating Java Types into Haskell types: type deduction fail due to rigid type variable на Returning something from another type class B in function of type class A in Haskell, поскольку считаю, что моя реальная проблема связана с проблемой возврата чего-то типа класса B из типа класса A в функция-итератор.

РЕШЕНИЕ: благодаря ответам я изменил свой код на приведенную ниже версию. Тем не менее, я весело провел время, читая Typeclassopedia, и могу только рекомендовать его. Как уже было сказано, нужно выучить идиомы Haskell.

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)