# GHC/AdvancedOverlap

### From HaskellWiki

< GHC

## Contents |

## 1 Choosing a type-class instance based on the context

Oleg Kiselyov and Simon Peyton-Jones (Apr 2008)

### 1.1 Problem definition

Suppose you have this class:

class Print a where print :: a -> IO ()

a

Show

instance Show a => Print a where print x = putStrLn (show x) instance Print a where print x = putStrLn "No show method"

But that is illegal in Haskell, because the heads of the two instance declarations are identical. Nevertheless, you can code it up using functional dependencies and overlapping instances, and that's what this note describes.

### 1.2 Solution 1 (using safer overlapping instances)

First define an auxiliary classPrint'

class Print' flag a where print' :: flag -> a -> IO () instance (ShowPred a flag, Print' flag a) => Print a where print = print' (undefined::flag)

Print

ShowPred

Show

-- Just two distinct types -- alternatively use 'True and 'False with -XDataKinds data HTrue data HFalse class ShowPred a flag | a->flag where {} -- Used only if the other -- instances don't apply -- instance TypeCast flag HFalse => ShowPred a flag -- before -XTypeFamilies instance (flag ~ HFalse) => ShowPred a flag instance ShowPred Int HTrue -- These instances must be instance ShowPred Bool HTrue -- the same as Show's instance ShowPred a flag => ShowPred [a] flag -- ...etc...

(ShowPred ty flag)

ty

HTrue

HFalse

Print'

instance (Show a) => Print' HTrue a where print' _ x = putStrLn (show x) instance Print' HFalse a where print' _ x = putStrLn "No show method"

(C a)

(C' a flag)

HTrue

HFalse

C a succeeds <--> C' a flag unifies flag with HTruePerhaps the most puzzling is the constraint

(TypeCast flag HFalse)

ShowPred

TypeCast

<http://homepages.cwi.nl/~ralf/HList/paper.pdf>

#### 1.2.1 Notes and variations

1. A more `closed world' alternative: writeShowPred

class ShowPred a flag | a->flag where {} instance HMember a Showtypes flag => ShowPred a flag

ShowPred

Showtypes

type Showtypes = Int :+: Bool :+: Char :+: ... :+: HNil

[a]

HMember

HList

HMember

TypeEq

requires overlapping instances.

ShowPred

Show

Show'

class Show' a flag | a->flag where show :: a -> String -- This instance is used only if the others don't apply instance TypeCast flag HFalse => Show' a flag where show = error "urk" -- These instances are the regular ones instance Show' Int HTrue where show = showInt instance Show' Bool HTrue where show = showBool ...etc...

Print'

instance Show' HTrue a => Print' HTrue a where print' x = putStrLn (show x) instance Print' HFalse a where print' x = putStrLn "No show method"

Show

class.

3. We need a bit of boolean algebra in the more interesting instances

ShowPred

instance (ShowPred a flag1, ShowPred b flag2, And flag1 flag2 flag) => (ShowPred (a,b) flag class And a b c | a b -> c instance And HTrue b b instance And HFalse b HFalse

The HList paper shows many examples of such type-level programming.

### 1.3 Solution 2 (using incoherent instances)

TurnShowPred

-- ShowPred is a predicate on types, which says -- which ones are instances of class Show type family ShowPred a type instance ShowPred a = HFalse type instance ShowPred Int = HTrue type instance ShowPred Bool = HTrue type instance ShowPred [a] = ShowPred a type instance ShowPred (a,b) = And (ShowPred a, ShowPred b) -- ...etc...

ShowPred

Without closed families, a solution is still available which mirrors the original program from solution 1. This requires -XIncoherentInstances in addition to the other flags.

class Print a where print :: a -> IO () instance (ShowPred a ~ flag, Print' flag a) => Print a where print = print' (undefined::flag) class Print' flag a where print' :: flag -> a -> IO () instance Show a => Print' HTrue a where print' _ x = putStrLn (show x) instance Print' flag a where print' _ _ = putStrLn "No show method" data HTrue data HFalse type family ShowPred a type instance ShowPred Int = HTrue type instance ShowPred Bool = HTrue

ShowPred

instance (ShowPred a flag, Print' flag a) => Print a

ShowPred a flag

instance (flag ~ HFalse) => ShowPred a flag

Print' flag a

Print' HTrue a

Print' HFalse a

(flag ~ HFalse)

ShowPred a

### 1.4 Solution 3 (using closed type families)

As of GHC 7.8, closed type families are available. For more details, see Type families#Closed family simplification. It is possible to rewriteShowPred

type family ShowPred a where ShowPred Int = HTrue ShowPred Bool = HTrue ShowPred [a] = ShowPred a ShowPred (a,b) = And (ShowPred a, ShowPred b) ShowPred a = HFalse

There are no incoherent instances anymore.

Any unspecifiedShowPred a

ShowPred a

Print' HTrue a

Print' flag a

Print' (ShowPred a) a

## 2 Appendix: the sample code

{-# LANGUAGE EmptyDataDecls, MultiParamTypeClasses, ScopedTypeVariables, FunctionalDependencies, OverlappingInstances, FlexibleInstances, UndecidableInstances #-} module Main where import Prelude hiding (print) class Print a where print :: a -> IO () {- the following does not work: instance Show a => Print a where print x = putStrLn (show x) instance Print a where print x = putStrLn "No show method" error: Duplicate instance declarations: instance (Show a) => Print a -- Defined at /tmp/wiki.hs:7:0 instance Print a -- Defined at /tmp/wiki.hs:9:0 -} class Print' flag a where print' :: flag -> a -> IO () instance (ShowPred a flag, Print' flag a) => Print a where print = print' (undefined::flag) -- overlapping instances are used only for ShowPred class ShowPred a flag | a->flag where {} -- Used only if the other -- instances don't apply instance TypeCast flag HFalse => ShowPred a flag instance ShowPred Int HTrue -- These instances should be instance ShowPred Bool HTrue -- the same as Show's instance ShowPred a flag => ShowPred [a] flag -- ...etc... data HTrue -- Just two data HFalse -- distinct types instance Show a => Print' HTrue a where print' _ x = putStrLn (show x) instance Print' HFalse a where print' _ x = putStrLn "No show method" test1 = print [True,False] -- [True,False] test2 = print id -- No show method -- see http://okmij.org/ftp/Haskell/typecast.html class TypeCast a b | a -> b, b->a where typeCast :: a -> b class TypeCast' t a b | t a -> b, t b -> a where typeCast' :: t->a->b class TypeCast'' t a b | t a -> b, t b -> a where typeCast'' :: t->a->b instance TypeCast' () a b => TypeCast a b where typeCast x = typeCast' () x instance TypeCast'' t a b => TypeCast' t a b where typeCast' = typeCast'' instance TypeCast'' () a a where typeCast'' _ x = x