more efficient type-level computations using type families?

Question

Based on the article in the Monad Reader, Issue #8, I've coded up the type-level solution to the "Instant Insanity" puzzle using both Functional Dependencies and Type Families:

• fundeps solution: http://lpaste.net/113108
• type family solution: http://lpaste.net/113113

The fundeps solutions takes about 200 secs. whereas the type families version completes in about 800 secs.

Are there any techniques I can employ to make the type family version run more efficiently?

Answer 1

I've added the following definitions of main to your two snippets, so that the solution is shown in a type error message complaining about the missing Show instance:

-- fundeps.hs
{-# OPTIONS_GHC -fcontext-stack=400 #-}
main = print $ solutions (undefined :: Cubes)

-- families-open.hs
{-# OPTIONS_GHC -ftype-function-depth=400 #-}
data Proxy a = Proxy
main = print (Proxy :: Proxy (Solutions Cubes))

and compiled both with GHC 7.8.3 to get some baseline timings:

• fundeps.hs : 23s
• families-open.hs : 46s

I've found that just transforming the type family version to use closed type families (code here) speeds it up enough to split the difference:

• families-closed.hs : 36s

I thought I could speed it up more by giving strict kinds to the type families by using DataKinds (code here), but surprisingly, that got me back to square one:

• families-closed-datakinds.hs : 44s

However, at least it produces the most readable output of all four versions:

No instance for (Show
                   (Proxy
                      '['['Cube 'G 'B 'W 'R 'B 'G, 'Cube 'W 'G 'B 'W 'R 'R,
                          'Cube 'R 'W 'R 'B 'G 'R, 'Cube 'B 'R 'G 'G 'W 'W],
                        '['Cube 'G 'B 'R 'W 'B 'G, 'Cube 'R 'R 'W 'B 'G 'W,
                          'Cube 'R 'G 'B 'R 'W 'R, 'Cube 'W 'W 'G 'G 'R 'B],
                        '['Cube 'G 'W 'R 'B 'B 'G, 'Cube 'W 'B 'W 'R 'G 'R,
                          'Cube 'R 'R 'B 'G 'W 'R, 'Cube 'B 'G 'G 'W 'R 'W],
                        '['Cube 'G 'R 'W 'B 'B 'G, 'Cube 'R 'W 'B 'G 'R 'W,
                          'Cube 'R 'B 'R 'W 'G 'R, 'Cube 'W 'G 'G 'R 'W 'B],
                        '['Cube 'G 'R 'B 'B 'W 'G, 'Cube 'W 'W 'R 'G 'B 'R,
                          'Cube 'R 'B 'G 'W 'R 'R, 'Cube 'B 'G 'W 'R 'G 'W],
                        '['Cube 'G 'W 'B 'B 'R 'G, 'Cube 'R 'B 'G 'R 'W 'W,
                          'Cube 'R 'R 'W 'G 'B 'R, 'Cube 'W 'G 'R 'W 'G 'B],
                        '['Cube 'G 'B 'B 'W 'R 'G, 'Cube 'W 'R 'G 'B 'W 'R,
                          'Cube 'R 'G 'W 'R 'B 'R, 'Cube 'B 'W 'R 'G 'G 'W],
                        '['Cube 'G 'B 'B 'R 'W 'G, 'Cube 'R 'G 'R 'W 'B 'W,
                          'Cube 'R 'W 'G 'B 'R 'R, 'Cube 'W 'R 'W 'G 'G 'B]]))

So, it seems at least one technique you can use to speed your code up is to use closed type families.

Update on performance numbers as of December 2014

As I've commented earlier, I've tried out these same programs on the GHC 7.9 development line as well, and found some serious performance regressions. This led to a GHC bug ticket which is now resolved to spectacular results: all three solutions involving type families are going to be significantly faster to typecheck on the upcoming GHC 7.10 release!

The new timing figures (as of GHC a225c70) are as follows:

• families-open.hs: 7s
• families-closed.hs: 6.5s
• families-closed-datakinds.hs: 7.5s

Given that I was running these tests without any rigour whatsoever, the above three timings should be taken to be equal, which means I would definitely go with the closed type families + datakinds approach as the most typed and the one producing the nicest output.