Personal tools

Simonpj/Talk:FunWithTypeFuns

From HaskellWiki

Revision as of 14:40, 14 May 2009 by Simonpj (Talk | contribs)

Jump to: navigation, search

Fun with Type Functions

Oleg Kiselyov, Ken Shan, and Simon Peyton Jones have a draft paper

which will appear in the proceedings of Tony Hoare's 75th birthday celebration.

Abstract. Tony Hoare has always been a leader in writing down and proving properties of programs. To prove properties of programs automatically, the most widely used technology today is by far the ubiquitous type checker. Alas, static type systems inevitably exclude some good programs and allow some bad ones. This dilemma motivates us to describe some fun we've been having with Haskell, by making the type system more expressive without losing the benefits of automatic proof and compact expression.

Haskell's type system extends Hindley-Milner with two distinctive features: polymorphism over type constructors and overloading using type classes. These features have been integral to Haskell since its beginning, and they are widely used and appreciated. More recently, Haskell has been enriched with type families, or associated types, which allows functions on types to be expressed as straightforwardly as functions on values. This facility makes it easier for programmers to effectively extend the compiler by writing functional programs that execute during type-checking.

This paper gives a programmer's tour of type families as they are supported in GHC today.

This Wiki page is a discussion page for the paper. If you are kind enough to read this paper, please help us by jotting down any thoughts it triggers off. Things to think about:

  • What is unclear?
  • What is omitted that you'd like to see?
  • Do you have any cool examples that are of a somewhat different character than the ones we describe? (If so, do explain the example on this page!)

Deadline is sometime in June 2009.

You can identify your entries by preceding them with four tildes. Doing so adds your name, and the date. Thus:

Simonpj 08:42, 19 April 2007 (UTC) Note from Simon


If you say who you are in this way, we'll be able to acknowledge your help in a revised version of the paper.


Add comments here (newest at the top):

Peter Verswyvelen and I have been working on some type family fun to give us generalised partial application (even to the point of being able to cope with giving arguments, but not a function). I don't know if it really makes any interesting point that you didn't already in the paper, but it's certainly fun...

{-# LANGUAGE TypeFamilies, EmptyDataDecls, TypeOperators, FlexibleInstances, FlexibleContexts #-}
 
module Burn2 where
 
newtype V a = V a -- A value<br />
data    B a = B   -- A value we don't want to provide yet
 
-- Type level homogenous lists (well just tuples in a list-like syntax really)<br />
data Nil a = Nil<br />
data a :& b = !a :& !b
 
infixr 5 :& 
 
class Apply funargs where<br />
  type Result funargs :: *<br />
  apply :: funargs -> Result funargs
 
instance (Apply (V b :& rest), a ~ c) => Apply (V (a->b) :& V c :& rest) where<br />
  type Result  (V (a->b) :& V c :& rest) = Result (V b :& rest)<br />
  apply (V f :& V a :& rest) = apply $ V (f a) :& rest
 
instance (Apply (V b :& rest), a ~ c) => Apply (B (a->b) :& V c :& rest) where<br />
  type Result (B (a->b) :& V c :& rest) = (a->b) -> Result (V b :& rest)<br />
  apply (B :& V a :& rest) = \f -> apply $ V (f a) :& rest
 
instance (Apply (V b :& rest), a ~ c) => Apply (V (a->b) :& B c :& rest) where<br />
  type Result  (V (a->b) :& B c :& rest) = a -> Result (V b :& rest)<br />
  apply (V f :& B :& rest) = \a -> apply $ V (f a) :& rest
 
instance (Apply (V b :& rest), a ~ c) => Apply (B (a->b) :& B c :& rest) where<br />
  type Result (B (a->b) :& B c :& rest) = (a->b) -> a -> Result (V b :& rest)<br />
  apply (B :& B :& rest) = \f a -> apply $ V (f a) :& rest
 
instance Apply (V a :& Nil b) where<br />
  type Result  (V a :& Nil b) = a<br />
  apply (V a :& Nil) = a
 
instance Apply (B a :& Nil b) where<br />
  type Result  (B a :& Nil b) = B a<br />
  apply (B :& Nil) = B
 
v1 = apply (V 1 :& Nil)
f1 = apply (B :& Nil)
v2 = apply (V negate :& V 1 :& Nil)
f3 = apply (V negate :& B :& Nil)
v3 = apply (V f3 :& V 1 :& Nil)

Beelsebob 13:04, 14 May 2009 (UTC)