I recently wrote a short post explaining why manual type class desugaring was different to actually writing a type class because of how they are optimised. http://mpickering.github.io/posts/2018-03-20-recordsvstypeclasses.html

I implement 4 different equivalent programs which are all optimised differently. I paste the whole file below as it is not very big.

Implementation 1 is in terms of a type class. Implementation 2 is in terms of explicit dictionary passing. Implementation 3 wraps a dictionary in a type class Implementation 4 wraps a dictionary in a type class with an additional dummy argument.

Naively, a user would expect all 4 implementations to be as fast as each other.

{-# LANGUAGE NoImplicitPrelude #-}
{-# LANGUAGE AllowAmbiguousTypes #-}
module Prop where

import Prelude (Bool(..), (||), (&&))

-- Implementation 1

class Prop r where
  or :: r -> r -> r
  and :: r -> r -> r
  true :: r
  false :: r

instance Prop Bool where
  or = (||)
  and = (&&)
  true = True
  false = False

-- Implementation 2

data PropDict r = PropDict {
  dor :: r -> r -> r
  , dand :: r -> r -> r
  , dtrue :: r
  , dfalse :: r
  }

boolDict = PropDict {
  dor = (||)
  , dand = (&&)
  , dtrue = True
  , dfalse = False }

-- Implementation 3

class PropProxy r where
  propDict :: PropDict r

instance PropProxy Bool where
  propDict = boolDict

-- Implementation 4

class PropProxy2 r where
  propDict2 :: PropDict r
  dummy :: ()

instance PropProxy2 Bool where
  propDict2 = boolDict
  dummy = ()


ors :: Prop r => [r] -> r
ors [] = true
ors (o:os) = o `or` ors os
{-# INLINABLE ors #-}

dors :: PropDict r -> [r] -> r
dors pd [] = dtrue pd
dors pd (o:os) = dor pd o (dors pd os)

pors :: PropProxy r => [r] -> r
pors [] = dtrue propDict
pors (o:os) = dor propDict o (pors os)
{-# INLINABLE pors #-}

porsProxy :: PropProxy2 r => [r] -> r
porsProxy [] = dtrue propDict2
porsProxy (o:os) = dor propDict2 o (porsProxy os)
{-# INLINABLE porsProxy #-}

Then using the 4 different implementations of ors in another module implementations 1 and 4 are fast whilst 2 and 3 are slow.

https://github.com/mpickering/rtcwrao-benchmarks/blob/master/Prop2.hs

benchmarking tc/Implementation 1
time                 3.510 ms   (3.509 ms .. 3.512 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 2.976 ms   (2.886 ms .. 3.060 ms)
std dev              241.1 μs   (195.4 μs .. 293.1 μs)
variance introduced by outliers: 51% (severely inflated)

benchmarking tc/Implementation 2
time                 25.05 ms   (21.16 ms .. 30.43 ms)
                     0.912 R²   (0.849 R² .. 0.984 R²)
mean                 19.18 ms   (16.20 ms .. 21.45 ms)
std dev              5.627 ms   (4.710 ms .. 6.618 ms)
variance introduced by outliers: 89% (severely inflated)

benchmarking tc/Implementation 3
time                 20.06 ms   (15.33 ms .. 23.57 ms)
                     0.856 R²   (0.755 R² .. 0.934 R²)
mean                 18.43 ms   (16.92 ms .. 19.85 ms)
std dev              3.490 ms   (3.003 ms .. 4.076 ms)
variance introduced by outliers: 74% (severely inflated)

benchmarking tc/Implementation 4
time                 3.498 ms   (3.484 ms .. 3.513 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 3.016 ms   (2.935 ms .. 3.083 ms)
std dev              205.7 μs   (162.6 μs .. 261.8 μs)
variance introduced by outliers: 42% (moderately inflated)

I compiled the module with -O2. If I turn off -fno-worker-wrapper and -fno-spec-constr then implementation 3 is also fast. Implementation 2 is always slow.

This ticket is querying what could be done to improve the robustness of these different refactorings.