Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
204 lines (157 sloc) 4.49 KB

Haskell at Target

./img/target.png

What is Target?

  • 1806 stores
  • 37 distribution centers
  • Target.com

Stores

./img/target-store-small.jpg ./img/target-store-interior-small.jpg

Distribution Centers

./img/dc-map.png

Distribution Centers

Maximize Experience; Minimize Cost

Demand Uncertainty

./img/dist-small.png

Other Random Variables

  • supply
  • lead times
  • spoilage

Stochastic Optimization

Markov Decision Processes

  • \(S\): set of states
  • \(A\): set of actions
  • \(P(s, a, s^′)\): transition probability
  • \(R(s, s^′)\): reward function

Policy

  • result of optimization
    • function \(S → A\)
    • maximizes expected reward

Techniques

  • dynamic programming (policy iteration)
  • linear programming
  • reinforcement learning
    • features
    • neural nets
  • domain-specific algorithms

In Haskell

data MDP m s a r = 
  MDP { step :: s -> a -> m (r, s) }

type Policy s a = s -> a
  • m: probability monad

Simulation

data Markov m s r = 
  Markov { step :: s -> m (s, r) }

apply :: MDP m s a r 
      -> Policy s a 
      -> Markov m s r

Probability Monad

  • return: constant probability
  • join: flatten distribution of distributions
    • sample sample
    • flatten and multiply

Probability Monad

coin :: Double -> m Bool

biased :: m Bool
biased = do 
  a <- coin 0.5
  if a then coin 0.1 else coin 0.5

Interpretations

  • exhaustive
newtype Dist p a = Dist [(p, a)]
  • sampling (PRNG)
newtype Random a = Random {
  run :: StateT Gen a
}

Free Monads

./img/prac-prob.png

step :: Qty -> Qty -> m (Qty, Money)
step inventory order = do
  let stocked = inventory + order
      cost    = price * order

  buyers <- demand

  let after  = max (stocked - buyers) 0
      sold   = inventory - after
      profit = salePrice * sold

  return (remaining, profit - cost)

Why Haskell?

Types

Embedded Domain-Specific Languages

Composing Contracts

./img/composing-contracts.png

A Haskell Framework

  • modular and typed models
  • separate out solution methods and approximations
    • approximations in solution
    • approximations in model
    • simulate without approximations

Haskell Lessons

Simple Abstractions Scale

  • discrete distribution monad
  • memo-tries
  • functional graph library (fgl)
  • simple optimization algorithms

Types: Good for the Little Things

Types

  • three kinds of item identifiers
  • two kinds of location identifiers
  • config files
  • data transformation inputs/outputs

Type System Extensions

  • powerful
  • risky
  • type inference is crucial
  • simple types, simple APIs

Lenses

Consistency is all I ask!

Difficulties

  • building and deployment
    • Nix: awesome but early adopter
  • compile times
  • network libraries
  • Linux > OS X

Hiring

  • our team is growing!
  • scaling, robustness, performance
    • databases, servers, distributed systems
  • optimization/machine learning

Credits

You can’t perform that action at this time.