Роль функциональной зависимости в стиле «Unfoldable» класса Haskell Collection API

Question

Im пытается понять дизайн библиотеки Haskell's Data.Collection, исходящей от фона Scala-Literate.

Он использует Functional Dependencies (у которых есть Scala analog), но способ, которым они используются, для меня не имеет смысла. В классе , воспроизведенном ниже, тип элемента i показан как , определяемый типами сбора c.

class Unfoldable c i | c -> i 

Класс коллекции с ненаблюдаемых элементов. Он является двойным классом Foldable.

Пожалуйста, объясните роль, которую играет здесь и намерение дизайна, в идеале, с примером использования?

Answer 1

Ограничение, выражаемое этой функциональной зависимостью, заключается в том, что данный тип коллекции 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 c i where 
    empty :: c 

instance Unfoldable [a] a where 
    empty = [] 

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

xs :: [a] 
xs = empty 

Это приводит к:

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