El Mamun's Caravan
El Mamun's Problem might be one of the oldest known dp problems:
```> module ElMamun where

> import Array
> import List
```
The signature:
```> data Bill = Mult Bill Char Bill |
>             Add  Bill Char Bill |
>             Ext  Bill Char      |
>             Val  Char
>                                 deriving (Show, Eq)
```
The yield grammar:
```> bill :: Bill_Algebra Char answer -> [Char] -> [answer]
> bill alg f = axiom formula where

>   (val, ext, add, mult, h) = alg

>   formula = tabulated (
>             number |||
>             add  <<< formula  ~~-  plus   ~~~  formula  |||
>             mult <<< formula  ~~-  times  ~~~  formula  ... h)

>   number = val <<< digit ||| ext <<< number ~~- digit

>   digit  = char '0' ||| char '1' ||| char '2' ||| char '3' |||
>            char '4' ||| char '5' ||| char '6' ||| char '7' |||
>            char '8' ||| char '9'

>   plus  = char '+'
>   times = char '*'
```
Bind input:
```>   z         = mk f

>   (_,n)     = bounds z
>   char      = char' z
>   tabulated = table n
>   axiom     = axiom' n

```
Enumeration algebra:
```> enum :: Bill_Algebra Char Bill
> enum = (val, ext, add, mult, h) where
>   val       = Val
>   ext       = Ext
>   mult      = Mult
>   h         = id
```
Pretty printing algebra:
```> prettyprint :: Bill_Algebra Char String
> prettyprint = (val, ext, add, mult, h) where
>   val   c     = [c]
>   ext   n c   = n ++ [c]
>   add   x c y = "(" ++ x ++ (c:y) ++ ")"
>   mult  x c y = "(" ++ x ++ (c:y) ++ ")"
>   h           = id
```
Counting algebra:
```> count :: Bill_Algebra Char Int
> count = (val, ext, add, mult, h) where
>   val c       = 1
>   ext n c     = 1
>   add  x t y  = x * y
>   mult x t y  = x * y
>   h []        = []
>   h l         = [sum l]
```
```> buyer :: Bill_Algebra Char Int
>   val c         = decode c
>   ext n c       = 10*n + decode c
>   add  x t y    = x + y
>   mult x t y    = x * y
>   h []          = []
>   h l           = [minimum l]
```
The seller's algebra:
```> seller :: Bill_Algebra Char Int
> seller = (val, ext, add, mult, h) where
>   val c       = decode c
>   ext n c     = 10*n + decode c
>   add  x c y  = x + y
>   mult x c y  = x * y
>   h []        = []
>   h l         = [maximum l]
```
Computation time:
```> time :: Bill_Algebra Char Int
> time = (val, ext, add, mult, h) where
>   val c       = 0
>   ext n c     = 0
>   add  x c y  = max x y + 2
>   mult x c y  = max x y + 5
>   h []        = []
>   h l         = [minimum l]
```
Algebra type:
```> type Bill_Algebra alphabet answer = (
>   alphabet -> answer,                       -- val
>   )
```
Algebra cross product:
```> infix ***
> (***) :: Eq answer1 =>