在Haskell中,在类A类的函数中从另一个类型B返回一些东西

Question

我正在做一个有趣的项目,我正在尝试从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

是的,我正在尝试翻译迭代器的概念(在这种情况下,它只是一个围绕实际列表的框).

这是我对一个简单List的实现:

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

迭代器函数将列表包装成a 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

我不太明白.LinkedListIterator有一个Iterator实例,为什么期望的Type"it e"与实际类型"LinkedListIterator e"不兼容(据我所知,它是Iterator 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时玩得很开心,只能推荐它.如上所述,人们应该学习哈斯克尔的习语.

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)

Answer 1

iterator :: Iterator it => i e -> it e

这意味着呼叫者可以选择it成为他们想要的任何东西,但要实施Iterator.另一种看待它的方式是,为所有实现的类型工作是一种承诺iterator.itIterator

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. 阅读Typeclassopedia中的类Foldable和Traversable类型.事实上,阅读Typeclassopedia,它是对一些更可怕的类型类的一个很好的介绍.