1 {-# OPTIONS_GHC -freduction-depth=1000 #-}

2 {-# LANGUAGE

3 FlexibleContexts, FlexibleInstances, FunctionalDependencies,

4 MultiParamTypeClasses, TypeSynonymInstances,

5 TypeOperators, UndecidableInstances, TypeFamilies #-}

8 -- As the below code demonstrates, the same issues demonstrated with

9 -- Functional Dependencies also appear with Type Families, although less

10 --horribly, as their code-path seems more optimized in the current

11 -- constraint solver:

13 -- Our running example, for simplicity's sake, is a type-level map of a

14 -- single function. For reference, here is the code for a simple

15 -- value-level map of a single function.

17 -- > vfoo = id

18 -- > mapfoo (x : xs) = vfoo x : mapfoo xs

19 -- > mapfoo [] = []

21 -- Because Haskell is a lazy language, this runs in O(n) time and constant stack.

23 -- We now lift map to the type level, to operate over HLists.

25 -- First, the basic HList types

31 -- Next, a large boring HList

33 -- Adds ten cells

36 x

41 -- Has 70 cells.

44 HNil

48 type TFooFun x

69 thMapFoo1 _ = HNil

71 -- The following, when enabled, takes ~3.5s. This demonstrates that slowdown occurs with type families as well.

73 testTHMapFoo1 = thMapFoo1 sampleData

85 thMapFoo2 acc _ = acc

87 -- The following, when enabled, takes ~0.6s. This demonstrates that the

88 -- tail recursive transform fixes the slowdown with type families just as

89 -- with fundeps.

91 testTHMapFoo2 = thMapFoo2 HNil sampleData

103 thMapFoo3 acc _ = acc

105 -- The following, when enabled, also takes ~0.6s. This demonstrates that,

106 -- unlike the fundep case, the order of type class constraints does not,

107 -- in this instance, affect the performance of type families.

109 testTHMapFoo3 = thMapFoo3 HNil sampleData