函数依赖在Haskell Collection API的Unfoldable类型类中的作用 [英] Role of functional dependency in `Unfoldable` typeclass of Haskell Collection API

问题描述

我试图理解Haskell的的设计 Data.Collection 库，来自Scala知识背景。

它使用功能依赖（其中包含 Scala analog ），但它们的使用方式对我来说没有意义。在下面转载的 Unfoldable 类中，元素类型 i 显示为，由集合类型 c 。

  class不可折叠的ci | c  - > i 
  

具有不可观察元素的集合类。它是 Foldable 类的双重元素。

请解释角色依赖项 c - >我在这里玩和设计意图，理想情况下用一个例子吗？

由该函数依赖表达的是，如果给定集合类型 c ，则其项目类型 i 已经确定。例如，如果 c〜[a] ，即集合是 a s的列表，那么我们应该是能够确定 i〜a 。

没有这种函数依赖关系，我们可能有两个实例，例如 Unfoldable [a] a （显而易见的/预期的实例）和 Unfoldable [a] [a] insert = concat ， singleton = id ）。如果类型检查器看到 empty :: [a] 之类的东西，那么它将无法选择使用哪个实例：

  { - ＃LANGUAGE MultiParamTypeClasses，FlexibleInstances＃ - } 
 
 class unfoldable ci其中
空:: c 
 
实例Unfoldable [a] a其中
空= [] 
 
实例不可折叠[a] [a]其中
空= [] 
 
 xs :: [a] 
 xs =空
  

结果如下：

 由于使用'empty'
而没有引用（Unfoldable [a] i0）的实例$ b $类型变量'i0'不明确
相关绑定包括
 xs :: [a] 
注意：有几个潜在的实例：
实例不可折叠的[a] a 
实例Unfoldable [a] [a] 
在表达式中：empty 
在`xs'的等式中：xs = empty 
  

Im trying to understand the design of Haskell's Data.Collection library, coming from a Scala-literate background.

It uses Functional Dependencies (which have a Scala analog) but the way they're used doesn't make sense to me. In the Unfoldable class, reproduced below, the element type i is shown as determined by the collection type c.

class Unfoldable c i | c -> i

Class of collection with unobservable elements. It is the dual of the Foldable class.

Please explain the role that the dependency c -> i is playing here and the design intent, ideally with an example of usage?

解决方案

The constraint expressed by that functional dependency is that given a collection type c, the type of its items i is already determined. For example, if c ~ [a], i.e. the collection is a list of as, then we should be able to determine that i ~ a.

Without that functional dependency, we could have two instances e.g. Unfoldable [a] a (the obvious/intended instance) and Unfoldable [a] [a] (with something like insert = concat, singleton = id). If the typechecker then sees something like empty :: [a], it would have no way of choosing which instance to use:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}

class Unfoldable c i where
    empty :: c

instance Unfoldable [a] a where
    empty = []

instance Unfoldable [a] [a] where
    empty = []

xs :: [a]
xs = empty

This results in:

No instance for (Unfoldable [a] i0) arising from a use of `empty'
The type variable `i0' is ambiguous
Relevant bindings include
  xs :: [a]
Note: there are several potential instances:
  instance Unfoldable [a] a
  instance Unfoldable [a] [a]
In the expression: empty
In an equation for `xs': xs = empty

这篇关于函数依赖在Haskell Collection API的Unfoldable类型类中的作用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！