Data types a la carte — over-engineered?


April 2019


6 time


I'm working through Swiertstra's 2008 paper. I'm up to Section 3 eval addExample, just before 'Automating injections'. And boy! does it need automating.

Is it just me, or is the whole thing over-engineered? Compare this in the paper

   addExample :: Expr (Val :+: Add)
   addExample = In (Inr (Add (In (Inl (Val 118))) (In (Inl (Val 1219)))))

With this made-up example

addExample3 :: Expr (CoPr (CoPr Val Add) (CoPr Add Mul))
addExample3 = In (Inl (Inr (Add (In (Inl (Inl (Val 333))))
                                  (In (Inr (Inl (Add (In (Inl (Inl (Val 303))))
                                                     (In (Inl (Inl (Val 330))))
                                  )   )    )    )
                  )   )    )

(Using type constructor CoPr instead of :+: in the paper. I've used layout there just to make sure I'm balancing my parens. This is as bad as LISP.)

eval addExample3  -- ===> 966 [correct]

So it works to have type constructor/functor Add appearing twice in the Expr. There's something wrong in the design here, because the CoProduct just needs to be a set of functors. Rather than using Swierstra's :+: I could use a type-level list(?) I notice the references don't include the HList paper, even though that was some 4 years earlier.

For each 'atomic' type constructor (Val, Add) there needs to be both a Functor instance, which is essentially determined from its arity; and an Eval instance, which makes it do something useful; so later in the paper there's a Render instance for each functor, to do something else useful.

For addExample and addExample3 above, GHC can infer the type. But when it gets to the smart (so-called) constructors, you need to supply the CoProduct type of the Expr. Can't those constructors (there's one for each atomic constructor) build the Expr type as it goes? (If the needed type constructor already appears, use Inl/Inr to get to it; if it doesn't appear, append it to the end of the CoProduct and generate the Inl/r.)

(I started looking at a-la-Carte because it's claimed the approach doesn't fit with Overlapping Instances. Just not so: it was easy to adapt it to use overlaps in Hugs. That's the least of the difficulties.)

0 answers