https://wiki.haskell.org/api.php?action=feedcontributions&user=Sciolizer&feedformat=atomHaskellWiki - User contributions [en]2024-03-29T08:01:49ZUser contributionsMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=GHC/Type_families&diff=62485GHC/Type families2018-05-19T02:52:40Z<p>Sciolizer: Updated link to GHC trac issue on Type Familes vs Functional Dependencies</p>
<hr />
<div>{{GHCUsersGuide|glasgow_exts|type-families|a Type Family section}}<br />
<br />
<br />
Indexed type families, or '''type families''' for short, are a Haskell extension supporting ad-hoc overloading of data types. Type families are parametric types that can be assigned specialized representations based on the type parameters they are instantiated with. They are the data type analogue of [[Type class|type classes]]: families are used to define overloaded ''data'' in the same way that classes are used to define overloaded ''functions''. Type families are useful for generic programming, for creating highly parameterised library interfaces, and for creating interfaces with enhanced static information, much like dependent types.<br />
<br />
Type families come in two flavors: ''data families'' and ''type synonym families''. Data families are the indexed form of data and newtype definitions. Type synonym families are the indexed form of type synonyms. Each of these flavors can be defined in a standalone manner or ''associated'' with a type class. Standalone definitions are more general, while associated types can more clearly express how a type is used and lead to better error messages.<br />
<br />
''NB: see also Simon's [http://hackage.haskell.org/trac/ghc/blog/LetGeneralisationInGhc7 blog entry on let generalisation] for a significant change in the policy for let generalisation, driven by the type family extension. In brief: a few programs will puzzlingly fail to compile with <tt>-XTypeFamilies</tt> even though the code is legal Haskell 98.''<br />
<br />
== What are type families? ==<br />
<br />
The concept of a type family comes from type theory. An indexed type family in type theory is a partial function at the type level. Applying the function to parameters (called ''type indices'') yields a type. Type families permit a program to compute what data constructors it will operate on, rather than having them fixed statically (as with simple type systems) or treated as opaque unknowns (as with parametrically polymorphic types).<br />
<br />
Type families are to vanilla data types what type class methods are to regular functions. Vanilla polymorphic data types and functions have a single definition, which is used at all type instances. Classes and type families, on the other hand, have an interface definition and any number of instance definitions. A type family's interface definition declares its [[kind]] and its arity, or the number of type indices it takes. Instance definitions define the type family over some part of the domain.<br />
<br />
As a simple example of how type families differ from ordinary parametric data types, consider a strict list type. We can represent a list of <hask>Char</hask> in the usual way, with cons cells. We can do the same thing to represent a list of <hask>()</hask>, but since a strict <hask>()</hask> value carries no useful information, it would be more efficient to just store the length of the list. This can't be done with an ordinary parametric data type, because the data constructors used to represent the list would depend on the list's type parameter: if it's <hask>Char</hask> then the list consists of cons cells; if it's <hask>()</hask>, then the list consists of a single integer. We basically want to select between two different data types based on a type parameter. Using type families, this list type could be declared as follows:<br />
<br />
<haskell><br />
-- Declare a list-like data family<br />
data family XList a<br />
<br />
-- Declare a list-like instance for Char<br />
data instance XList Char = XCons !Char !(XList Char) | XNil<br />
<br />
-- Declare a number-like instance for ()<br />
data instance XList () = XListUnit !Int<br />
</haskell><br />
<br />
The right-hand sides of the two <code>data instance</code> declarations are exactly ordinary data definitions. In fact, a <code>data instance</code> declaration is nothing more than a shorthand for a <code>data</code> declaration followed by a <code>type instance</code> (see below) declaration. However, they define two instances of the same parametric data type, <hask>XList Char</hask> and <hask>XList ()</hask>, whereas ordinary data declarations define completely unrelated types. A recent [[Simonpj/Talk:FunWithTypeFuns|tutorial paper]] has more in-depth examples of programming with type families. <br />
<br />
[[GADT]]s bear some similarity to type families, in the sense that they allow a parametric type's constructors to depend on the type's parameters. However, all GADT constructors must be defined in one place, whereas type families can be extended. Functional dependencies are similar to type families, and many type classes that use functional dependencies can be equivalently expressed with type families. Type families provide a more functional style of type-level programming than the relational style of functional dependencies.<br />
<br />
== What do I need to use type families? ==<br />
<br />
Type families are a GHC extension enabled with the <code>-XTypeFamilies</code> flag or the <code>{-# LANGUAGE TypeFamilies #-}</code> pragma. The first stable release of GHC that properly supports type families is 6.10.1. (The 6.8 release included an early partial implementation, but its use is deprecated.) Please [http://hackage.haskell.org/trac/ghc/query?status=new&status=assigned&status=reopened&group=priority&type=bug&order=id&desc=1 report bugs] via the GHC bug tracker, ideally accompanied by a small example program that demonstrates the problem. Use the [mailto:glasgow-haskell-users@haskell.org GHC mailing list] for questions or for a discussion of this language extension and its description on this wiki page.<br />
<br />
== An associated data type example ==<br />
<br />
As an example, consider Ralf Hinze's [http://www.cs.ox.ac.uk/ralf.hinze/publications/GGTries.ps.gz generalised tries], a form of generic finite maps. <br />
<br />
=== The class declaration ===<br />
<br />
We define a type class whose instances are the types that we can use as keys in our generic maps:<br />
<haskell><br />
class GMapKey k where<br />
data GMap k :: * -> *<br />
empty :: GMap k v<br />
lookup :: k -> GMap k v -> Maybe v<br />
insert :: k -> v -> GMap k v -> GMap k v<br />
</haskell><br />
The interesting part is the ''associated data family'' declaration of the class. It gives a [http://www.haskell.org/ghc/docs/latest/html/users_guide/type-families.html#data-family-declarations ''kind signature''] (here <hask>* -> *</hask>) for the associated data type <hask>GMap k</hask> - analogous to how methods receive a type signature in a class declaration.<br />
<br />
What it is important to notice is that the first parameter of the associated type <hask>GMap</hask> coincides with the class parameter of <hask>GMapKey</hask>. This indicates that also in all instances of the class, the instances of the associated data type need to have their first argument match up with the instance type. In general, the type arguments of an associated type can be a subset of the class parameters (in a multi-parameter type class) and they can appear in any order, possibly in an order other than in the class head. The latter can be useful if the associated data type is partially applied in some contexts.<br />
<br />
The second important point is that as <hask>GMap k</hask> has kind <hask>* -> *</hask> and <hask>k</hask> (implicitly) has kind <hask>*</hask>, the type constructor <hask>GMap</hask> (without an argument) has kind <hask>* -> * -> *</hask>. Consequently, we see that <hask>GMap</hask> is applied to two arguments in the signatures of the methods <hask>empty</hask>, <hask>lookup</hask>, and <hask>insert</hask>.<br />
<br />
=== An Int instance ===<br />
<br />
To use Ints as keys into generic maps, we declare an instance that simply uses <hask>Data.IntMap</hask>, thusly:<br />
<haskell><br />
instance GMapKey Int where<br />
data GMap Int v = GMapInt (Data.IntMap.IntMap v)<br />
empty = GMapInt Data.IntMap.empty<br />
lookup k (GMapInt m) = Data.IntMap.lookup k m<br />
insert k v (GMapInt m) = GMapInt (Data.IntMap.insert k v m)<br />
</haskell><br />
The <hask>Int</hask> instance of the associated data type <hask>GMap</hask> needs to have both of its parameters, but as only the first one corresponds to a class parameter, the second needs to be a type variable (here <hask>v</hask>). As mentioned before, any associated type parameter that corresponds to a class parameter must be identical to the class parameter in each instance. The right hand side of the associated data declaration is like that of any other data type.<br />
<br />
NB: At the moment, GADT syntax is not allowed for associated data types (or other indexed types). This is not a fundamental limitation, but just a shortcoming of the current implementation, which we expect to lift in the future.<br />
<br />
As an exercise, implement an instance for <hask>Char</hask> that maps back to the <hask>Int</hask> instance using the conversion functions <hask>Char.ord</hask> and <hask>Char.chr</hask>.<br />
<br />
=== A unit instance ===<br />
<br />
Generic definitions, apart from elementary types, typically cover units, products, and sums. We start here with the unit instance for <hask>GMap</hask>:<br />
<haskell><br />
instance GMapKey () where<br />
data GMap () v = GMapUnit (Maybe v)<br />
empty = GMapUnit Nothing<br />
lookup () (GMapUnit v) = v<br />
insert () v (GMapUnit _) = GMapUnit $ Just v<br />
</haskell><br />
For unit, the map is just a <hask>Maybe</hask> value.<br />
<br />
=== Product and sum instances ===<br />
<br />
Next, let us define the instances for pairs and sums (i.e., <hask>Either</hask>):<br />
<haskell><br />
instance (GMapKey a, GMapKey b) => GMapKey (a, b) where<br />
data GMap (a, b) v = GMapPair (GMap a (GMap b v))<br />
empty = GMapPair empty<br />
lookup (a, b) (GMapPair gm) = lookup a gm >>= lookup b <br />
insert (a, b) v (GMapPair gm) = GMapPair $ case lookup a gm of<br />
Nothing -> insert a (insert b v empty) gm<br />
Just gm2 -> insert a (insert b v gm2 ) gm<br />
<br />
instance (GMapKey a, GMapKey b) => GMapKey (Either a b) where<br />
data GMap (Either a b) v = GMapEither (GMap a v) (GMap b v)<br />
empty = GMapEither empty empty<br />
lookup (Left a) (GMapEither gm1 _gm2) = lookup a gm1<br />
lookup (Right b) (GMapEither _gm1 gm2 ) = lookup b gm2<br />
insert (Left a) v (GMapEither gm1 gm2) = GMapEither (insert a v gm1) gm2<br />
insert (Right b) v (GMapEither gm1 gm2) = GMapEither gm1 (insert b v gm2)<br />
</haskell><br />
If you find this code algorithmically surprising, I'd suggest to have a look at [http://www.cs.ox.ac.uk/ralf.hinze/publications/index.html#J4 Ralf Hinze's paper]. The only novelty concerning associated types, in these two instances, is that the instances have a context <hask>(GMapKey a, GMapKey b)</hask>. Consequently, the right hand sides of the associated type declarations can use <hask>GMap</hask> recursively at the key types <hask>a</hask> and <hask>b</hask> - not unlike the method definitions use the class methods recursively at the types for which the class is given in the instance context.<br />
<br />
=== Using a generic map ===<br />
<br />
Finally, some code building and querying a generic map:<br />
<haskell><br />
myGMap :: GMap (Int, Either Char ()) String<br />
myGMap = insert (5, Left 'c') "(5, Left 'c')" $<br />
insert (4, Right ()) "(4, Right ())" $<br />
insert (5, Right ()) "This is the one!" $<br />
insert (5, Right ()) "This is the two!" $<br />
insert (6, Right ()) "(6, Right ())" $<br />
insert (5, Left 'a') "(5, Left 'a')" $<br />
empty<br />
main = putStrLn $ maybe "Couldn't find key!" id $ lookup (5, Right ()) myGMap<br />
</haskell><br />
<br />
=== Download the code ===<br />
<br />
If you want to play with this example without copying it off the wiki, just download the source code[http://darcs.haskell.org/testsuite/tests/ghc-regress/indexed-types/should_run/GMapAssoc.hs] for <hask>GMap</hask> from GHC's test suite.<br />
<br />
== Detailed definition of data families ==<br />
<br />
Data families appear in two flavours: (1) they can be defined on the toplevel or (2) they can appear inside type classes (in which case they are known as associated types). The former is the more general variant, as it lacks the requirement for the type-indices to coincide with the class parameters. However, the latter can lead to more clearly structured code and compiler warnings if some type instances were - possibly accidentally - omitted. In the following, we always discuss the general toplevel form first and then cover the additional constraints placed on associated types.<br />
<br />
=== Family declarations ===<br />
<br />
Indexed data families are introduced by a signature, such as <br />
<haskell><br />
data family GMap k :: * -> *<br />
</haskell><br />
The special <hask>family</hask> distinguishes family from standard data declarations. The result kind annotation is optional and, as usual, defaults to <hask>*</hask> if omitted. An example is<br />
<haskell><br />
data family Array e<br />
</haskell><br />
Named arguments can also be given explicit kind signatures if needed. Just as with [http://www.haskell.org/ghc/docs/latest/html/users_guide/gadt.html GADT declarations] named arguments are entirely optional, so that we can declare <hask>Array</hask> alternatively with<br />
<haskell><br />
data family Array :: * -> *<br />
</haskell><br />
<br />
==== Associated family declarations ====<br />
<br />
When a data family is declared as part of a type class, we drop the <hask>family</hask> keyword. The <hask>GMap</hask> declaration takes the following form<br />
<haskell><br />
class GMapKey k where<br />
data GMap k :: * -> *<br />
...<br />
</haskell><br />
In contrast to toplevel declarations, named arguments must be used for all type parameters that are to be used as type-indices. Moreover, the argument names must be class parameters. Each class parameter may only be used at most once per associated type, but some may be omitted and they may be in an order other than in the class head. In other words: '''the named type parameters of the data declaration must be a permutation of a subset of the class variables'''. <br />
<br />
Example is admissible:<br />
<haskell><br />
class C a b c where { data T c a :: * } -- OK<br />
class C a b c where { data T a a :: * } -- Bad: repeated variable<br />
class D a where { data T a x :: * } -- Bad: x is not a class variable<br />
class D a where { data T a :: * -> * } -- OK<br />
</haskell><br />
<br />
=== Instance declarations ===<br />
<br />
Instance declarations of data and newtype families are very similar to standard data and newtype declarations. The only two differences are that the keyword <hask>data</hask> or <hask>newtype</hask> is followed by <hask>instance</hask> and that some or all of the type arguments can be non-variable types, but may not contain forall types or type synonym families. However, data families are generally allowed in type parameters, and type synonyms are allowed as long as they are fully applied and expand to a type that is itself admissible - exactly as this is required for occurrences of type synonyms in class instance parameters. For example, the <hask>Either</hask> instance for <hask>GMap</hask> is<br />
<haskell><br />
data instance GMap (Either a b) v = GMapEither (GMap a v) (GMap b v)<br />
</haskell><br />
In this example, the declaration has only one variant. In general, it can be any number.<br />
<br />
Data and newtype instance declarations are only legit when an appropriate family declaration is in scope - just like class instances require the class declaration to be visible. Moreover, each instance declaration has to conform to the kind determined by its family declaration. This implies that the number of parameters of an instance declaration matches the arity determined by the kind of the family. Although all data families are declared with the <hask>data</hask> keyword, instances can be either <hask>data</hask> or <hask>newtype</hask>s, or a mix of both.<br />
<br />
Even if type families are defined as toplevel declarations, functions that perform different computations for different family instances still need to be defined as methods of type classes. In particular, the following is not possible:<br />
<haskell><br />
data family T a<br />
data instance T Int = A<br />
data instance T Char = B<br />
nonsense :: T a -> Int<br />
nonsense A = 1 -- WRONG: These two equations together...<br />
nonsense B = 2 -- ...will produce a type error.<br />
</haskell><br />
Given the functionality provided by GADTs (Generalised Algebraic Data Types), it might seem as if a definition, such as the above, should be feasible. However, type families - in contrast to GADTs - are ''open''; i.e., new instances can always be added, possibly in other modules. Supporting pattern matching across different data instances would require a form of extensible case construct.<br />
<br />
==== Associated type instances ====<br />
<br />
When an associated family instance is declared within a type class instance, we drop the <hask>instance</hask> keyword in the family instance. So, the <hask>Either</hask> instance for <hask>GMap</hask> becomes:<br />
<haskell><br />
instance (GMapKey a, GMapKey b) => GMapKey (Either a b) where<br />
data GMap (Either a b) v = GMapEither (GMap a v) (GMap b v)<br />
...<br />
</haskell><br />
The most important point about associated family instances is that the type indices corresponding to class parameters must be identical to the type given in the instance head; here this is the first argument of <hask>GMap</hask>, namely <hask>Either a b</hask>, which coincides with the only class parameter. Any parameters to the family constructor that do not correspond to class parameters, need to be variables in every instance; here this is the variable <hask>v</hask>.<br />
<br />
Instances for an associated family can only appear as part of instance declarations of the class in which the family was declared - just as with the equations of the methods of a class. Also in correspondence to how methods are handled, declarations of associated types can be omitted in class instances. If an associated family instance is omitted, the corresponding instance type is not inhabited; i.e., only diverging expressions, such as <hask>undefined</hask>, can assume the type.<br />
<br />
==== Scoping of class parameters ====<br />
<br />
In the case of multi-parameter type classes, the visibility of class parameters in the right-hand side of associated family instances depends ''solely'' on the parameters of the data family. As an example, consider the simple class declaration<br />
<haskell><br />
class C a b where<br />
data T a<br />
</haskell><br />
Only one of the two class parameters is a parameter to the data family. Hence, the following instance declaration is invalid:<br />
<haskell><br />
instance C [c] d where<br />
data T [c] = MkT (c, d) -- WRONG!! 'd' is not in scope<br />
</haskell><br />
Here, the right-hand side of the data instance mentions the type variable <hask>d</hask> that does not occur in its left-hand side. We cannot admit such data instances as they would compromise type safety.<br />
<br />
==== Type class instances of family instances ====<br />
<br />
Type class instances of instances of data families can be defined as usual, and in particular data instance declarations can have <hask>deriving</hask> clauses. For example, we can write<br />
<haskell><br />
data GMap () v = GMapUnit (Maybe v)<br />
deriving Show<br />
</haskell><br />
which implicitly defines an instance of the form<br />
<haskell><br />
instance Show v => Show (GMap () v) where ...<br />
</haskell><br />
<br />
Note that class instances are always for particular ''instances'' of a data family and never for an entire family as a whole. This is for essentially the same reasons that we cannot define a toplevel function that performs pattern matching on the data constructors of ''different'' instances of a single type family. It would require a form of extensible case construct.<br />
<br />
==== Overlap ====<br />
<br />
The instance declarations of a data family used in a single program may not overlap at all, independent of whether they are associated or not. In contrast to type class instances, this is not only a matter of consistency, but one of type safety.<br />
<br />
=== Import and export ===<br />
<br />
The association of data constructors with type families is more dynamic than that is the case with standard data and newtype declarations. In the standard case, the notation <hask>T(..)</hask> in an import or export list denotes the type constructor and all the data constructors introduced in its declaration. However, a family declaration never introduces any data constructors; instead, data constructors are introduced by family instances. As a result, which data constructors are associated with a type family depends on the currently visible instance declarations for that family. Consequently, an import or export item of the form <hask>T(..)</hask> denotes the family constructor and all currently visible data constructors - in the case of an export item, these may be either imported or defined in the current module. The treatment of import and export items that explicitly list data constructors, such as <hask>GMap(GMapEither)</hask>, is analogous.<br />
<br />
==== Associated families ====<br />
<br />
As expected, an import or export item of the form <hask>C(..)</hask> denotes all of the class' methods and associated types. However, when associated types are explicitly listed as subitems of a class, we need some new syntax, as uppercase identifiers as subitems are usually data constructors, not type constructors. To clarify that we denote types here, each associated type name needs to be prefixed by the keyword <hask>type</hask>. So for example, when explicitly listing the components of the <hask>GMapKey</hask> class, we write <hask>GMapKey(type GMap, empty, lookup, insert)</hask>.<br />
<br />
==== Examples ====<br />
<br />
Assuming our running <hask>GMapKey</hask> class example, let us look at some export lists and their meaning:<br />
<br />
* <hask>module GMap (GMapKey) where...</hask>: Exports just the class name.<br />
* <hask>module GMap (GMapKey(..)) where...</hask>: Exports the class, the associated type <hask>GMap</hask> and the member functions <hask>empty</hask>, <hask>lookup</hask>, and <hask>insert</hask>. None of the data constructors is exported.<br />
* <hask>module GMap (GMapKey(..), GMap(..)) where...</hask>: As before, but also exports all the data constructors <hask>GMapInt</hask>, <hask>GMapChar</hask>, <hask>GMapUnit</hask>, <hask>GMapPair</hask>, and <hask>GMapEither</hask>.<br />
* <hask>module GMap (GMapKey(empty, lookup, insert), GMap(..)) where...</hask>: As before.<br />
* <hask>module GMap (GMapKey, empty, lookup, insert, GMap(..)) where...</hask>: As before.<br />
<br />
Finally, you can write <hask>GMapKey(type GMap)</hask> to denote both the class <hask>GMapKey</hask> as well as its associated type <hask>GMap</hask>. However, you cannot write <hask>GMapKey(type GMap(..))</hask> &mdash; i.e., sub-component specifications cannot be nested. To specify <hask>GMap</hask>'s data constructors, you have to list it separately.<br />
<br />
==== Instances ====<br />
<br />
Family instances are implicitly exported, just like class instances. However, this applies only to the heads of instances, not to the data constructors an instance defines.<br />
<br />
== An associated type synonym example ==<br />
<br />
Type synonym families are an alternative to functional dependencies, which makes functional dependency examples well suited to introduce type synonym families. In fact, type families are a more functional way to express the same as functional dependencies (despite the name!), as they replace the relational notation of functional dependencies by an expression-oriented notation; i.e., functions on types are really represented by functions and not relations.<br />
<br />
=== The <hask>class</hask> declaration ===<br />
<br />
Here's an example from Mark Jones' seminal paper on functional dependencies:<br />
<haskell><br />
class Collects e ce | ce -> e where<br />
empty :: ce<br />
insert :: e -> ce -> ce<br />
member :: e -> ce -> Bool<br />
toList :: ce -> [e]<br />
</haskell><br />
<br />
With associated type synonyms we can write this as<br />
<haskell><br />
class Collects ce where<br />
type Elem ce<br />
empty :: ce<br />
insert :: Elem ce -> ce -> ce<br />
member :: Elem ce -> ce -> Bool<br />
toList :: ce -> [Elem ce]<br />
</haskell><br />
Instead of the multi-parameter type class, we use a single parameter class, and the parameter <hask>e</hask><br />
turned into an associated type synonym <hask>Elem ce</hask>.<br />
<br />
=== An <hask>instance</hask>===<br />
<br />
Instances change correspondingly. An instance of the two-parameter class<br />
<haskell><br />
instance Eq e => Collects e [e] where<br />
empty = []<br />
insert e l = (e:l)<br />
member e [] = False<br />
member e (x:xs) <br />
| e == x = True<br />
| otherwise = member e xs<br />
toList l = l<br />
</haskell><br />
becomes an instance of a single-parameter class, where the dependent type parameter turns into an associated type instance declaration:<br />
<haskell><br />
instance Eq e => Collects [e] where<br />
type Elem [e] = e<br />
empty = []<br />
insert e l = (e:l)<br />
member e [] = False<br />
member e (x:xs) <br />
| e == x = True<br />
| otherwise = member e xs<br />
toList l = l<br />
</haskell><br />
<br />
=== Using generic collections ===<br />
<br />
With Functional Dependencies the code would be:<br />
<haskell><br />
sumCollects :: (Collects e c1, Collects e c2) => c1 -> c2 -> c2<br />
sumCollects c1 c2 = foldr insert c2 (toList c1)<br />
</haskell><br />
<br />
In contrast, with associated type synonyms, we get:<br />
<haskell><br />
sumCollects :: (Collects c1, Collects c2, Elem c1 ~ Elem c2) => c1 -> c2 -> c2<br />
sumCollects c1 c2 = foldr insert c2 (toList c1)<br />
</haskell><br />
<br />
== Detailed definition of type synonym families ==<br />
<br />
Type families appear in two flavours: (1) they can be defined on the toplevel or (2) they can appear inside type classes (in which case they are known as associated type synonyms). The former is the more general variant, as it lacks the requirement for the type-indices to coincide with the class parameters. However, the latter can lead to more clearly structured code and compiler warnings if some type instances were - possibly accidentally - omitted. In the following, we always discuss the general toplevel form first and then cover the additional constraints placed on associated types.<br />
<br />
=== Family declarations ===<br />
<br />
Indexed type families are introduced by a signature, such as <br />
<haskell><br />
type family Elem c :: *<br />
</haskell><br />
The special <hask>family</hask> distinguishes family from standard type declarations. The result kind annotation is optional and, as usual, defaults to <hask>*</hask> if omitted. An example is<br />
<haskell><br />
type family Elem c<br />
</haskell><br />
Parameters can also be given explicit kind signatures if needed. We call the number of parameters in a type family declaration, the family's arity, and all applications of a type family must be fully saturated w.r.t. to that arity. This requirement is unlike ordinary type synonyms and it implies that the kind of a type family is not sufficient to determine a family's arity, and hence in general, also insufficient to determine whether a type family application is well formed. As an example, consider the following declaration:<br />
<haskell><br />
type family F a b :: * -> * -- F's arity is 2, <br />
-- although its overall kind is * -> * -> * -> *<br />
</haskell><br />
Given this declaration the following are examples of well-formed and malformed types:<br />
<haskell><br />
F Char [Int] -- OK! Kind: * -> *<br />
F Char [Int] Bool -- OK! Kind: *<br />
F IO Bool -- WRONG: kind mismatch in the first argument<br />
F Bool -- WRONG: unsaturated application<br />
</haskell><br />
<br />
A top-level type family can be declared as open or closed. (Associated type<br />
families are always open.) A closed type family has all of its equations<br />
defined in one place and cannot be extended, whereas an open family can have<br />
instances spread across modules. The advantage of a closed family is that<br />
its equations are tried in order, similar to a term-level function definition:<br />
<haskell><br />
type family G a where<br />
G Int = Bool<br />
G a = Char<br />
</haskell><br />
With this definition, the type <hask>G Int</hask> becomes <hask>Bool</hask><br />
and, say, <hask>G Double</hask> becomes <hask>Char</hask>. See also [http://ghc.haskell.org/trac/ghc/wiki/NewAxioms here] for more information about closed type families.<br />
<br />
==== Associated family declarations ====<br />
<br />
When a type family is declared as part of a type class, we drop the <hask>family</hask> special. The <hask>Elem</hask> declaration takes the following form<br />
<haskell><br />
class Collects ce where<br />
type Elem ce :: *<br />
...<br />
</haskell><br />
Exactly as in the case of an associated data declaration, '''the named type parameters must be a permutation of a subset of the class parameters'''. Examples<br />
<haskell><br />
class C a b c where { type T c a :: * } -- OK<br />
class D a where { type T a x :: * } -- No: x is not a class parameter<br />
class D a where { type T a :: * -> * } -- OK<br />
</haskell><br />
<br />
=== Type instance declarations ===<br />
<br />
Instance declarations of open type families are very similar to standard type synonym declarations. The only two differences are that the keyword <hask>type</hask> is followed by <hask>instance</hask> and that some or all of the type arguments can be non-variable types, but may not contain forall types or type synonym families. However, data families are generally allowed, and type synonyms are allowed as long as they are fully applied and expand to a type that is admissible - these are the exact same requirements as for data instances. For example, the <hask>[e]</hask> instance for <hask>Elem</hask> is<br />
<haskell><br />
type instance Elem [e] = e<br />
</haskell><br />
<br />
A type family instance declaration must satisfy the following rules:<br />
* An appropriate family declaration is in scope - just like class instances require the class declaration to be visible. <br />
* The instance declaration conforms to the kind determined by its family declaration<br />
* The number of type parameters in an instance declaration matches the number of type parameters in the family declaration.<br />
* The right-hand side of a type instance must be a monotype (i.e., it may not include foralls) and after the expansion of all saturated vanilla type synonyms, no synonyms, except family synonyms may remain.<br />
<br />
Here are some examples of admissible and illegal type instances and closed families:<br />
<haskell><br />
type family F a :: *<br />
type instance F [Int] = Int -- OK!<br />
type instance F String = Char -- OK!<br />
type instance F (F a) = a -- WRONG: type parameter mentions a type family<br />
type instance F (forall a. (a, b)) = b -- WRONG: a forall type appears in a type parameter<br />
type instance F Float = forall a.a -- WRONG: right-hand side may not be a forall type<br />
<br />
type family F2 a where -- OK!<br />
F2 (Maybe Int) = Int<br />
F2 (Maybe Bool) = Bool<br />
F2 (Maybe a) = String<br />
<br />
type family G a b :: * -> *<br />
type instance G Int = (,) -- WRONG: must be two type parameters<br />
type instance G Int Char Float = Double -- WRONG: must be two type parameters<br />
</haskell><br />
<br />
==== Closed family simplification ====<br />
<br />
Included in ghc starting 7.8.1.<br />
<br />
When dealing with closed families, simplifying the type is harder than just finding a left-hand side that matches and replacing that with a right-hand side. GHC will select an equation to use in a given type family application (the "target") if and only if the following 2 conditions hold:<br />
<br />
# There is a substitution from the variables in the equation's LHS that makes the left-hand side of the branch coincide with the target.<br />
# For each previous equation in the family: either the LHS of that equation is ''apart'' from the type family application, '''or''' the equation is ''compatible'' with the chosen equation.<br />
<br />
Now, we define ''apart'' and ''compatible'':<br />
# Two types are ''apart'' when one cannot simplify to the other, even after arbitrary type-family simplifications<br />
# Two equations are ''compatible'' if, either, their LHSs are apart or their LHSs unify and their RHSs are the same under the substitution induced by the unification.<br />
<br />
Some examples are in order:<br />
<haskell><br />
type family F a where<br />
F Int = Bool<br />
F Bool = Char<br />
F a = Bool<br />
<br />
type family And (a :: Bool) (b :: Bool) :: Bool where<br />
And False c = False<br />
And True d = d<br />
And e False = False<br />
And f True = f<br />
And g g = g<br />
</haskell><br />
<br />
In <hask>F</hask>, all pairs of equations are compatible except the second and third. The first two are compatible because their LHSs are apart. The first and third are compatible because the unifying substitution leads the RHSs to be the same. But, the second and third are not compatible because neither of these conditions holds. As a result, GHC will not use the third equation to simplify a target unless that target is apart from <hask>Bool</hask>.<br />
<br />
In <hask>And</hask>, ''every'' pair of equations is compatible, meaning GHC never has to make the extra apartness check during simplification.<br />
<br />
Why do all of this? It's a matter of type safety. Consider this example:<br />
<br />
<haskell><br />
type family J a b where<br />
J a a = Int<br />
J a b = Bool<br />
</haskell><br />
<br />
Say GHC selected the second branch just because the first doesn't apply at the moment, because two type variables are distinct. The problem is that those variables might later be instantiated at the same value, and then the first branch would have applied. You can convince this sort of inconsistency to produce <hask>unsafeCoerce</hask>.<br />
<br />
It gets worse. GHC has no internal notion of inequality, so it can't use previous, failed term-level GADT pattern matches to refine its type assumptions. For example:<br />
<br />
<haskell><br />
data G :: * -> * where<br />
GInt :: G Int<br />
GBool :: G Bool<br />
<br />
type family Foo (a :: *) :: * where<br />
Foo Int = Char<br />
Foo a = Double<br />
<br />
bar :: G a -> Foo a<br />
bar GInt = 'x'<br />
bar _ = 3.14<br />
</haskell><br />
<br />
The last line will fail to typecheck, because GHC doesn't know that the type variable <hask>a</hask> can't be <hask>Int</hask> here, even though it's obvious. The only general way to fix this is to have inequality evidence introduced into GHC, and that's a big deal and we don't know if we have the motivation for such a change yet.<br />
<br />
==== Associated type instances ====<br />
<br />
When an associated family instance is declared within a type class instance, we drop the <hask>instance</hask> keyword in the family instance. So, the <hask>[e]</hask> instance for <hask>Elem</hask> becomes:<br />
<haskell><br />
instance (Eq (Elem [e])) => Collects ([e]) where<br />
type Elem [e] = e<br />
...<br />
</haskell><br />
The most important point about associated family instances is that the type indexes corresponding to class parameters must be identical to the type given in the instance head; here this is <hask>[e]</hask>, which coincides with the only class parameter.<br />
<br />
Instances for an associated family can only appear as part of instance declarations of the class in which the family was declared - just as with the equations of the methods of a class. Also in correspondence to how methods are handled, declarations of associated types can be omitted in class instances. If an associated family instance is omitted, the corresponding instance type is not inhabited; i.e., only diverging expressions, such as <hask>undefined</hask>, can assume the type.<br />
<br />
==== Overlap ====<br />
<br />
The instance declarations of an open type family used in a single program must be compatible, in the form defined above. This condition is independent of whether the type family is associated or not, and it is not only a matter of consistency, but one of type safety. <br />
<br />
Here are two examples to illustrate the condition under which overlap is permitted.<br />
<haskell><br />
type instance F (a, Int) = [a]<br />
type instance F (Int, b) = [b] -- overlap permitted<br />
<br />
type instance G (a, Int) = [a]<br />
type instance G (Char, a) = [a] -- ILLEGAL overlap, as [Char] /= [Int]<br />
</haskell><br />
<br />
==== Decidability ====<br />
<br />
In order to guarantee that type inference in the presence of type families is decidable, we need to place a number of additional restrictions on the formation of type instance declarations (c.f., Definition 5 (Relaxed Conditions) of [http://www.cse.unsw.edu.au/~chak/papers/SPCS08.html Type Checking with Open Type Functions]). Instance declarations have the general form<br />
<haskell><br />
type instance F t1 .. tn = t<br />
</haskell><br />
where we require that for every type family application <hask>(G s1 .. sm)</hask> in <hask>t</hask>, <br />
# <hask>s1 .. sm</hask> do not contain any type family constructors,<br />
# the total number of symbols (data type constructors and type variables) in <hask>s1 .. sm</hask> is strictly smaller than in <hask>t1 .. tn</hask>, and<br />
# for every type variable <hask>a</hask>, <hask>a</hask> occurs in <hask>s1 .. sm</hask> at most as often as in <hask>t1 .. tn</hask>.<br />
These restrictions are easily verified and ensure termination of type inference. However, they are not sufficient to guarantee completeness of type inference in the presence of, so called, ''loopy equalities'', such as <hask>a ~ [F a]</hask>, where a recursive occurrence of a type variable is underneath a family application and data constructor application - see the above mentioned paper for details. <br />
<br />
If the option <tt>-XUndecidableInstances</tt> is passed to the compiler, the above restrictions are not enforced and it is on the programmer to ensure termination of the normalisation of type families during type inference.<br />
<br />
=== Equality constraints ===<br />
<br />
Type context can include equality constraints of the form <hask>t1 ~ t2</hask>, which denote that the types <hask>t1</hask> and <hask>t2</hask> need to be the same. In the presence of type families, whether two types are equal cannot generally be decided locally. Hence, the contexts of function signatures may include equality constraints, as in the following example:<br />
<haskell><br />
sumCollects :: (Collects c1, Collects c2, Elem c1 ~ Elem c2) => c1 -> c2 -> c2<br />
</haskell><br />
where we require that the element type of <hask>c1</hask> and <hask>c2</hask> are the same. In general, the types <hask>t1</hask> and <hask>t2</hask> of an equality constraint may be arbitrary monotypes; i.e., they may not contain any quantifiers, independent of whether higher-rank types are otherwise enabled.<br />
<br />
Equality constraints can also appear in class and instance contexts. The former enable a simple translation of programs using functional dependencies into programs using family synonyms instead. The general idea is to rewrite a class declaration of the form<br />
<haskell><br />
class C a b | a -> b<br />
</haskell><br />
to<br />
<haskell><br />
class (F a ~ b) => C a b where<br />
type F a<br />
</haskell><br />
That is, we represent every functional dependency (FD) <hask>a1 .. an -> b</hask> by an FD type family <hask>F a1 .. an</hask> and a superclass context equality <hask>F a1 .. an ~ b</hask>, essentially giving a name to the functional dependency. In class instances, we define the type instances of FD families in accordance with the class head. Method signatures are not affected by that process.<br />
<br />
== Frequently asked questions ==<br />
<br />
=== Comparing type families and functional dependencies ===<br />
<br />
Functional dependencies cover some of the same territory as type families. How do the two compare?<br />
There are some articles about this question:<br />
<br />
* Experiences in converting functional dependencies to type families: "[[Functional dependencies vs. type families]]"<br />
* [https://ghc.haskell.org/trac/ghc/wiki/TFvsFD GHC trac] on a comparison of functional dependencies and type families<br />
<br />
=== Injectivity, type inference, and ambiguity ===<br />
<br />
A common problem is this<br />
<haskell><br />
type family F a<br />
<br />
f :: F a -> F a<br />
f = undefined<br />
<br />
g :: F Int -> F Int<br />
g x = f x<br />
</haskell><br />
The compiler complains about the definition of <tt>g</tt> saying<br />
<code><br />
Couldn't match expected type `F Int' against inferred type `F a1'<br />
</code><br />
In type-checking <tt>g</tt>'s right hand side GHC discovers (by instantiating <tt>f</tt>'s type with a fresh type variable) that it has type <tt>F a1 -> F a1</tt> for some as-yet-unknown type <tt>a1</tt>. Now it tries to make the inferred type match <tt>g</tt>'s type signature. Well, you say, just make <tt>a1</tt> equal to <tt>Int</tt> and you are done. True, but what if there were these instances<br />
<haskell><br />
type instance F Int = Bool<br />
type instance F Char = Bool<br />
</haskell><br />
Then making <tt>a1</tt> equal to <tt>Char</tt> would ''also'' make the two types equal. Because there is (potentially) more than one choice, the program is rejected.<br />
<br />
However (and confusingly) if you omit the type signature on <tt>g</tt> altogether, thus<br />
<haskell><br />
f :: F a -> F a<br />
f = undefined<br />
<br />
g x = f x<br />
</haskell><br />
GHC will happily infer the type <tt>g :: F a -> F a</tt>. But you can't ''write'' that type signature or, indeed, the more specific one above. (Arguably this behaviour, where GHC ''infers'' a type it can't ''check'', is very confusing. I suppose we could make GHC reject both programs, with and without type signatures.)<br />
<br />
'''What is the problem?''' The nub of the issue is this: knowing that <tt>F t1</tt>=<tt>F t2</tt> does ''not'' imply that <tt>t1</tt> = <tt>t2</tt>.<br />
The difficulty is that the type function <tt>F</tt> need not be ''injective''; it can map two distinct types to the same type. For an injective type constructor like <tt>Maybe</tt>, if we know that <tt>Maybe t1</tt> = <tt>Maybe t2</tt>, then we know that <tt>t1</tt> = <tt>t2</tt>. But not so for non-injective type functions.<br />
<br />
The problem starts with <tt>f</tt>. Its type is ''ambiguous''; even if I know the argument and result types for <tt>f</tt>, I cannot use that to find the type at which <tt>a</tt> should be instantiated. (So arguably, <tt>f</tt> should be rejected as having an ambiguous type, and probably will be in future.) The situation is well known in type classes: <br />
<haskell><br />
bad :: (Read a, Show a) => String -> String<br />
bad x = show (read x)<br />
</haskell><br />
At a call of <tt>bad</tt> one cannot tell at what type <tt>a</tt> should be instantiated.<br />
<br />
The only solution is to avoid ambiguous types. In the type signature of a function, <br />
* Ensure that every type variable occurs in the part after the "<tt>=></tt>"<br />
* Ensure that every type variable appears at least once outside a type function call.<br />
Alternatively, you can use data families, which create new types and are therefore injective. The following code works:<br />
<br />
<haskell>data family F a<br />
<br />
f :: F a -> F a<br />
f = undefined<br />
<br />
g :: F Int -> F Int<br />
g x = f x</haskell><br />
<br />
== References ==<br />
<br />
* [http://www.cse.unsw.edu.au/~chak/papers/CKPM05.html Associated Types with Class.] Manuel M. T. Chakravarty, Gabriele Keller, Simon Peyton Jones, and Simon Marlow. In ''Proceedings of The 32nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'05)'', pages 1-13, ACM Press, 2005.<br />
* [http://www.cse.unsw.edu.au/~chak/papers/CKP05.html Associated Type Synonyms.] Manuel M. T. Chakravarty, Gabriele Keller, and Simon Peyton Jones. In ''Proceedings of The Tenth ACM SIGPLAN International Conference on Functional Programming'', ACM Press, pages 241-253, 2005.<br />
* [http://www.cse.unsw.edu.au/~chak/papers/SCPD07.html System F with Type Equality Coercions.] Martin Sulzmann, Manuel M. T. Chakravarty, Simon Peyton Jones, and Kevin Donnelly. In ''Proceedings of The Third ACM SIGPLAN Workshop on Types in Language Design and Implementation'', ACM Press, 2007.<br />
* [http://www.cse.unsw.edu.au/~chak/papers/SPCS08.html Type Checking With Open Type Functions.] Tom Schrijvers, Simon Peyton-Jones, Manuel M. T. Chakravarty, Martin Sulzmann. In ''Proceedings of The 13th ACM SIGPLAN International Conference on Functional Programming'', ACM Press, pages 51-62, 2008.<br />
* [[Simonpj/Talk:FunWithTypeFuns | Fun with Type Functions]] Oleg Kiselyov, Simon Peyton Jones, Chung-chieh Shan (the source for this paper can be found at http://patch-tag.com/r/schoenfinkel/typefunctions/wiki ) <br />
<br />
[[Category:Type-level programming]]<br />
[[Category:Language extensions]]<br />
[[Category:GHC|Indexed types]]</div>Sciolizerhttps://wiki.haskell.org/index.php?title=Video_presentations&diff=60983Video presentations2016-08-07T07:05:21Z<p>Sciolizer: Replaced dead link of Transactional Memory for Concurrent Programming</p>
<hr />
<div>[[Category:Tutorials]]<br />
Collected videos of Haskell tutorials and conference presentations, sorted by topic.<br />
<br />
For more recent videos, check:<br />
<br />
* '''[http://vimeo.com/channels/haskell The Haskell Vimeo Channel]'''<br />
* '''[http://vimeo.com/channels/galois The Galois Tech Talk Vimeo Channel]'''<br />
* '''[http://channel9.msdn.com/tags/Haskell/ Haskell videos on MSDN Channel 9]'''<br />
<br />
Maintained by the community.<br />
<br />
== Introductions to Haskell ==<br />
<br />
:<del>[http://blip.tv/file/324976 Part 1] ([http://blip.tv/file/get/OSCON-OSCON2007SimonPeytonJonesATasteOfHaskellPartI455.flv Download])</del> ([https://www.youtube.com/watch?v=jLj1QV11o9g On YouTube])<br />
:<del>[http://blip.tv/file/325646 Part 2] ([http://blip.tv/file/get/OSCON-OSCON2007SimonPeytonJonesATasteOfHaskellPartII749.flv Download])</del> ([https://www.youtube.com/watch?v=IqXTUbdLig0 On YouTube])<br />
:[http://conferences.oreillynet.com/presentations/os2007/os_peytonjones.pdf Slides]<br />
:Simon Peyton-Jones, OSCON, July 2007.<br />
<blockquote><br />
Haskell is the world's leading purely functional programming language<br />
that offers a radical and elegant attack on the whole business of<br />
writing programs. In the last two or three years there has been an<br />
explosion of interest in Haskell, and it is now being used for a<br />
bewildering variety of applications. In this tutorial, I will try to<br />
show you why programming in Haskell is such fun, and how it makes you<br />
think about programming in a new way.<br />
</blockquote><br />
<br />
[http://channel9.msdn.com/shows/Going+Deep/Lecture-Series-Erik-Meijer-Functional-Programming-Fundamentals-Chapter-1/ Functional Programming Fundamentals - Erik Meijer]<br />
:Erik's 13 part lecture series on Haskell, using [http://www.amazon.com/Programming-Haskell-Graham-Hutton/dp/0521692695/ref=sr_1_1?ie=UTF8&qid=1287780326&sr=8-1 Programming in Haskell] by Graham Hutton.<br />
<br />
[http://channel9.msdn.com/showpost.aspx?postid=326762 Programming language nirvana]<br />
:Simon Peyton-Jones, Eric Meijer, MSR, July 2007.<br />
<br />
;[http://yow.eventer.com/events/1004/talks/1054 Escape From the Ivory Tower: The Haskell Journey, From 1990 to 2011]<br />
:Simon Peyton-Jones, Yow, December 2011<br />
<br />
;[http://ulf.wiger.net/weblog/2008/02/29/peyton-jones-taming-effects-the-next-big-challenge/ Taming Effects - The Next Big Challenge]<br />
:Simon Peyton-Jones at Ericsson, February 2008.<br />
<br />
;[http://video.google.com/videoplay?docid=-4167170843018186532 Faith, Evolution, and Programming Languages]<br />
:Phil Wadler, April 2007. Slides are [http://homepages.inf.ed.ac.uk/wadler/topics/gj.html#oopsla here]<br />
<br />
;[http://port25.technet.com/archive/2007/09/26/haskell-in-the-hallway-sam-interviews-simon-peyton-jones.aspx Haskell in the Hallway]<br />
: An interview with SPJ at OSCON, Sep 2007.<br />
<br />
;[http://video.s-inf.de/#FP.2005-SS-Giesl.(COt).HD_Videoaufzeichnung Lecture Functional Programming]<br />
: A computer science lecture at RWTH University Aachen (Germany) dealing with functional programming and haskell (including theoretical background)<br />
<br />
;[http://www.dotnetrocks.com/default.aspx?ShowNum=310 Simon Peyton Jones on Functional Programming and Haskell (Audio)]<br />
:Simon explains laziness, purity, parallelism, side effects, monads, software transactional memory<br />
<br />
;[http://ulf.wiger.net/weblog/2008/02/29/john-launchbury-high-assurance-software/ High-Assurance Software] <br />
:John Launchbury at Ericsson, 21 February 2008.<br />
<br />
== Haskell Implementors Workshop 2009,2010,2011,2012 ==<br />
[[HaskellImplementorsWorkshop]]<br />
<br />
== Haskell Symposium 2008 ==<br />
<br />
[[/Haskell Symposium 2008]] videos. <br />
<br />
== ICFP 2007 and Workshops ==<br />
<br />
; [http://video.google.com/videoplay?docid=-1518197558546337776 The Reduceron: Widening the von Neumann Bottleneck for Graph Reduction using an FPGA.]<br />
:The Reduceron: Widening the von Neumann Bottleneck for Graph Reduction using an FPGA. A research talk given at IFL'2007 in Freiburg. Work by Matthew Naylor and Colin Runciman of the University of York. <br />
<br />
; [http://www.ludd.ltu.se/~pj/icfp2007/ICFP2007.html Selected videos from IFL 2007 and ICFP 2007.]<br />
<br />
; [http://www.ludd.ltu.se/~pj/hw2007/HaskellWorkshop.html All talks from Haskell Workshop 2007.]<br />
<br />
== Advanced topics in functional programming ==<br />
<br />
;[http://video.google.com/videoplay?docid=-4991530385753299192 Type-driven testing in Haskell]<br />
:Simon Peyton Jones talks about QuickCheck and SmallCheck<br />
<br />
;[http://www.youtube.com/user/TheCatsters The Catsters on YouTube]<br />
:Various interesting lectures on category theory, including monads, adjunctions, limits, and a variety of other topics.<br />
<br />
;[http://iba-cg.de/haskell.html Generic Programming in Haskell].<br />
:Johan Jeuring, July 2007.<br />
<br />
;[http://video.google.com/videoplay?docid=-4851250372422374791 Parametric Polymorphism and the Girard-Reynolds Isomorphism]<br />
:Phil Gossett, April 2007.<br />
:(link broken as of 2012-02-07)<br />
<br />
;[http://channel9.msdn.com/ShowPost.aspx?PostID=358968#358968 Don't fear the monads]<br />
:Brian Beckman introducing monads<br />
<br />
== Concurrency and parallelism ==<br />
<br />
;[http://www.bayfp.org/blog/?p=25 Concurrent and multicore programming in Haskell] [http://blip.tv/file/913860 (alternate link, just video)]<br />
:[http://www.serpentine.com/blog/ Bryan O’Sullivan] at [http://bayfp.org Bay Area Functional Programmers], 8 May 2008<br />
<br />
;[http://ulf.wiger.net/weblog/2008/02/29/satnam-singh-declarative-programming-techniques-for-many-core-architectures/ Declarative Programming Techniques for Many-Core Architectures] <br />
:Satnam Singh at Ericsson, 21 February 2008<br />
<br />
;[https://www.youtube.com/watch?v=4caDLTfSa2Q Transactional Memory for Concurrent Programming]<br />
:Simon Peyton-Jones, OSCON, July 2007.<br />
<br />
;[http://channel9.msdn.com/Showpost.aspx?postid=231495 Programming in the Age of Concurrency: Software Transactional Memory]<br />
:Simon Peyton-Jones and Tim Harris, September 2006.<br />
<br />
;[http://www.londonhug.net/2007/09/25/nested-data-parallelism-video-returns/ Nested Data Parallelism in Haskell]<br />
:Simon Peyton-Jones, [http://www.londonhug.net/ London HUG], May 2007.<br />
:[http://research.microsoft.com/~simonpj/papers/ndp/NdpSlides.pdf Slides] (pdf)<br />
<br />
== The Web ==<br />
<br />
;[http://www.bayfp.org/blog/2007/10/16/alex-jacobson-on-happs-videos-slides/ HAppS]<br />
:Alex Jacobson, [http://www.bayfp.org/blog Bay Area FPers], Oct 2007.<br />
<br />
== Games ==<br />
<br />
;[http://www.londonhug.net/2007/09/24/better-video-for-games-in-haskell/ Games in Haskell]<br />
:2007 meeting of the London Haskell User Group. Matthew Sackman and Tristan Allwood of Imperial College talk about building 3D games in Haskell.<br />
<br />
;[http://uk.youtube.com/watch?v=uziCn2SBbxs Data parallel physics engine]<br />
:2008, Hpysics' visulization code now performs double buffering<br />
<br />
;[http://uk.youtube.com/watch?v=mwge13bX9W8 Yampa Space Invaders]<br />
:Space Invaders, using functional reactive programming.<br />
<br />
;[http://uk.youtube.com/watch?v=zqFgQiPKtOI Monadius]<br />
:A 2D space game<br />
<br />
;[http://uk.youtube.com/watch?v=gVLFGQGRsDw Super 'Nario' Bros]<br />
:Super 'Nario' Brothers in Haskell<br />
<br />
;[http://uk.youtube.com/watch?v=0jYdu2u8gAU Frag]<br />
: Frag<br />
<br />
== The ICFP contest ==<br />
<br />
;[http://video.google.com/videoplay?docid=6419094369756184531 2006 ICFP contest results]<br />
:ICFP, 2006<br />
<br />
;[http://www.ludd.ltu.se/~pj/icfp2007/ICFP%20contest%202007.mov 2007 ICFP contest results]<br />
:ICFP, 2007<br />
<br />
== Livecoding Haskell ==<br />
<br />
;[http://www.youtube.com/watch?v=045422s6xik Data Driven Programming in Haskell]<br />
: Uses the unscripted, “real-world” toy project of performing character recognition on an image that many other OCR tools fail on due to very low resolution.<br />
<br />
;[http://www.youtube.com/user/entirelysubjective?feature=watch Coding Uncut]<br />
: A channel of unscripted, unedited and uncut videos of solving problems using Haskell.<br />
<br />
;[http://haskelllive.com/ Haskell Live]<br />
: Basic and intermediate Haskell concepts taught while tackling problems.<br />
<br />
;[https://www.youtube.com/watch?v=zZ_nI9E9g0I&list=PLxj9UAX4Em-Ij4TKwKvo-SLp-Zbv-hB4B&index=1 Haskell from Scratch]<br />
: Implementation of djb's redo (a GNU Make replacement) from scratch.<br />
<br />
[[Category:Music]]<br />
<br />
;[http://video.google.de/videoplay?docid=-6594267962912965757&q=hal2+july+2007&total=7&start=0&num=50&so=0&type=search&plindex=3 Music and Sound generation]<br />
:Henning Thielemann July 2007 in Leipzig about Music and Sound using SuperCollider, CSound, MIDI and pure Haskell (German)<br />
<br />
;[http://youtube.com/watch?v=xaoLbKWMwoU Haskell music]<br />
:[http://doc.gold.ac.uk/~ma503am/ Yaxu], 2006.<br />
<br />
;[http://youtube.com/watch?v=eLS6GHXWMpA Hacking Haskell music]<br />
:More of Yaxu live coding music and Haskell, 2006.<br />
<br />
;[http://doc.gold.ac.uk/~ma503am/alex/asciirave ASCII Rave in Haskell]<br />
:Yaxu, using words to control the articulation of a physical modelling synthesiser based on the elegant Karplus-Strong algorithm<br />
<br />
== GHC Hackathon presentations ==<br />
<br />
;[http://hackage.haskell.org/trac/ghc/wiki/AboutVideos GHC commentary]<br />
:Simon Peyton Jones and Simon Marlow, 2006.<br />
<br />
== Commercial users ==<br />
<br />
;[http://www.londonhug.net/2008/08/11/video-paradise-a-dsel-for-derivatives-pricing/ Paradise]<br />
:An EDSL in Haskell developed by Credit Suisse for Derivatives Pricing<br />
<br />
== Haskell applications ==<br />
<br />
;[http://www.youtube.com/watch?v=oYdkrOMhFWU Emacs Flymake]<br />
:Daisuke IKEGAMI, a demo of editing Haskell program on Emacs with on-the-fly syntax and type checking using flymake-mode (see also [http://www.emacswiki.org/cgi-bin/emacs/FlymakeHaskell EmacsWiki:FlymakeHaskell] for details), 11 November 2007<br />
<br />
;[http://video.google.de/videosearch?q=hal2+july+2007 HAL2]<br />
:HAL2 meeting in July 2007 in Leipzig, presenting talks about Generic Programming (English), Eclipse for Haskell (German), Grapefruit GUI (German) and Music+Sound generation (German)<br />
<br />
;[http://ftp.belnet.be/mirrors/FOSDEM/2006/FOSDEM2006-darcs.avi GADTs for darcs]<br />
:David Roundy, FOSDEM, 2006<br />
<br />
;[http://www.londonhug.net/2008/02/02/video-darcs-and-gadts/ Darcs and Generalised Algebraic Data Types]<br />
:Ganesh Sittampalamhs talk on Darcs and GADTs<br />
<br />
;[http://www.uwtv.org/programs/displayevent.aspx?rID=2124&fID=368 Functional Image Synthesis]<br />
:Conal Elliott, talk at University of Washington, November 2000<br />
<br />
;[http://www.youtube.com/watch?v=faJ8N0giqzw Tangible Functional Programming]<br />
:Conal Eliott's Google Tech Talk<br />
<br />
;[http://ulf.wiger.net/weblog/2008/02/29/john-hughes-testing-with-quickcheck/ Testing with QuickCheck]<br />
:John Hughes at Ericsson, 21 February 2008<br />
<br />
;[http://ulf.wiger.net/weblog/2008/02/29/simon-peyton-jones-composing-contracts-an-adventure-in-financial-engineering/ Composing Contracts - An Adventure in Financial Engineering] <br />
:Simon Peyton Jones at Ericsson, 21 February 2008.<br />
<br />
;[http://www.ludd.ltu.se/~pj/hw2007/xmonad.mov xmonad]<br />
: Don Stewart at the Haskell Workshop, 2007.<br />
<br />
;[http://www.youtube.com/watch?v=yHd0u6zuWdw Coconut: COde CONstructing User Tool]<br />
:Haskell DSL to produce high performance SIMD-Parallel code<br />
<br />
;[http://covector.blogspot.com/2007/10/functional-augmented-reality.html Augmented reality using Haskell computer vision]<br />
:Functional augmented reality, Alberto Ruiz<br />
<br />
;[http://www.vimeo.com/1983774 Understanding HaskellDB trailer]<br />
<br />
;[https://www.youtube.com/watch?v=FEFETKhhq8w&list=PLxj9UAX4Em-Lz5btngxMVZxf_B44GETVz Haskell Deconstructed]<br />
:Examining the source code to Pandoc, xmonad, and other Haskell applications<br />
<br />
== Interviews ==<br />
<br />
;[http://www.haskellcast.com/ The Haskell Cast]<br />
:A monthly podcast with interviews from the Haskell community<br />
<br />
== Other ==<br />
<br />
;[http://www.youtube.com/watch?v=faJ8N0giqzw Tangible Functional Programming: a modern marriage of usability and composability]<br />
:Conal Elliott. Google TechTalk, November 2007</div>Sciolizerhttps://wiki.haskell.org/index.php?title=BayHac2011&diff=38708BayHac20112011-02-11T17:18:00Z<p>Sciolizer: /* Attendees */</p>
<hr />
<div>[[Image:Haskell-and-dojo.png]]<br />
<br />
<span style="color:#930;font-weight:bold;">Haskell Project Hackathon</span><br />
<br />
''Friday, February 11th, 2pm – Sunday, February 13th 2pm''<br />
<br />
Come join a group of Haskell hackers. Bring your own projects, or work on ours: It is more fun to do it in a group!<br />
<br />
<br />
<span style="color:#930;font-weight:bold;">Learn Haskell Workshop </span><br />
<br />
''Saturday, February 12th, 10am – 4pm''<br />
<br />
Come learn Haskell! No prior Haskell experience needed. Bring your laptop and a willingness to have your brain stretched in enjoyable ways. We’ll be do some web programming in Haskell.<br />
----<br />
{|<br />
|When:<br />
|Feb 11-13, 2011<br />
|-<br />
|Where:<br />
|[http://www.hackerdojo.com/ Hacker Dojo], 140A South Whisman Road, Mountain View, CA ([http://maps.google.com/maps/place?cid=2122486601784397611&q=hacker+dojo&gl=us Google Map])<br />
|-<br />
|Cost:<br />
|Free<br />
|-<br />
|Sign up:<br />
|[https://spreadsheets.google.com/viewform?formkey=dEc5cW1fa3hjQ3JheVF5dHAwdTk0eGc6MQ sign-up form]<br />
|-<br />
|News and Discussion:<br />
|[http://groups.google.com/group/bayhac BayHac Google Group]<br />
|}<br />
<br />
----<br />
<br />
''As of Feb 1st, there are over 60 people signed up!''<br />
<br />
== Attendees == <br />
<br />
If you're attending, please put your name up!<br />
<br />
* [http://www.serpentine.com/blog Bryan O'Sullivan] - organizer<br />
* [http://www.ozonehouse.com/mark/ Mark Lentczner] - organizer<br />
* [http://hacks.yi.org/~as/ Austin Seipp]<br />
* [http://blog.johantibell.com/ Johan Tibell]<br />
* [http://blog.gregweber.info/ Greg Weber]<br />
* [http://conal.net/ Conal Elliott]<br />
* Joshua Ball<br />
<br />
== Projects == <br />
<br />
If you're going to attend and plan working on a project, please put it up here so other interested hackers can see what sorts of projects are afoot.<br />
<br />
=== Compiler plugins for GHC ===<br />
<br />
I plan on helping integrate and maintain compiler plugins for GHC. My work at the hackathon will be to try and get the current patch (allowing you to write Core optimizations) applied to GHC HEAD. Following that, my plan is to extend the functionality, so you can write Cmm passes as well.<br />
<br />
There's a wiki-page describing this on-going work: http://hackage.haskell.org/trac/ghc/wiki/NewPlugins<br />
<br />
* Hackers: Austin Seipp<br />
<br />
=== Hashing-based containers ===<br />
<br />
I plan to finish a first release of my new HashMap container, based on the hash array mapped trie data structure.<br />
<br />
* Hackers: Johan Tibell<br />
<br />
=== music sequencer ===<br />
<br />
It's a music sequencer in haskell, rather different from other sequencers out there. I'm (elaforge) planning on lazifying score interpretation, or if I'm done with that by the time the hackathon comes up, picking something from the list below:<br />
<br />
* language / score design<br />
* performance tuning (garbage reduction, parallelization, ...)<br />
* port to linux (i.e. write alsa midi or jack midi bindings)<br />
* alternate backends (osc, csound, lilypond, ...)<br />
* GUI / UI<br />
* if someone else is interested, whatever it is they're interested in!<br />
<br />
* Hackers: Evan Laforge<br />
<br />
=== project watcher ===<br />
Code to watch for changes to a project to automatically re-compile, run tests, etc. I have this working for me on Linux now. I would like to release this as an easy to use, platform independent package.<br />
<br />
* Hackers: Greg Weber<br />
<br />
=== Yesod ===<br />
I will probably work on the MongoDB backend for Persistent. If anyone has questions about web development with Yesod, or wants to hack on the framework, let me know.<br />
<br />
* Hackers: Greg Weber<br />
<br />
=== Projects listed in signups ===<br />
<br />
* GHC<br />
** Compiler Plugins<br />
** LLVM backend<br />
* Haskell Platform<br />
* Yices-Painless EDSL<br />
* network package re-write<br />
* BLAS bindings<br />
* iterIO/haskellDB<br />
* music sequencer<br />
* Yesod<br />
* binary file/block device analyzer/editor<br />
* Erland in Haskell<br />
* Graphics<br />
* NoSQL DB<br />
* HWordNet<br />
* barley<br />
* machine learning<br />
* natral language processing<br />
* matrix and tensor manipulation<br />
* DSL for microcontrollers<br />
* hledger<br />
* darcsden<br />
* theorem prover<br />
* interface to Swiss Ephemeris<br />
<br />
<br />
== Links ==<br />
<br />
* [http://wiki.hackerdojo.com/w/page/32992961/Haskell-Hackathon-2011 Hacker Dojo wiki page] for the event</div>Sciolizerhttps://wiki.haskell.org/index.php?title=Foreign_Function_Interface&diff=37728Foreign Function Interface2010-12-04T23:28:48Z<p>Sciolizer: </p>
<hr />
<div>The Foreign Function Interface (FFI) allows you to link Haskell programs to programs written in another language.<br />
<br />
Select one of the following links for more information:<br />
* [[FFI Introduction]]<br />
* The official description: [http://www.cse.unsw.edu.au/~chak/haskell/ffi/ The Haskell 98 Foreign Function Interface 1.0. An Addendum to the Haskell 98 Report]<br />
* [[FFI cook book]]<br />
* [[FFI complete examples]]<br />
* [[GHC/Using the FFI]]<br />
* [http://research.microsoft.com/~simonpj/papers/marktoberdorf/ Tackling the awkward squad]<br />
* Blog article: [http://blog.danieroux.com/2007/01/01/simple-demonstration-of-haskell-ffi/ Simple demonstration of Haskell FFI]<br />
* Blog article: [http://therning.org/magnus/archives/238 C and Haskell sitting in a tree…]<br />
* [[Applications and libraries/Interfacing other languages]]<br />
* Blog article: [http://vis.renci.org/jeff/2009/07/10/c2hs-example-to-save-other-people-frustration/ C2HS example: To save other people frustration] <br />
* [[Cxx foreign function interface]]; how to link to a C++ library<br />
* Blog article: [http://blog.ezyang.com/2010/07/safety-first-ffi-and-threading/ Safety first: FFI and threading]</div>Sciolizerhttps://wiki.haskell.org/index.php?title=FFI_complete_examples&diff=37727FFI complete examples2010-12-04T23:28:41Z<p>Sciolizer: New page: Category:Tutorials This is a repository of COMPLETE WORKING EXAMPLES on how to do FFI. The examples here don't require any tools other than their respective compilers (ghc or g++). In...</p>
<hr />
<div>[[Category:Tutorials]]<br />
<br />
This is a repository of COMPLETE WORKING EXAMPLES on how to do FFI. The examples here don't require any tools other than their respective compilers (ghc or g++). In particular, no make files or helper tools such as c2hs, hsc2hs, or cabal are necessary to build and run these examples.<br />
<br />
A complete novice with no experience in any of Haskell, C, C++, or Python should be able to get all of these examples working. All of the build commands are explicitly given for each example.<br />
<br />
I am using ghc version 6.12.3.<br />
<br />
== When main is in Haskell ==<br />
<br />
The following examples all involve a Haskell program calling into libraries in other languages. These are the simplest case to build, because ghc can usually do the heavy lifting for us.<br />
<br />
=== Calling standard library functions ===<br />
<br />
This example is adapted from [[FFI_Introduction]].<br />
<br />
Main.hs:<br />
<br />
<haskell><br />
{-# LANGUAGE ForeignFunctionInterface #-}<br />
module Main where<br />
<br />
import Prelude hiding (sin)<br />
<br />
import Foreign.C -- get the C types<br />
import Foreign.Ptr (Ptr,nullPtr)<br />
<br />
-- pure function<br />
foreign import ccall "sin" c_sin :: CDouble -> CDouble<br />
sin :: Double -> Double<br />
sin d = realToFrac (c_sin (realToFrac d))<br />
<br />
-- impure function<br />
foreign import ccall "time" c_time :: Ptr a -> IO CTime<br />
getTime :: IO CTime<br />
getTime = c_time nullPtr<br />
<br />
main = do<br />
print . sin =<< readLn<br />
print =<< getTime<br />
</haskell><br />
<br />
To run:<br />
<pre><br />
$ ghc --make Main.hs<br />
[1 of 1] Compiling Main ( Main.hs, Main.o )<br />
Linking Main ...<br />
$ ./Main<br />
3.14159265358<br />
9.793177720293495e-12<br />
1291494446<br />
</pre><br />
<br />
=== Calling C functions when you have the source code ===<br />
<br />
The [[FFI_Introduction]] page has a nice example of wrapping the termios libraries. Here is how to build the program without a make file:<br />
<br />
<pre><br />
$ ghc --make -main-is FfiEx FfiEx.hs termops.c<br />
[1 of 2] Compiling Termios ( Termios.hs, Termios.o )<br />
<br />
Termios.hs:1:11:<br />
Warning: -#include and INCLUDE pragmas are deprecated: They no longer have any effect<br />
<br />
Termios.hs:2:11:<br />
Warning: -#include and INCLUDE pragmas are deprecated: They no longer have any effect<br />
[2 of 2] Compiling FfiEx ( FfiEx.hs, FfiEx.o )<br />
Linking FfiEx ...<br />
$ ./FfiEx<br />
? ayou typed a<br />
? byou typed b<br />
? cyou typed c<br />
? qyou typed q<br />
</pre><br />
<br />
If you are running GHC 6.10 or higher (I am running 6.12.3), you can get rid of the warnings by removing the INCLUDE lines from Termios.hs.<br />
<br />
=== Calling C functions when you don't have the source code ===<br />
<br />
See the [[FFI_Introduction]] page for how to create the files termops.c, termops.h, Termios.hs, and FfiEx.hs. This example is essentially the same as the one on the [[FFI_Introduction]], but we are running by hand the commands that make would normally run for us.<br />
<br />
<pre><br />
$ mkdir c<br />
$ mkdir hs<br />
$ cd c<br />
$ $EDITOR termops.c<br />
$ $EDITOR termops.h<br />
$ gcc -c -o termops.o termops.c<br />
$ cp termops.o ../hs<br />
$ cd ../hs<br />
</pre><br />
<br />
Now to build FfiEx.hs without access to the original c file:<br />
<br />
<pre><br />
$ $EDITOR Termios.hs<br />
$ $EDITOR FfiEx.hs<br />
$ ghc --make -main-is FfiEx -o ffi_ex FfiEx.hs termops.o<br />
[1 of 2] Compiling Termios ( Termios.hs, Termios.o )<br />
<br />
Termios.hs:1:11:<br />
Warning: -#include and INCLUDE pragmas are deprecated: They no longer have any effect<br />
<br />
Termios.hs:2:11:<br />
Warning: -#include and INCLUDE pragmas are deprecated: They no longer have any effect<br />
[2 of 2] Compiling FfiEx ( FfiEx.hs, FfiEx.o )<br />
Linking ffi_ex ...<br />
$ ./ffi_ex <br />
? ayou typed a<br />
? byou typed b<br />
? cyou typed c<br />
? qyou typed q<br />
</pre><br />
<br />
== When main is in C++ ==<br />
<br />
These examples are for building Haskell libraries to be used in a C++ program. Because g++ is not Haskell aware, building is substantially more complicated, so you would normally use a tool for this.<br />
<br />
=== Reading structs in Haskell ===<br />
<br />
Foo.hs:<br />
<br />
<haskell><br />
{-# LANGUAGE ForeignFunctionInterface #-}<br />
module Foo where<br />
<br />
import Foreign.Ptr<br />
import Foreign.Storable<br />
import Foreign.C.Types<br />
<br />
-- pure function<br />
foreign export ccall foo :: MyStruct -> Int<br />
<br />
foo :: MyStruct -> Int<br />
foo = const 42<br />
<br />
-- impure function<br />
foreign export ccall showStruct :: MyStruct -> IO ()<br />
<br />
showStruct :: MyStruct -> IO ()<br />
showStruct ss = peek ss >>= print<br />
<br />
data MyStructType = MyStructType CInt CChar<br />
deriving (Show, Read, Eq)<br />
type MyStruct = Ptr MyStructType<br />
<br />
instance Storable MyStructType where<br />
sizeOf _ = 8<br />
alignment = sizeOf<br />
peek ptr = do<br />
a <- peekByteOff ptr 0<br />
b <- peekByteOff ptr 4<br />
return (MyStructType a b)<br />
</haskell><br />
<br />
test.cpp:<br />
<br />
<pre><br />
#include <iostream><br />
#include "Foo_stub.h"<br />
<br />
struct MyStruct {<br />
int foo;<br />
char bar;<br />
};<br />
<br />
int main(int argc, char *argv[])<br />
{<br />
MyStruct myStruct;<br />
<br />
myStruct.foo = 7;<br />
myStruct.bar = 'x';<br />
<br />
hs_init(&argc, &argv);<br />
std::cout << foo(&myStruct) << "\n";<br />
showStruct(&myStruct);<br />
hs_exit();<br />
return 0;<br />
}<br />
</pre><br />
<br />
Here's where it gets a bit hacky. We need to capture all of Haskell's library dependencies, so we will compile Foo.hs verbosely.<br />
<br />
<pre><br />
$ ghc Foo.hs -v >ghc_output 2>&1<br />
</pre><br />
<br />
This should produce Foo.hi, Foo.o, Foo_stub.c, Foo_stub.h, and Foo_stub.o. Take a look at ghc_output and look for "*** Linker" to see all of the libraries that we will need to let g++ know about.<br />
<br />
<pre><br />
$ grep -A 1 "*** Linker" ghc_output | tail -n 1 | grep -o -- "-L.*" > link_options<br />
</pre><br />
<br />
Now to build test.cpp:<br />
<br />
<pre><br />
$ g++ -c test.cpp -I`ghc --print-libdir`/include<br />
$ g++ -o test Foo.o Foo_stub.o test.o `cat link_options`<br />
$ ./test <br />
42<br />
MyStructType 7 120<br />
</pre><br />
<br />
== When main is in Python ==<br />
<br />
=== Using ctypes ===<br />
<br />
TODO: Adapt [http://darq.weboder.com/entry/2010/jun/03/call-haskell-code-python/ Call Haskell Code From Python].<br />
<br />
=== Using swig (and a c wrapper) ===<br />
<br />
This example is adapted from [http://www.swig.org/tutorial.html The Swig Tutorial]. The factorial function has been modified to call into Haskell.<br />
<br />
Foo.hs:<br />
<br />
<haskell><br />
{-# LANGUAGE ForeignFunctionInterface #-}<br />
module Foo where<br />
<br />
import Foreign.C.Types<br />
<br />
foreign export ccall hs_fact :: CInt -> CInt<br />
hs_fact :: CInt -> CInt<br />
hs_fact n = product [1..n]<br />
</haskell><br />
<br />
example.c:<br />
<br />
<pre><br />
#include "Foo_stub.h"<br />
<br />
void py_init(int argc, char *argv[]) {<br />
hs_init(&argc, &argv);<br />
}<br />
<br />
void py_exit() {<br />
hs_exit();<br />
}<br />
<br />
int fact(int n) {<br />
return hs_fact(n);<br />
}<br />
</pre><br />
<br />
example.i:<br />
<br />
<pre><br />
%module example<br />
%{<br />
<br />
/* Put header files here or function declarations like below */<br />
extern int fact(int n);<br />
extern void py_init(int argc, char** argv);<br />
extern void py_exit();<br />
%}<br />
<br />
%typemap(in) (int argc, char **argv) {<br />
/* Check if is a list */<br />
if (PyList_Check($input)) {<br />
int i;<br />
$1 = PyList_Size($input);<br />
$2 = (char **) malloc(($1+1)*sizeof(char *));<br />
for (i = 0; i < $1; i++) {<br />
PyObject *o = PyList_GetItem($input,i);<br />
if (PyString_Check(o))<br />
$2[i] = PyString_AsString(PyList_GetItem($input,i));<br />
else {<br />
PyErr_SetString(PyExc_TypeError,"list must contain strings");<br />
free($2);<br />
return NULL;<br />
}<br />
}<br />
$2[i] = 0;<br />
} else {<br />
PyErr_SetString(PyExc_TypeError,"not a list");<br />
return NULL;<br />
}<br />
}<br />
<br />
%typemap(freearg) (int argc, char **argv) {<br />
free((char *) $2);<br />
}<br />
<br />
extern int fact(int n);<br />
extern void py_init(int argc, char** argv);<br />
extern void py_exit();<br />
</pre><br />
<br />
run.py:<br />
<br />
<pre><br />
import example<br />
import sys<br />
example.py_init(sys.argv)<br />
print example.fact(5)<br />
example.py_exit()<br />
</pre><br />
<br />
To build (you may need to change the include path if you are using a different installation of python):<br />
<br />
<pre><br />
$ ghc -c -dynamic -fPIC Foo.hs<br />
$ swig -python example.i<br />
$ gcc -fpic -c example.c example_wrap.c -I/usr/include/python2.6 -I`ghc --print-libdir`/include<br />
$ ghc -o _example.so -shared -dynamic -fPIC example.o example_wrap.o Foo.o Foo_stub.o -lHSrts-ghc6.12.3<br />
$ python run.py<br />
</pre></div>Sciolizerhttps://wiki.haskell.org/index.php?title=Haskell_in_industry&diff=19165Haskell in industry2008-02-16T01:53:17Z<p>Sciolizer: Added Anygma stub link</p>
<hr />
<div>Haskell is growing in commercial use. This page collects resources on<br />
the industrial use of Haskell.<br />
<br />
== Haskell in Industry ==<br />
<br />
* [http://www.aetion.com/ Aetion Technologies LLC]<br />
<br />
<blockquote><br />
Aetion is a defense contractor whose applications use artificial intelligence.<br />
Rapidly changing priorities make it important to minimize the code impact of<br />
changes, which suits Haskell well. Aetion has developed three main projects in<br />
Haskell, all successful. Haskell's concise code was perhaps most important for<br />
rewriting: it made it practicable to throw away old code occasionally. DSELs<br />
allowed the AI to be specified very declaratively. <br />
</blockquote><br />
<br />
* [http://www.anygma.com/ Anygma]<br />
<br />
* [http://www.bluespec.com/ Bluespec, Inc.]<br />
<br />
<blockquote><br />
Developing a modern integrated circuit (ASIC or FPGA) is an enormously<br />
expensive process involving specification, modeling (to choose and fix the<br />
architecture), design (to describe what will become silicon) and verification<br />
(to ensure that it meets the specs), all before actually committing anything to<br />
silicon (where the cost of a failure can be tens of millions of dollars).<br />
Bluespec, Inc. is a three year-old company that provides language facilities,<br />
methodologies, and tools for this purpose, within the framework of the IEEE<br />
standard languages SystemVerilog and SystemC, but borrowing ideas heavily from<br />
Term Rewriting Systems and functional programming languages like Haskell. In<br />
this talk, after a brief technical overview to set the context, we will<br />
describe our tactics and strategies, and the challenges we face, in introducing<br />
declarative programming ideas into this field, both externally (convincing<br />
customers about the value of these ideas) and internally (using Haskell for our<br />
tool implementation). <br />
</blockquote><br />
<br />
* [http://www.credit-suisse.com/ Credit Suisse Global Modelling and Analytics Group]<br />
<br />
<blockquote><br />
GMAG, the quantitative modelling group at Credit Suisse, has been using Haskell<br />
for various projects since the beginning of 2006, with the twin aims of<br />
improving the productivity of modellers and making it easier for other people<br />
within the bank to use GMAG models. Current projects include: Further work on<br />
tools for checking, manipulating and transforming spreadsheets; A<br />
domain-specific language embedded in Haskell for implementing reusable<br />
components that can be compiled into various target forms.<br />
[http://tinyurl.com/2lqoq9 We are hiring].<br />
</blockquote><br />
<br />
* [http://www.erlang-consulting.com/ Erlang Training and Consulting Ltd]<br />
<br />
* [http://www.galois.com/ Galois, Inc]<br />
<br />
<blockquote><br />
Galois designs and develops high confidence software for critical applications.<br />
Our innovative approach to software development provides high levels of<br />
assurance, yet its scalability enables us to address the most complex problems.<br />
We have successfully engineered projects under contract for corporations and<br />
government clients in the demanding application areas of security, information<br />
assurance and cryptography. <br />
</blockquote><br />
<br />
* [http://iba-cg.de/haskell.html iba Consulting Gesellschaft] - Intelligent business architecture for you<br />
<blockquote>iba CG develops software for large companies: <br />
* risk analysis and reporting solution for power supply company; <br />
* contract management, assert management, booking and budgeting software for one of the worldwide leading accounting firm.<br />
</blockquote><br />
<br />
* [http://article.gmane.org/gmane.comp.lang.haskell.cafe/21951 HAppS LLC]<br />
<br />
<blockquote><br />
Open web development company.<br />
</blockquote><br />
<br />
* [http://www.linspire.com/ Linspire]<br />
<br />
<blockquote><br />
Linspire, Inc. has used functional programming since its inception in 2001,<br />
beginning with extensive use of O'Caml, with a steady shift to Haskell as its<br />
implementations and libraries have matured. Hardware detection, software<br />
packaging and CGI web page generation are all areas where we have used<br />
functional programming extensively. Haskell's feature set lets us replace much<br />
of our use of little languages (e.g., bash or awk) and two-level languages (C<br />
or C++ bound to an interpreted language), allowing for faster development,<br />
better code sharing and ultimately faster implementations. Above all, we value<br />
static type checking for minimizing runtime errors in applications that run in<br />
unknown environments and for wrapping legacy programs in strongly typed<br />
functions to ensure that we pass valid arguments. <br />
</blockquote><br />
<br />
* [http://www.haskell.org/haskellwiki/Nokia_Research_Center_Cambridge Nokia Research Center Cambridge]<br />
<br />
<blockquote><br />
Nokia Research Center Cambridge is a group of 16 researchers located in<br />
Cambridge, Massachusetts. NRCC's charter is to renew Nokia via open<br />
innovation, in particular via joint research projects with MIT Computer<br />
Science and Artificial Intelligence Laboratory. We are a systems<br />
research center, investigating all aspects of future mobile phones and<br />
services. Our goal is to develop new technologies, applications, and<br />
services, and to work with the rest of Nokia to make these a reality.<br />
</blockquote><br />
<br />
* [http://www.db.com/ Deutsche Bank Equity Proprietary Trading, Directional Credit Trading]<br />
<br />
<blockquote><br />
The Directional Credit Trading group uses Haskell as the primary implementation language for all its software infrastructure.<br />
</blockquote><br />
<br />
* [http://cufp.galois.com/2007Abstracts.html#CyrilSchmidt ABN AMRO]<br />
<br />
<blockquote><br />
ABN AMRO is an international bank headquartered in Amsterdam. For its investment banking activities it needs to measure the counterparty risk on portfolios of financial derivatives.<br />
</blockquote><br />
<br />
* [http://www.barcap.com/ Barclays Capital]<br />
<br />
<blockquote><br />
See http://jobs-in-fp.org/<br />
</blockquote><br />
<br />
* [http://blog.openomy.com/2008/01/case-study-using-haskell-and-happs-for.html Openomy]<br />
:Openomy's API v2.0 is developed in Haskell, using the [http://www.happs.org/ HAppS] web platform.<br />
<br />
Quotes are taken from the [http://www.galois.com/cufp/ Commercial Users of Functional Programming] workshop. If you're using Haskell commercially, please add your details here.<br />
<br />
== Jobs and recruitment ==<br />
<br />
[[Jobs|Haskell jobs]].<br />
<br />
See also the [http://www.jobs-in-fp.org/ Jobs in Functional Programming] event.<br />
<br />
== Commercial Users of Functional Programming Workshop ==<br />
<br />
[http://www.galois.com/cufp/ Commercial Users of Functional Programming]<br />
<br />
The goal of [http://www.galois.com/cufp/ CUFP] is to build a community<br />
for users of functional programming languages and technology, be they<br />
using functional languages in their professional lives, in an open<br />
source project (other than implementation of functional languages), as a<br />
hobby, or any combination thereof. In short: anyone who uses functional<br />
programming as a means, but not an end.<br />
<br />
[[Category:Community]]</div>Sciolizerhttps://wiki.haskell.org/index.php?title=Jobs&diff=19164Jobs2008-02-16T01:49:45Z<p>Sciolizer: Added Anygma to industry positions</p>
<hr />
<div>Haskell is a freely available language based on [http://www.opensource.org/ open-source software]. So this page mainly advertises for participation in unpaid projects. However, advertisements for university and industry positions are just as welcome.<br />
<br />
If you are seeking Haskell jobs, good places to follow are the Haskell<br />
mailing list, and the Types mailing list, particularly for research jobs.<br />
<br />
==Academic positions==<br />
*[http://jobs.nottingham.ac.uk/vacancies.aspx?cat=160#j2797 Two Lectureships in Nottingham]<br />
<br />
==Industry positions==<br />
<br />
*[http://www.aetion.com/ Aetion Technologies LLC]<br />
*[http://www.bluespec.com/about/careers.htm Bluespec, Inc.]<br />
*[https://creditsuisse.taleo.net/servlets/CareerSection?art_ip_action=FlowDispatcher&flowTypeNo=13&pageSeq=2&reqNo=53820&art_servlet_language=en&selected_language=en&csNo=10020#topOfCsPage Credit Suisse]<br />
*[http://www.erlang-consulting.com/jobs.html Erlang Training and Consulting Ltd]<br />
*[http://www.galois.com/join.php Galois, Inc]<br />
*[[Nokia Research Center Cambridge]]<br />
*[http://article.gmane.org/gmane.comp.lang.haskell.cafe/21951 HAppS LLC]<br />
*[http://article.gmane.org/gmane.comp.lang.haskell.cafe/36676 Anygma]<br />
<br />
See the most up to date list on the [[Haskell in industry]] page.<br />
<br />
===Recent positions===<br />
<br />
*[http://article.gmane.org/gmane.comp.lang.haskell.cafe/33377 Prototyping]<br />
*[http://article.gmane.org/gmane.comp.lang.haskell.cafe/30685 Web development]<br />
*[http://article.gmane.org/gmane.comp.lang.haskell.cafe/30228 Finance]<br />
<br />
===Recruitment days===<br />
<br />
*[http://www.jobs-in-fp.org/ Jobs in FP]<br />
<br />
==Fellowships==<br />
<br />
* [http://www.cs.nott.ac.uk/~gmh/fellowship Postdoctoral Research Fellowship in Functional Programming, Nottingham]<br />
<br />
==PhD/MSc Studentships==<br />
<br />
* [http://www.cs.chalmers.se/~koen/phdad.html PhD positions at Chalmers on Verification and Testing]<br />
<br />
* [http://www.haskell.org/pipermail/haskell/2007-June/019591.html PhD student on Real-life datatype-generic programming]<br />
<br />
==Internships==<br />
<br />
[http://hackage.haskell.org/trac/ghc/wiki/Internships Internships on Haskell and GHC, at Microsoft Research, Cambridge]<br />
<br />
[[Category:Community]]</div>Sciolizerhttps://wiki.haskell.org/index.php?title=Lazy_vs._non-strict&diff=16921Lazy vs. non-strict2007-11-19T21:03:26Z<p>Sciolizer: referenced example in non-strict semantics</p>
<hr />
<div>(this is a bit of a stub. Feel free to edit)<br />
<br />
Haskell is often described as a lazy language. However, the language specification simply states that Haskell is non-strict, which is not quite the same thing as lazy. See [[Non-strict semantics]] for a brief example.<br />
<br />
(describe WHNF)<br />
<br />
Laziness is simply a common implementation technique for non-strict languages, but it is not the only possible technique. One major drawback with lazy implementations is that they are not generally amenable to parallelisation. This paper states that experiments indicate that little parallelism can be extracted from lazy programs:<br />
<br />
"The Impact of Laziness on Parallelism and the Limits of Strictness Analysis"<br />
(G. Tremblay G. R. Gao)<br />
http://citeseer.ist.psu.edu/tremblay95impact.html<br />
<br />
Lenient, or optimistic, evaluation is an implementation approach that lies somewhere between lazy and strict, and combines eager evaluation with non-strict semantics. This seems to be considered more promising for parallelisation.<br />
<br />
This paper implies (section 2.2.1) that lenient evaluation can handle circular data structures and recursive definitions, but cannot express infinite structures without explicit use of delays:<br />
<br />
"How Much Non-strictness do Lenient Programs Require?"<br />
(Klaus E. Schauser, Seth C. Goldstein)<br />
http://citeseer.ist.psu.edu/schauser95how.html<br />
<br />
Some experiments with non-lazy Haskell compilers have been attempted:<br />
http://www.haskell.org/haskellwiki/Research_papers/Runtime_systems#Optimistic_Evaluation<br />
<br />
[[Category:Theoretical_foundations]]</div>Sciolizerhttps://wiki.haskell.org/index.php?title=Blow_your_mind&diff=16342Blow your mind2007-10-25T23:11:15Z<p>Sciolizer: Added tweaked example from sigfpe's "From Löb's Theorem to Spreadsheet Evaluation"</p>
<hr />
<div>Useful Idioms that will blow your mind (unless you already know them :)<br />
<br />
This collection is supposed to be comprised of short, useful, cool, magical examples, which should incite the reader's curiosity and (hopefully) lead him to a deeper understanding of advanced Haskell concepts. At a later time I might add explanations to the more obscure solutions. I've also started providing several alternatives to give more insight into the interrelations of solutions.<br />
<br />
More examples are always welcome, especially "obscure" monadic ones.<br />
<br />
<br />
== List/String operations ==<br />
<br />
<br />
<haskell><br />
-- split at whitespace<br />
-- "hello world" -> ["hello","world"]<br />
words<br />
<br />
unfoldr (\b -> fmap (const . (second $ drop 1) . break (==' ') $ b) . listToMaybe $ b)<br />
<br />
takeWhile (not . null) . evalState (repeatM $ modify (drop 1) >> State (break (== ' '))) . (' ' :)<br />
where repeatM = sequence . repeat<br />
<br />
fix (\f l -> if null l then [] else let (s,e) = break (==' ') l in s:f (drop 1 e))<br />
<br />
<br />
-- splitting in two (alternating)<br />
-- "1234567" -> ("1357", "246")<br />
-- the lazy match with ~ is necessary for efficiency, especially enabling processing of infinite lists<br />
foldr (\a ~(x,y) -> (a:y,x)) ([],[])<br />
<br />
(map snd *** map snd) . partition (even . fst) . zip [0..]<br />
<br />
transpose . unfoldr (\a -> toMaybe (null a) (splitAt 2 a))<br />
-- this one uses the solution to the next problem in a nice way :)<br />
<br />
toMaybe b x = if b then Just x else Nothing<br />
-- or generalize it:<br />
-- toMaybe = (toMonadPlus :: Bool -> a -> Maybe a)<br />
toMonadPlus b x = guard b >> return x<br />
<br />
-- splitting into lists of length N<br />
-- "1234567" -> ["12", "34", "56", "7"]<br />
unfoldr (\a -> toMaybe (null a) (splitAt 2 a))<br />
<br />
takeWhile (not . null) . unfoldr (Just . splitAt 2)<br />
<br />
<br />
-- sorting by a custom function<br />
-- length -> ["abc", "ab", "a"] -> ["a", "ab", "abc"]<br />
comparing f x y = compare (f x) (f y)<br />
sortBy (comparing length)<br />
<br />
map snd . sortBy (comparing fst) . map (length &&& id) <br />
-- the so called "Schwartzian Transform" for computationally more expensive <br />
-- functions.<br />
<br />
-- comparing adjacent elements<br />
rises xs = zipWith (<) xs (tail xs)<br />
<br />
-- lazy substring search<br />
-- "ell" -> "hello" -> True<br />
substr a b = any (a `isPrefixOf`) $ tails b<br />
<br />
-- multiple splitAt's:<br />
-- splitAts [2,5,0,3] [1..15] == [[1,2],[3,4,5,6,7],[],[8,9,10],[11,12,13,14,15]]<br />
splitAts = foldr (\n r -> splitAt n >>> second r >>> uncurry (:)) return<br />
<br />
-- frequency distribution<br />
-- "abracadabra" -> fromList [('a',5),('b',2),('c',1),('d',1),('r',2)]<br />
import Data.Map<br />
histogram = fromListWith (+) . (`zip` repeat 1)<br />
<br />
-- using arrows and sort<br />
histogramArr = map (head&&&length) . group . sort<br />
</haskell><br />
<br />
== Mathematical sequences, etc ==<br />
<br />
<br />
<haskell><br />
-- factorial<br />
-- 6 -> 720<br />
product [1..6]<br />
<br />
foldl1 (*) [1..6]<br />
<br />
(!!6) $ scanl (*) 1 [1..]<br />
<br />
fix (\f n -> if n <= 0 then 1 else n * f (n-1))<br />
<br />
<br />
-- powers of two sequence<br />
iterate (*2) 1<br />
<br />
unfoldr (\z -> Just (z,2*z)) 1<br />
<br />
<br />
-- fibonacci sequence<br />
unfoldr (\(f1,f2) -> Just (f1,(f2,f1+f2))) (0,1)<br />
<br />
fibs = 0:1:zipWith (+) fibs (tail fibs)<br />
<br />
fib = 0:scanl (+) 1 fib<br />
<br />
<br />
-- pascal triangle<br />
pascal = iterate (\row -> zipWith (+) ([0] ++ row) (row ++ [0])) [1]<br />
<br />
<br />
-- prime numbers<br />
-- example of a memoising caf (??)<br />
primes = sieve [2..] where<br />
sieve (p:x) = p : sieve [ n | n <- x, n `mod` p > 0 ]<br />
<br />
unfoldr sieve [2..] where <br />
sieve (p:x) = Just(p, [ n | n <- x, n `mod` p > 0 ])<br />
<br />
-- or if you want to use the Sieve of Eratosthenes..<br />
diff [] l = l<br />
diff l [] = l<br />
diff xl@(x:xs) yl@(y:ys) | x < y = x:diff xs yl<br />
| x > y = diff xl ys<br />
| otherwise = diff xs ys <br />
esieve [] = []<br />
esieve (p:ps) = p:esieve (diff ps (iterate (+p) p))<br />
eprimes = esieve [2..]<br />
<br />
-- enumerating the rationals (see [1])<br />
rats :: [Rational]<br />
rats = iterate next 1 where<br />
next x = recip (fromInteger n+1-y) where (n,y) = properFraction x<br />
<br />
-- another way<br />
rats2 = fix ((1:) . (>>= \x -> [1+x, 1/(1+x)])) :: [Rational]<br />
</haskell><br />
<br />
[1] [http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#rationals Gibbons, Lest, Bird - Enumerating the Rationals]<br />
<br />
== Monad magic ==<br />
<br />
The list monad can be used for some amazing Prolog-ish search problems.<br />
<br />
<haskell><br />
-- all combinations of a list of lists.<br />
-- these solutions are all pretty much equivalent in that they run<br />
-- in the List Monad. the "sequence" solution has the advantage of<br />
-- scaling to N sublists.<br />
-- "12" -> "45" -> ["14", "15", "24", "25"]<br />
sequence ["12", "45"]<br />
<br />
[[x,y] | x <- "12", y <- "45"]<br />
<br />
do { x <- "12"; y <- "45"; return [x,y] }<br />
<br />
"12" >>= \a -> "45" >>= \b -> return [a,b]<br />
<br />
-- all combinations of letters<br />
(inits . repeat) ['a'..'z'] >>= sequence<br />
<br />
-- apply a list of functions to an argument<br />
-- even -> odd -> 4 -> [True,False]<br />
map ($4) [even,odd]<br />
<br />
sequence [even,odd] 4<br />
<br />
-- all subsequences of a sequence/ aka powerset.<br />
filterM (const [True, False])<br />
<br />
-- apply a function to two other function the same argument<br />
-- (lifting to the Function Monad (->))<br />
-- even 4 && odd 4 -> False<br />
liftM2 (&&) even odd 4<br />
<br />
liftM2 (>>) putStrLn return "hello"<br />
<br />
fix ((1:) . (>>= \x -> [x+1, 1/(x+1)])) :: [Rational]<br />
[1%1,2%1,1%2,3%1,1%3,3%2,2%3,4%1,1%4,4%3,3%4,5%2,2%5,5%3,3%5,5%1,1%5,5%4,4%5...<br />
<br />
-- forward function concatenation<br />
(*3) >>> (+1) $ 2<br />
<br />
foldl1 (flip (.)) [(+1),(*2)] 500<br />
<br />
<br />
-- perform functions in/on a monad, lifting<br />
fmap (+2) (Just 2)<br />
<br />
liftM2 (+) (Just 4) (Just 2)<br />
<br />
<br />
-- [still to categorize]<br />
(id >>= (+) >>= (+) >>= (+)) 3 -- (3+3)+(3+3) = 12<br />
<br />
double = join (+)<br />
<br />
(join . liftM2) (*) (+3) 5 -- 64<br />
<br />
mapAccumL (\acc n -> (acc+n,acc+n)) 0 [1..10] -- interesting for fac, fib, ...<br />
<br />
do f <- [not, not]; d <- [True, False]; return (f d) -- [False,True,False,True]<br />
<br />
do { Just x <- [Nothing, Just 5, Nothing, Just 6, Just 7, Nothing]; return x }<br />
</haskell><br />
<br />
== Other ==<br />
<br />
<br />
<haskell><br />
-- simulating lisp's cond<br />
case () of () | 1 > 2 -> True<br />
| 3 < 4 -> False<br />
| otherwise -> True<br />
<br />
<br />
-- match a constructor<br />
-- this is better than applying all the arguments, because this way the<br />
-- data type can be changed without touching the code (ideally).<br />
case a of Just{} -> True<br />
_ -> False<br />
<br />
<br />
-- spreadsheet magic<br />
-- requires import Control.Monad.Instances<br />
let loeb x = fmap ($ loeb x) x in <br />
loeb [ (!!5), const 3, liftM2 (+) (!!0) (!!1), (*2) . (!!2), length, const 17]<br />
<br />
<br />
{- <br />
TODO, IDEAS:<br />
more fun with monad, monadPlus (liftM, ap, guard, when)<br />
fun with arrows (second, first, &&&, ***)<br />
liftM, ap<br />
lazy search (searching as traversal of lazy structures)<br />
innovative data types (i.e. having fun with Maybe sequencing)<br />
<br />
LINKS:<br />
bananas, envelopes, ... (generic traversal)<br />
why functional fp matters (lazy search, ...)<br />
-}<br />
</haskell><br />
<br />
=== Polynomials ===<br />
In abstract algebra you learn that polynomials can be used the same way integers are used given the right assumptions about their coefficients and roots. Specifically, polynomials support addition, subtraction, multiplication and sometimes division. It also turns out that one way to think of polynomials is that they are just lists of numbers (their coefficients). <br />
<br />
instance Num a => Num [a] where -- (1)<br />
<br />
(f:fs) + (g:gs) = f+g : fs+gs -- (2)<br />
fs + [] = fs -- (3a)<br />
[] + gs = gs -- (3b)<br />
<br />
(f:fs) * (g:gs) = f*g : [f]*gs + fs*(g:gs) -- (4)<br />
_ * _ = [] -- (5)<br />
<br />
====Explanation====<br />
(1) puts lists into type class Num, the class to which operators + and * belong, provided the list elements are in class Num.<br />
<br />
Lists are ordered by increasing powers. Thus <tt>f:fs</tt> means <tt>f+x*fs</tt> in algebraic notation. (2) and (4) follow from these algebraic identities:<br />
<br />
(f+x*fs) + (g+x*gs) = f+g + x*(fs+gs)<br />
(f+x*fs) * (g+x*gs) = f*g + x*(f*gs + fs*(g+x*gs))<br />
<br />
(3) and (5) handle list ends.<br />
<br />
The bracketed <tt>[f]</tt> in (4) avoids mixed arithmetic, which Haskell doesn't support.<br />
<br />
====Comments====<br />
<br />
The methods are qualitatively different from ordinary array-based methods; there is no vestige of subscripting or counting of terms.<br />
<br />
The methods are suitable for on-line computation. Only<br />
<i>n</i> terms of each input must be seen before the <i>n</i>-th term<br />
of output is produced.<br />
<br />
Thus the methods work on infinite series as well as polynomials.<br />
<br />
Integer power comes for free. This example tests the cubing of (1+x):<br />
<br />
[1, 1]^3 == [1, 3, 3, 1]<br />
<br />
See also<br />
* [[Pointfree]]<br />
* [http://darcs.haskell.org/numericprelude/src/MathObj/Polynomial.hs NumericPrelude: Polynomials]<br />
* [[Add polynomials]]<br />
* Solve differential equations in terms of [http://www.haskell.org/pipermail/haskell-cafe/2004-May/006192.html power series].<br />
<br />
[[Category:Idioms]]<br />
[[Category:Mathematics]]</div>Sciolizer