🎓 A1Learner
🔍
0 of 47 lessons completed

Haskell Functional Dependencies

A functional dependency is a promise that one type fixes another type. In class Collects, the collection type fixes the element type.

A list collection fixes its element type

The list instance ties a list to its element type. The elements of a list of numbers are numbers.

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE FlexibleInstances #-}
class Collects e c | c -> e where
  elems :: c -> [e]
instance Collects a [a] where
  elems xs = xs
main :: IO ()
main = print (elems [1, 2, 3])

A Maybe collection fixes its wrapped type

The Maybe instance ties a Maybe value to its wrapped type. Its elements form a one element list or an empty list.

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE FlexibleInstances #-}
class Collects e c | c -> e where
  elems :: c -> [e]
instance Collects a (Maybe a) where
  elems Nothing = []
  elems (Just x) = [x]
main :: IO ()
main = do
  print (elems (Just 5))
  print (elems (Nothing :: Maybe Int))

The compiler infers the element type from the collection

The call gives only a list. The compiler still knows the elements are numbers.

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE FlexibleInstances #-}
class Collects e c | c -> e where
  elems :: c -> [e]
getElems :: Collects e c => c -> [e]
getElems = elems
instance Collects a [a] where
  elems xs = xs
main :: IO ()
main = print (getElems [7, 8])

Example

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE FlexibleInstances #-}
class Collects e c | c -> e where
  elems :: c -> [e]
  count :: c -> Int
  count c = length (elems c)
data Box a = Box a
getElems :: Collects e c => c -> [e]
getElems = elems
instance Collects a [a] where
  elems xs = xs
instance Collects a (Maybe a) where
  elems Nothing = []
  elems (Just x) = [x]
instance Collects a (Box a) where
  elems (Box x) = [x]
main :: IO ()
main = do
  print (getElems [7, 8])
  print (count (Just 9))
  print (getElems (Box 5))

Key points

  • Functional dependency: a promise written after a class name that one type parameter fixes another.
  • The arrow in c -> e says the collection type determines the element type.
  • A functional dependency lets the compiler work out the element type from the collection alone.
  • Use a functional dependency when one parameter should always decide another.
  • A multi-parameter class has two or more type parameters.

In this example, Collects promises that the collection type fixes the element type. The list, Maybe, and Box instances each honour that promise. The prints show list elements, the count of a Maybe value, and the elements of a box.

Note

A class with a functional dependency needs the FunctionalDependencies and MultiParamTypeClasses extensions.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Haskell Playground

Exercise

In class Collects e c | c -> e, what does c -> e promise?