Modeling algorithms with types

[First draft]

Things get so much easier when you try
to understand how the types work together
to accomplish some work.

In this article, we are going to model
a system that apply discounts using many
strategies.

I'm going to use Haskell and javascript.
haskell (or ocaml if you like) is great to visualize
what's going on the type level...

We can starting by trying to think
on the simplest way to accomplish the job.

We can start by using a simple subtraction (-).

applyDiscount :: Float -> Float -> Float
applyDiscount price discount = price - discount

let price = 10.0
    discounts = [1.0, 4.0]
    finalPrice = 5.0
in foldl applyDiscount price discounts == finalPrice

const applyDiscount = (price, discount) => price - discount;

const price = 10.0;
const discounts = [1.0, 4.0];
const finalPrice = 5.0;

discounts.reduce(applyDiscount, price) == finalPrice;

Then we can clarify what which Float means
on the type specifiction...

type Price = Float
type Discount = Float

applyDiscount :: Price -> Discount -> Price
applyDiscount price discount = price - discount

Now we have Price -> Discount -> Price which means
"given a Price and a Discount, it returns back the price
after the discount"...and that means, in this case,
that the Price acts like an accumulator!

With this information, we can now improve applyDiscount
to be more generic.

class ApplyDiscount a where
  applyDiscount :: a -> Discount -> a

applyDiscounts :: ApplyDiscount a => a -> [Discount] -> a
applyDiscounts = foldl applyDiscount

In this case, in typescript, it should be the same as...

interface ApplyDiscount {
  applyDiscount(discount: Discount): ApplyDiscount;
}

Now, we just need to create instances for each a!

newtype ApplyAll = ApplyAll Price
  deriving (Show, Eq)

instance ApplyDiscount a where
  applyDiscount (ApplyAll p) d = ApplyAll (p - d)

let discounts = [1.0, 4.0]
    strategy = ApplyAll 10.0
    finalPrice = ApplyAll 5.0
in foldl applyDiscount strategy discounts == finalPrice

class ApplyAll {
  constructor(x) { this.price = x; }
  applyDiscount(d) { return new ApplyAll(this.price - d); }
}

const discounts = [1.0, 4.0];
const strategy = new ApplyAll(10.0);
const finalPrice = 5.0;

const applyDiscount =
  (strategy, discount) => strategy.applyDiscount(discount);

discounts.reduce(applyDiscount, strategy).price == finalPrice;

Now we have our first strategy! ApplyAll
just apply all discounts available,
and this is a great first strategy.

A new requirement has arived!

Now, we have too apply all discounts,
but we are not going to let the final price
goes negative.

newtype ApplyAllNoNegative = ApplyAllNoNegative Price
  deriving (Show, Eq)

instance ApplyDiscount a where
  applyDiscount (ApplyAllNoNegative p) d =
    ApplyAllNoNegative (max 0 (p - d))

let discounts = [5.0, 5.0]
    strategy = ApplyAllNoNegative 8.0
    finalPrice = ApplyAllNoNegative 0.0
in foldl applyDiscount strategy discounts == finalPrice

class ApplyAllNoNegative {
  constructor(x) { this.price = x; }
  applyDiscount(d) {
    const price = Math.max(0, this.price - d);
    return new ApplyAllNoNegative(price);
  }
}

const discounts = [1.0, 4.0];
const strategy = new ApplyAllNoNegative(10.0);
const finalPrice = 5.0;

discounts.reduce(applyDiscount, strategy).price == finalPrice;

Too easy!

Our next task is to:

"If it goes negative, just collect
all discounts that we couldn't apply,
otherwise return the final price."

newtype CollectDiscountWhenGoesNegative =
  Applying Price |
  NotApplied [Discount]
  deriving (Show, Eq)

instance ApplyDiscount a where
  applyDiscount (Applying p) d =
    let x = p - d
    in if x >= 0 then
         Applying x
       else
         NotApplied [d]
  applyDiscount (NotApplied ls) c =
    NotApplied (c : ls)

let discounts = [5.0, 5.0]
    strategy = Applying 10.0
    finalPrice = Applying 0.0
in foldl applyDiscount strategy discounts == finalPrice

let discounts = [5.0, 8.0]
    strategy = Applying 10.0
    finalPrice = NotApplied [8.0]
in foldl applyDiscount strategy discounts == finalPrice

// Don't do this! It's just to help visualize what's going on.
class CollectDiscountWhenGoesNegative {}

class NotApplied extends CollectDiscountWhenGoesNegative {
  constructor(x) { this.list = x; }
  applyDiscount(d) { retun new this(this.list.concat([d])); }
}

class Applying extends CollectDiscountWhenGoesNegative {
  constructor(x) { this.price = x; }
  applyDiscount(d) {
    const price = this.price - d;
    if (price >= 0) {
      return new Applying(price);
    } else {
      return new NotApplied([d]);
    }
  }
}

const discounts = [1.0, 4.0];
const strategy = new Applying(10.0);
const finalPrice = 5.0;

discounts.reduce(applyDiscount, strategy).price == finalPrice;

const discounts = [1.0, 4.0];
const strategy = new Applying(1.0);

discounts.reduce(applyDiscount, strategy).list == [4.0];

It's really easy to work with this. If
the discount goes negative, we know exactly
which discounts were not applied to mark on
the frontend as feedback.

Our final task is:

"It must not apply duplicate discounts,
and it must keep the duplicated to send as feedback
to the user. Also, it must use the previous strategies
so we can allow it goes negative or not."

type AlreadyAppliedDiscounts = S.Set Discount
type DuplicatedDiscounts = [Discount]

data DontApplyDuplicate a =
  DontApplyDuplicate AlreadyAppliedDiscounts DuplicatedDiscounts a
  deriving (Show, Eq)

dadup = DontApplyDuplicate

instance (ApplyDiscount a) => ApplyDiscount (DontApplyDuplicate a) where
  applyDiscount (DontApplyDuplicate ls xs s) d =
    if S.member d ls then
      dadup ls (d : xs) s
    else
      dadup (S.insert d ls) xs $ applyDiscount s d

-- could be a `Default` instance
new = dadup S.empty []

let discounts = [5.0, 5.0]
    strategy = new (Applying 10.0)
    finalPrice = dadup (S.fromList [5.0]) [5.0] (Applying 5)
in foldl applyDiscount strategy discounts == finalPrice

let discounts = [5.0, 8.0]
    strategy = Applying 10.0
    finalPrice = NotApplied [8.0]
in foldl applyDiscount strategy discounts == finalPrice

class DontApplyDuplicate {
  constructor(strategy) {
    this.usedDiscounts = new Set();
    this.duplicated = [];
    this.strategy = strategy;
  }
  applyDiscount(d) {
    if (this.usedDiscount.has(d)) {
     this.duplicated.push(d);
     return this;
    }
    this.usedDiscount.add(d);
    this.strategy = this.strategy.applyDiscount(d)
    return this;
  }
}

const discounts = [1.0, 4.0];
const strategy = new DontApplyDuplicate(new Applying(10.0));
const finalPrice = 5.0;

discounts.reduce(
  (p, d) => p.applyDiscount(d),
  strategy
).price == finalPrice;

const discounts = [1.0, 1.0, 4.0, 6.0];
const strategy = new DontApplyDuplicate(new Applying(10.0));

const {
  usedDiscounts,
  duplicated,
  strategy: { list },
} = discounts.reduce(applyDiscount, strategy);

usedDiscount = [1.0, 4.0];
duplicated = [1.0];
list = [6.0];