Enhanced Builder Pattern, verified at compile time

Question

Question: can you design a Builder Pattern API which verifies at compile time that every field is set exactly once?

To be eligible, the size of the compiler output should not be exponential in the number of fields. The best solution will be the shortest implementation for a class of 22 fields.

---

Example of a possible surface API in java

Given an class for immutable data structure such as this one:

public class Human {
  private final String name;
  private final Int age;
  private final Double money;

  public Human(String name, Int age, Double money) {
    this.name = name;
    this.age = age;
    this.money = money;
  }

  public String getName() { return name; }
  public Int getAge() { return age; }
  public Double getMoney() { return money; }
}

The goal is to design an API to construct instances this Humain class with the following requirements, checked at compile time (the code in example is just a possible design, you can come up with anything that is equivalent in term of functionally):

• Possible to set parameters in any order:

  Human h = HumanBuilder().withName("n").withMoney(0.15).withAge(1).build();
  Human g = HumanBuilder().withName("n").withAge(1).withMoney(0.15).build();
  

• Possible to set parameters in different places of the code:

  // Given appropriate takesCareOfTheMan & takesCareOfTheMoney methods
  Human h = takesCareOfTheMan(takesCareOfTheMoney(HumanBuilder())).build();
  Human g = takesCareOfTheMoney(takesCareOfTheMan(HumanBuilder())).build();
  

• Impossible to set the same parameter twice:

  // This should not compile:
  // Human h = HumanBuilder().withName("n").withAge(1).withAge(2).withMoney(0.15).build();
  

• Impossible to omit a parameter:

  // This should not compile:
  // Human h = HumanBuilder().withName("n").withMoney(0.15).build();
  

Answer 1

How about something like this, in Haskell:

