CODEWITHSUNDEEP
haskelltypeclassfunctional-dependencies
Petr
Petr

Reputation: 63419

All type parameters depending on each other in functional dependencies

Let's say I have a type class with n type parameters and I want any of them to uniquely determine all the other ones. Is it enough to make the dependencies form a cycle like in

class Foo a b c | a -> b, b -> c, c -> a

(linear) where there is a path from every parameter to every other one, or do I need to expand all possible paths like in

class Bar a b c | a -> b, a -> c, b -> a, b -> c, c -> a, c -> b

(quadratic)? Is there any observable difference between the two? And how about

class Baz a b c | a -> b c, b -> a c, c -> a b

Upvotes: 14

Views: 141

Answers (1)

mniip
mniip

Reputation: 796

Operationally, all of the above are equivalent:

First of all, a -> b c is quite literally the same thing as a -> b, a -> c.

Next, assume we got Foo a b c => (a, b, c). Say, we realize that a ~ A. We find the a -> b fundep and scan through instances to find b ~ B. Again we find the b -> c fundep and realize c ~ C. Voila we got (A, B, C).

If instead we had Bar a b c => (a, b, c) with a ~ A, we would've found a -> b, and b ~ B, however before finding b -> c, we would have found a -> c.

The only difference is which fundep arrows are used to infer the types. a -> b, b -> c and a -> b, a -> c can't produce different results.

Upvotes: 1

Related Questions