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 javascri…

[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.”

data DontApplyDuplicate a =
  DontApplyDuplicate (S.Set Discount) [Discount] 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

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];

Print Share Comment Cite Upload Translate
APA
Bruno Dias | Sciencx (2024-03-28T15:30:20+00:00) » Modeling algorithms with types. Retrieved from https://www.scien.cx/2021/12/04/modeling-algorithms-with-types/.
MLA
" » Modeling algorithms with types." Bruno Dias | Sciencx - Saturday December 4, 2021, https://www.scien.cx/2021/12/04/modeling-algorithms-with-types/
HARVARD
Bruno Dias | Sciencx Saturday December 4, 2021 » Modeling algorithms with types., viewed 2024-03-28T15:30:20+00:00,<https://www.scien.cx/2021/12/04/modeling-algorithms-with-types/>
VANCOUVER
Bruno Dias | Sciencx - » Modeling algorithms with types. [Internet]. [Accessed 2024-03-28T15:30:20+00:00]. Available from: https://www.scien.cx/2021/12/04/modeling-algorithms-with-types/
CHICAGO
" » Modeling algorithms with types." Bruno Dias | Sciencx - Accessed 2024-03-28T15:30:20+00:00. https://www.scien.cx/2021/12/04/modeling-algorithms-with-types/
IEEE
" » Modeling algorithms with types." Bruno Dias | Sciencx [Online]. Available: https://www.scien.cx/2021/12/04/modeling-algorithms-with-types/. [Accessed: 2024-03-28T15:30:20+00:00]
rf:citation
» Modeling algorithms with types | Bruno Dias | Sciencx | https://www.scien.cx/2021/12/04/modeling-algorithms-with-types/ | 2024-03-28T15:30:20+00:00
https://github.com/addpipe/simple-recorderjs-demo