{-# LANGUAGE GADTs, DataKinds, KindSignatures, StandaloneDeriving #-}
module Builder ( Human', Human, mkHuman, unHuman
               , withName, withAge, withMoney
               ) where

data Optional (b :: Bool) (a :: *) where
    Missing :: Optional False a
    Present :: a -> Optional True a
deriving instance (Show a) => Show (Optional b a)

data Human' b1 b2 b3 where
    MkHuman :: Optional b1 String -> Optional b2 Int -> Optional b3 Double -> Human' b1 b2 b3
deriving instance Show (Human' b1 b2 b3)

type Human = Human' True True True

mkHuman :: Human' False False False
mkHuman = MkHuman Missing Missing Missing

unHuman :: Human -> (String, Int, Double)
unHuman (MkHuman (Present name) (Present age) (Present money)) = (name, age, money)

withName :: String -> Human' False b2 b3 -> Human' True b2 b3
withName name (MkHuman _ age money) = MkHuman (Present name) age money

withAge :: Int -> Human' b1 False b3 -> Human' b1 True b3
withAge age (MkHuman name _ money) = MkHuman name (Present age) money

withMoney :: Double -> Human' b1 b2 False -> Human' b1 b2 True
withMoney money (MkHuman name age _) = MkHuman name age (Present money)

Example usage:

h1, h2 :: Human
h1 = withName "n" . withMoney 0.15 . withAge 1 $ mkHuman
h2 = withName "n" . withAge 1 . withMoney 0.15 $ mkHuman

takesCareOfTheName :: Human' False b2 b3 -> Human' True b2 b3
takesCareOfTheName = withName "John"

-- This doesn't typecheck
h3 :: Human
h3 = withName "newName" h1

-- Neither does this
h4 :: Human
h4 = withName "n" . withAge 1 $ mkHuman

Answer 2

OK here's one, also in Haskell, that is much more extensible: notice how Human is merely a Builder with a specific index of field types.

{-# LANGUAGE GADTs, DataKinds, KindSignatures, StandaloneDeriving #-}
{-# LANGUAGE TypeOperators, TypeFamilies #-}
{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-}
{-# LANGUAGE FlexibleInstances, FlexibleContexts #-}

data Optional (b :: Bool) (a :: *) where
    Missing :: Optional False a
    Present :: a -> Optional True a
deriving instance (Show a) => Show (Optional b a)

data Builder (as :: [*]) (bs :: [Bool]) where
    BNil :: Builder '[] '[]
    BCons :: Optional b a -> Builder as bs -> Builder (a ': as) (b ': bs)

type family Empty_ as where
    Empty_ '[] = '[]
    Empty_ (a ': as) = False ': Empty_ as

type family Full_ as where
    Full_ '[] = '[]
    Full_ (a ': as) = True ': Full_ as

type family Empty builder where
    Empty (Builder as) = Builder as (Empty_ as)

type family Full builder where
    Full (Builder as) = Builder as (Full_ as)

data Tuple as where
    TNil :: Tuple '[]
    (:>) :: a -> Tuple as -> Tuple (a ': as)

infixr 5 :>

fromFull :: Full (Builder as) -> Tuple as
fromFull BNil = TNil
fromFull (BCons (Present x) xs) = x :> fromFull xs

class Buildable as where
    emptyBuilder :: Empty (Builder as)

instance Buildable '[] where
    emptyBuilder = BNil

instance (Buildable as) => Buildable (a ': as) where
    emptyBuilder = BCons Missing emptyBuilder

type Human = Builder '[String, Int, Double]

mkHuman :: Empty Human
mkHuman = emptyBuilder

data Nat = Z | S Nat

data Lookup i as where
    Here :: a -> Lookup Z (a ': as)
    There :: Lookup i as -> Lookup (S i) (a ': as)

type family FillAt i bs where
    FillAt Z (False ': bs) = True ': bs
    FillAt (S i) (b ': bs) = b ': FillAt i bs

class Fill bs (i :: Nat) where
    fill :: Lookup i as -> Builder as bs -> Builder as (FillAt i bs)

instance Fill (False ': bs) Z where
    fill (Here x) (BCons Missing xs) = BCons (Present x) xs

instance (Fill bs i) => Fill (b ': bs) (S i) where
    fill (There k) (BCons x xs) = BCons x $ fill k xs

withName :: (Fill bs Z) => String -> Human bs -> Human (FillAt Z bs)
withName = fill . Here

withAge :: (Fill bs (S Z)) => Int -> Human bs -> Human (FillAt (S Z) bs)
withAge = fill . There . Here

withMoney :: (Fill bs (S (S Z))) => Double -> Human bs -> Human (FillAt (S (S Z)) bs)
withMoney = fill . There . There . Here

unHuman :: Full Human -> (String, Int, Double)
unHuman h = case fromFull h of
    name :> age :> money :> TNil -> (name, age, money)

h1, h2 :: Full Human
h1 = withName "n" . withMoney 0.15 . withAge 1 $ mkHuman
h2 = withName "n" . withAge 1 . withMoney 0.15 $ mkHuman

takesCareOfTheName :: (Fill bs Z) => Human bs -> Human (FillAt Z bs)
takesCareOfTheName = withName "John"

-- -- This doesn't typecheck
-- h3 :: Full Human
-- h3 = withName "newName" h1

-- -- Neither does this
-- h4 :: Full Human
-- h4 = withName "n" . withAge 1 $ mkHuman

Answer 3

import shapeless.<:!<

case class HumanBuilder[A]( name: String, age: Int, money: Double) {

  def withName(name: String)(implicit ev: A <:!< Name): HumanBuilder[A with Name] = this.copy[A with Name](name = name)
  def withAge(age: Int)(implicit ev: A <:!< Age): HumanBuilder[A with Age] = this.copy[A with Age](age = age)
  def withMoney(money: Double)(implicit ev: A <:!< Money): HumanBuilder[A with Money] = this.copy[A with Money](money = money)

  def build()(implicit ev: A =:= Builder with Name with Age with Money): Human = Human(name, age, money)
}

object HumanBuilder {

  def apply(): HumanBuilder[Builder] = HumanBuilder[Builder]("", 0, 0.0)

}

trait Builder
trait Name
trait Age
trait Money

case class Human(name: String, age: Int, money: Double)

Usage

    scala> HumanBuilder().withName("test").withAge(10).withMoney(1.0).build()
res1: puzzle.Human = Human(test,10,1.0)

scala> HumanBuilder().withMoney(3.0).withName("test").withAge(10).build()
res2: puzzle.Human = Human(test,10,3.0)

scala> HumanBuilder().withName("test").withAge(10).withMoney(1.0).withMoney(3.0).build()
<console>:14: error: ambiguous implicit values:
 both method nsubAmbig1 in package shapeless of type [A, B >: A]=> shapeless.package.<:!<[A,B]
 and method nsubAmbig2 in package shapeless of type [A, B >: A]=> shapeless.package.<:!<[A,B]
 match expected type shapeless.<:!<[puzzle.Builder with puzzle.Name with puzzle.Age with puzzle.Money,puzzle.Money]
       HumanBuilder().withName("test").withAge(10).withMoney(1.0).withMoney(3.0).build()
                                                                           ^

scala> HumanBuilder().withName("test").withAge(10).build()
<console>:14: error: Cannot prove that puzzle.Builder with puzzle.Name with puzzle.Age =:= puzzle.Builder with puzzle.Name with puzzle.Age with puzzle.Money.
       HumanBuilder().withName("test").withAge(10).build()

Answer 4

In Scala, you could do the following:

// Or import shapeless._
object Lib {
  trait Nat
  trait Succ[N <: Nat] extends Nat
  trait Z extends Nat
}

object Builder {
  import Lib._

  case class Human(age: Int, name: String, money: Double)

  trait WithAge { def age: Int }
  trait WithName { def name: String }
  trait WithMoney { def money: Double }

  trait HumanBuilder {
    type N <: Nat
    type Next[N0 <: Nat] = this.type { type N = Succ[N0] }

    var age: Int = _
    var name: String = _
    var money: Double = _

    def thiz[A]: A = asInstanceOf[A] // ez typecheck
    def withAge(a: Int): Next[N] with WithAge = { age = a; thiz }
    def withName(n: String): Next[N] with WithName = { name = n; thiz }
    def withMoney(m: Double): Next[N] with WithMoney = { money = m; thiz }
  }

  object HumanBuilder {
    def apply() = new HumanBuilder { type N = Z }

    type WithList = WithAge with WithName with WithMoney
    type WithSize = { type N = Succ[Succ[Succ[Z]]] }

    implicit class Build(hb: HumanBuilder with WithList with WithSize) {
      def build(): Human = Human(hb.age, hb.name, hb.money)
    }
  }
}

Tests:

object Usage extends App {
  import shapeless.test.illTyped
  import Builder._

  illTyped("""
    HumanBuilder()
      .withName("n")
      .withAge(1).withAge(2)
      .withMoney(0.15)
      .build()
  """)

  illTyped("""
    HumanBuilder()
      .withName("n")
      // .withAge(1)
      .withMoney(0.15)
      .build()
  """)

  val h: Human = HumanBuilder()
    .withName("n")
    .withAge(1)
    .withMoney(0.15)
    .build()

  println(h)
}