The role of functional dependency in the "Unfoldable" style of the Haskell Collection API

Question

I am trying to understand the design of the Haskell library Data.Collectioncoming from a Scala-literate background.

It uses Functional Dependencies (which have Scala analog ), but the way they are used does not make sense to me. In the class Unfoldablereproduced below, the type of the item is idisplayed as determined by the type of collection c.

class Unfoldable c i | c -> i

Collection class with unobservable elements. He is a double class Foldable.

Please explain the role that addiction c -> iand design intent plays here , ideally with a usage example?

Answer 1

The limitation expressed by this functional dependence is that this type of collection c, the type of its elements is ialready defined. For example, if c ~ [a], i.e. The collection is a list of as, then we should be able to determine what i ~ a.

Without this functional dependency, we could have two examples, for example. Unfoldable [a] a(obvious / alleged instance) and Unfoldable [a] [a](with something like insert = concat, singleton = id). If typechecker sees something like empty :: [a], it will have no choice which instance will be used:

{-# 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

It leads to:

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