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

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

4 голосов
/ 05 февраля 2012

Я делаю забавный проект, в котором я пытаюсь переделать некоторые базовые типы данных и концепции из 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

Я исключил другие функции, такие как удаление, содержит, добавить все для упрощения.

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

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" (который, насколько я понимаю, является итератором e). Что означает тильда (~)? Что такое переменная жесткого типа?

РЕДАКТИРОВАТЬ: Я изменил название с 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-from-type- проблема класса 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)

1 Ответ

8 голосов
/ 05 февраля 2012 
iterator :: Iterator it => i e -> it e

Это означает, что вызывающий абонент может выбрать it в качестве того, что он хочет, при условии, что он реализует Iterator. Еще один способ взглянуть на это - обещание от iterator работать для всех типов it, которые реализуют Iterator.

Ваша реализация предоставляет LinkedListIterator, независимо от того, что запрашивает вызывающий.

Компилятор не может доказать, что это одно и то же (поскольку вызывающая сторона может потребовать другую реализацию Iterator), поэтому выдает ошибку.

Это отличается от Java, где вызывающий выбирает классы входных данных, а вызываемый выбирает класс выходных данных. В Haskell вызывающая сторона выбирает типы ввода и вывода.

~ означает равенство типов.

Некоторые более широкие вопросы. (И я ценю, что вы пытаетесь перевести идиомы Java в Haskell, но в то же время вам нужно изучить идиомы Haskell.)

  1. Иногда вы не хотите возвращать значение, которое реализует класс типов, вы просто хотите вернуть значение.

    Если вместо Iterator быть классом типов, это был тип данных ... 

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

    ... тогда вы могли бы просто вернуть значение типа Iterator и не беспокоиться о различных реализациях классов типов.

    Ленивость означает, что последовательные значения из итератора не будут сгенерированы (и исключения не будут выброшены), пока их не попросят. До тех пор, пока вы не перейдете к старому значению итератора, эти значения можно будет собирать мусором во время итерации, поэтому мы по-прежнему будем использовать постоянное пространство.

  2. Лучшее определение Iterator будет 

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

    Это лучше, потому что вам труднее запрашивать следующее значение у итератора без предварительной проверки, чтобы увидеть следующее значение.

  3. Мое второе определение Iterator немного похоже на ваше определение LinkedList, а также на определение стандартных списков Haskell (которые сами являются связанными списками). И действительно, идиоматично использовать списки Haskell в качестве промежуточной структуры данных там, где это необходимо для итерации.

  4. Подробнее о классах типов Foldable и Traversable в Typeclassopedia. На самом деле, прочитайте Typeclassopedia , это хорошее введение в некоторые из самых страшных классов типов.

...