**Implement an inventory facility**

Implement the following module:

module Inventory : sig type 'a inventory = ('a * int) list val valid : 'a inventory -> bool val sort : 'a inventory -> 'a inventory val union : 'a inventory -> 'a inventory -> 'a inventory val difference : 'a inventory -> 'a inventory -> 'a inventory * 'a inventory val intersects : 'a inventory -> 'a inventory -> bool val length : 'a inventory -> int val distance : 'a inventory -> 'a inventory -> int * int val discriminate : 'a inventory -> 'a inventory -> 'a inventory -> int type ('a, 'b) catalog = ('a * 'b inventory) list val place_order : ('a, 'b) catalog -> 'b inventory -> 'a inventory * 'b inventory end

An `inventory`

is an association list of item/counts.

**a)** `sort`

just sorts an `inventory`

according to its items.

**b)** `valid`

checks that an `inventory`

:

1. is strictly sorted according to its items

2. has only stricly positive item counts

By "strictly" sorted we mean that each item must be strictly greater than its predecessor which verifies item unicity in linear time.

In the following module functions, `assert`

must be systematically used to ensure argument(s) validity where needed.

**c)** `union`

sums two inventories into an augmented `inventory`

.

**d)** `difference`

subtracts one `inventory`

to another `inventory`

. There are two results: `a-b`

and `b-a`

, respectively the items of the first minus the items of the second, and the items of the second minus the items of the first.

**e)** `intersects`

checks if two inventories intersect.

**f)** `length`

returns the sum of item counts.

**g)** `distance`

returns two integers:

1. how many items of the first inventory are in the second inventory

2. how many items of the second inventory are not in the first inventory

**h)** `discriminate`

uses `distance`

to determine whether its second or its third argument is closer to its first argument and returns -1,0,1 accordingly.

**i)** The last function `place_order`

is the big one that justifies all the previous utilities.

A new type `catalog`

is defined that is an association list made available to you, the client, by your supplier. Each key in this list has an associated inventory. The first argument of `place_order`

is the available catalog. The second argument is the exact inventory wanted by the client. The challenge is to compute:

1. the cheapest order, that is the order inventory that includes the wanted inventory with as few extras as possible

2. the extra inventory that will be received and stocked while waiting an usage

The problem ressembles the "Backpack problem", here you can find hints for solving it: A solution to the Backpack Problem.

Otherwise here is the code:

type ('a, 'b) catalog = ('a * 'b inventory) list;;

let place_order cat wanted = let rec helper (cat: ('a,'b) catalog) (wanted: 'b inventory) keys extras = if wanted=[] then keys,extras else let passed = List.find_all (fun (_,inv) -> intersects wanted inv) cat in match passed with | [] -> raise Not_found | (k,inv)::l -> let k_max = ref k and inv_max = ref inv in begin List.iter (fun (k,inv) -> if discriminate wanted inv !inv_max > 0 then begin k_max := k; inv_max := inv end) l; let rest,more = difference wanted !inv_max in helper passed rest (union keys [!k_max,1]) (union more extras) end in helper cat wanted [] [];;