Changes between Version 23 and Version 24 of FunctionalDependencies


Ignore:
Timestamp:
May 23, 2006 1:03:00 PM (8 years ago)
Author:
ross@…
Comment:

expand use cases

Legend:

Unmodified
Added
Removed
Modified
  • FunctionalDependencies

    v23 v24  
    2424[[TicketQuery(description~=FunctionalDependencies)]] 
    2525 
    26 == Use Cases == 
    27  * Edison data structures library 
    28  * Monad Transformers library 
    29  * possible use in Hat tracer [attachment:thoughtsOnMixing.ps] 
    30  
    3126== Pros == 
    3227 * In GHC and Hugs for a long time. 
     
    10095 * With FlexibleInstances and no OverlappingInstances, this system is coherent and decidable (CHR paper, corr. 1). 
    10196 
    102  * Unfortunately the "coverage" condition rules out instances like the following, from the monad transformer library: 
    103    {{{ 
    104 class (Monoid w, Monad m) => MonadWriter w m | m -> w 
    105 instance (Error e, MonadWriter w m) => MonadWriter w (ErrorT e m) 
    106 }}} 
     97 * Because it ignores the context, the "coverage" condition does not allow some instances for "transformere", e.g. in the monad transformer library (see [wiki:FunctionalDependencies#UseCases Use Cases] below). 
    10798 
    10899== GHC and Hugs == 
     
    188179Another possibility is to modify instance reduction to record the functional dependency on the constraint being reduced (see [http://www.cs.kent.ac.uk/~cr3/chr/Tc2CHR.hs]). 
    189180 
     181== Use Cases == 
     182 
     183 [http://www.haskell.org/ghc/docs/6.4/html/libraries/mtl/ Monad Transformers library] ([http://www.csee.ogi.edu/~diatchki/monadLib new version]):: 
     184   Auxiliary parameters (state, errors, output, environment) are determined by the monad, e.g.: 
     185   {{{ 
     186class (Monoid w, Monad m) => MonadWriter w m | m -> w 
     187}}} 
     188   All dependencies are full, and there are two sorts of instances: 
     189   base case satisfying the coverage condition, e.g. 
     190   {{{ 
     191instance (Monoid w, Monad m) => MonadWriter w (WriterT w m) 
     192}}} 
     193   and transformer applications where the dependency is derived from dependencies in the context, e.g. 
     194   {{{ 
     195instance (Error e, MonadWriter w m) => MonadWriter w (ErrorT e m) 
     196}}} 
     197 
     198 [http://www.eecs.tufts.edu/~rdocki01/edison.html Edison] data structures library:: 
     199   Keys (or elements of sets) are determined by the collection, e.g. 
     200   {{{ 
     201class (Coll c a, OrdCollX c a) => OrdColl c a | c -> a 
     202}}} 
     203   The most complex case is represented by adaptors like 
     204   {{{ 
     205instance (OrdColl h a, Ord a) => OrdColl (Min h a) a 
     206}}} 
     207   All dependencies are full and all instances satisfy the coverage condition. 
     208 
     209 [http://darcs.haskell.org/packages/collections/ collections] package:: 
     210   Elements are determined by the collection, e.g. 
     211   {{{ 
     212class Foldable c o => Collection c i o | c -> i o 
     213}}} 
     214   The most complex case is represented by views like 
     215   {{{ 
     216instance Collection m (k,v) (k,v) => Collection (KeysView m k v) (k,v) k 
     217}}} 
     218   All dependencies are full and all instances satisfy the coverage condition. 
     219 
     220 [http://www.haskell.org/yampa/ Yampa]:: 
     221   Vector spaces, with the scalar type determined by the vector type. 
     222   Some non-full dependencies, but all instances satisfy the coverage condition. 
     223 
     224 possible use in Hat tracer:: 
     225   [attachment:thoughtsOnMixing.ps] 
     226 
     227Functional dependencies are often used in fairly experimental work together with UndecidableInstances and OverlappingInstances, but since those are unlikely to be included in Haskell', they are not considered further here. 
     228 
    190229----------------------------------------------------------------------------------