Role of functional dependency in `Unfoldable` typeclass of Haskell Collection API

Question

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?

Answer 1

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