https://wiki.haskell.org/index.php?title=Functional_dependencies_vs._type_families&feed=atom&action=historyFunctional dependencies vs. type families - Revision history2024-03-19T12:47:20ZRevision history for this page on the wikiMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=Functional_dependencies_vs._type_families&diff=57509&oldid=prevLemming: type functions in foreign declarations2014-01-27T20:35:26Z<p>type functions in foreign declarations</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 20:35, 27 January 2014</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Line 48:</td>
<td colspan="2" class="diff-lineno">Line 48:</td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></haskell></div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></haskell></div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>=== Type functions in foreign declarations ===</div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>A foreign import or export must not have type constraints</div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>but it can contain type functions.</div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>That is, you must not declare</div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><haskell></div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>foreign import ccall unsafe "llvm_convert"</div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> convert :: (MakeValueTuple a b) => StablePtr a -> IO (Ptr b)</div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></haskell></div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>for a type class <hask>MakeValueTuple</hask></div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>with a functional dependency from <hask>a</hask> to <hask>b</hask>,</div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>but you can declare</div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><haskell></div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>foreign import ccall unsafe "llvm_convert"</div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> convert :: StablePtr a -> IO (Ptr (ValueTuple b))</div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></haskell></div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>for a type function <hask>ValueTuple</hask>.</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== No TypeSynonymInstances ===</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== No TypeSynonymInstances ===</div></td>
</tr>
</table>Lemminghttps://wiki.haskell.org/index.php?title=Functional_dependencies_vs._type_families&diff=45956&oldid=prevLemming: Category:Language extensions2012-06-10T10:10:33Z<p>Category:Language extensions</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 10:10, 10 June 2012</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Line 188:</td>
<td colspan="2" class="diff-lineno">Line 188:</td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>This article was written in June 2012</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>This article was written in June 2012</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>when GHC-7.4.1 was the current version of GHC.</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>when GHC-7.4.1 was the current version of GHC.</div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Language extensions]]</div></td>
</tr>
</table>Lemminghttps://wiki.haskell.org/index.php?title=Functional_dependencies_vs._type_families&diff=45955&oldid=prevLemming: converted my Haskell-Cafe post to Wiki2012-06-10T10:08:07Z<p>converted my Haskell-Cafe post to Wiki</p>
<p><b>New page</b></p><div>When I reported a<br />
[http://hackage.haskell.org/trac/ghc/ticket/5970 typechecker performance problem]<br />
related to functional dependencies<br />
I promised to try to convert from functional dependencies to type families.<br />
<br />
Thus I converted my code and the llvm package to type-families:<br />
http://code.haskell.org/~thielema/llvm-tf/<br />
<br />
Here are some of my experiences:<br />
<br />
== Advantages of TypeFamilies ==<br />
<br />
=== Speed ===<br />
<br />
For what I did the type families solution was considerably faster<br />
than the functional dependencies code at least in GHC-7.4.1.<br />
Thus the bug in ticket 5970 does no longer hurt me.<br />
(In GHC-6.12.3 the conversion to type families made the compilation even slower.)<br />
<br />
<br />
=== Anonymous type function values ===<br />
<br />
One of the most annoying type classes of the llvm package was the IsSized class:<br />
<haskell><br />
class (LLVM.IsType a, IsPositive size) => IsSized a size | a -> size<br />
</haskell><br />
where size is a type-level decimal natural number.<br />
<br />
Many llvm functions require that an LLVM type has a size<br />
where the particular size is not important.<br />
However, I always have to name the size type.<br />
I also cannot get rid of it using a subclass, like<br />
<haskell><br />
class (IsSized a size) => IsAnonymouslySized a where<br />
</haskell><br />
The <hask>size</hask> type is somehow sticky.<br />
<br />
The conversion of this type class to type families is straightforward:<br />
<haskell><br />
class (IsType a, PositiveT (SizeOf a)) => IsSized a where<br />
type SizeOf a :: *<br />
</haskell><br />
<br />
Now I have to use <hask>SizeOf</hask> only if needed.<br />
I can also easily define sub-classes like<br />
<haskell><br />
class (IsSized a) => C a where<br />
</haskell><br />
<br />
<br />
=== No TypeSynonymInstances ===<br />
<br />
At the right hand side of a <hask>type instance</hask> I can use type synonyms like<br />
<haskell><br />
type instance F T = String<br />
</haskell><br />
without the <hask>TypeSynonymInstance</hask> extension.<br />
This feels somehow more correct<br />
than refering to a type synonym in a class instance head like in<br />
<haskell><br />
instance C T String where<br />
</haskell><br />
<br />
The compiler does not need to analyze <hask>String</hask> in order to find the correct instance.<br />
<br />
<br />
=== No FlexibleInstances ===<br />
<br />
The same applies to<br />
<haskell><br />
instance C (T a) (A (B a))<br />
</haskell><br />
which is a flexible instance that is not required for<br />
<haskell><br />
type instance F (T a) = A (B a)<br />
</haskell><br />
<br />
<br />
=== No MultiParamTypeClass, No UndecidableInstances ===<br />
<br />
I have some type classes that convert a type to another type and a tuple of types to another tuple of types<br />
where the element types are converted accordingly.<br />
With functional dependencies:<br />
<haskell><br />
class MakeValueTuple haskellTuple llvmTuple | haskellTuple -> llvmTuple where<br />
<br />
instance (MakeValueTuple ha la, MakeValueTuple hb lb) =><br />
MakeValueTuple (ha,hb) (la,lb)<br />
</haskell><br />
The class is a multi-parameter type class and the instance is undecidable.<br />
<br />
This is much simpler with type families:<br />
<haskell><br />
class MakeValueTuple haskellTuple where<br />
type ValueTuple haskellTuple :: *<br />
<br />
instance (MakeValueTuple ha, MakeValueTuple hb) =><br />
MakeValueTuple (ha,hb) where<br />
type ValueTuple (ha,hb) = (ValueTuple ha, ValueTuple hb)<br />
</haskell><br />
<br />
<br />
Thus summarized: Type families may replace several other type extensions.<br />
If I ignore the associated type functions<br />
then many classes become Haskell 98 with Haskell 98 instances.<br />
This is good because those instances prevent instance conflicts with other non-orphan instances.<br />
<br />
<br />
== Disadvantage of TypeFamilies ==<br />
<br />
=== Redundant instance arguments ===<br />
<br />
I have to write the type arguments both in the instance head<br />
and in the function argument.<br />
This is especially annoying in the presence of multi-parameter type classes<br />
with bidirectional dependencies.<br />
E.g.<br />
<haskell><br />
class (a ~ Input parameter b, b ~ Output parameter a) => C parameter a b where<br />
type Input parameter b :: *<br />
type Output parameter a :: *<br />
process :: Causal p (parameter, a) b<br />
<br />
instance (...) => C (FilterParam a) v (FilterResult v) where<br />
type Input (FilterParam a) (FilterResult v) = v<br />
type Output (FilterParam a) v = FilterResult v<br />
</haskell><br />
<br />
<br />
With functional dependencies it was:<br />
<haskell><br />
class C parameter a b | parameter a -> b, parameter b -> a where<br />
process :: Causal p (parameter, a) b<br />
<br />
instance (...) => C (FilterParam a) v (FilterResult v) where<br />
</haskell><br />
<br />
<br />
=== Bidirectional dependencies ===<br />
<br />
In GHC-6.12.3 it was not possible to write<br />
<haskell><br />
class (a ~ Back b, b ~ Forth a) => C a b where<br />
</haskell><br />
Fortunately, this is now allowed in GHC-7.<br />
But bidirectional dependencies are still cumbersome to work with<br />
as shown in the example above.<br />
<br />
<br />
=== Equality constraints are not supported for newtype deriving ===<br />
<br />
Not so important, just for completeness:<br />
http://hackage.haskell.org/trac/ghc/ticket/6088<br />
<br />
<br />
== Confusions ==<br />
<br />
=== Upper case type function names ===<br />
<br />
Why are type function names upper case, not lower case?<br />
They are not constructors after all.<br />
Maybe this is one reason,<br />
why I forget from time to time that type functions are not injective.<br />
<br />
Sure, lower-case type variables are implicitly forall quantified in Haskell 98.<br />
In the presence of lower-case type functions we would need explicit forall quantification.<br />
<br />
=== Why can associated types not be exported by C(AssocType) syntax? ===<br />
<br />
Why must they be exported independently from the associated class?<br />
<br />
<br />
=== FlexibleContexts ===<br />
<br />
The context <hask>(Class (TypeFun a))</hask><br />
requires <hask>FlexibleContexts</hask> extension,<br />
whereas the equivalent <hask>(TypeFun a ~ b, Class b)</hask><br />
does not require <hask>FlexibleContexts</hask>.<br />
<br />
<br />
== See also ==<br />
<br />
* The llvm package converted to type families: http://code.haskell.org/~thielema/llvm-tf/<br />
* [http://www.haskell.org/pipermail/haskell-cafe/2012-June/101629.html Haskell Cafe post]<br />
<br />
== Footnotes ==<br />
<br />
This article was written in June 2012<br />
when GHC-7.4.1 was the current version of GHC.</div>Lemming