|
|
# Relaxed Dependency Analysis
|
|
|
|
|
|
|
|
|
In Haskell 98, a group of bindings is sorted into strongly-connected components, and then type-checked in dependency order ([ H98 s4.5.1](http://haskell.org/onlinereport/decls.html#sect4.5.1)). As each dependency group is type-checked, any binders of the group that have an explicit type signature are put in the type environment with the specified polymorphic type, and all others are monomorphic until the group is generalized ([ H98 s4.5.2](http://haskell.org/onlinereport/decls.html#sect4.5.2)).
|
|
|
|
|
|
|
|
|
Consider
|
|
|
|
|
|
```wiki
|
|
|
data BalancedTree a = Zero a | Succ (BalancedTree (a,a))
|
|
|
|
|
|
zig :: BalancedTree a -> a
|
|
|
zig (Zero a) = a
|
|
|
zig (Succ t) = fst (zag t)
|
|
|
|
|
|
zag (Zero a) = a
|
|
|
zag (Succ t) = snd (zig t)
|
|
|
```
|
|
|
|
|
|
|
|
|
As with many operations on non-regular (or nested) types, `zig` and `zag` need to be polymorphic in the element type. In Haskell 98, the bindings of the two functions are interdependent, and thus constitute a single binding group. When type inference is performed on this group, `zig` may be used at different types, because it has a user-supplied polymorphic signature. However, `zag` may not, and the example is rejected, unless we add an explicit type signature for `zag`.
|
|
|
|
|
|
|
|
|
However GHC, Hugs and Nhc98 follow the suggestion of Mark Jones in [ Typing Haskell in Haskell](http://www.cse.ogi.edu/~mpj/thih/), that the dependency analysis should ignore references to variables that have an explicit type signature. Hence `zag` does not depend on `zig`, and we can infer the type
|
|
|
|
|
|
```wiki
|
|
|
zag :: BalancedTree a -> a
|
|
|
```
|
|
|
|
|
|
|
|
|
and then go on to successfully check the type signature of `zig`.
|
|
|
|
|
|
|
|
|
Dependency groups are smaller, and more programs type-check. |