Generalizing three programs

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Generalizing three programs

Andrew Wagner
Hi everyone,
I've got an interesting problem here I'm trying to solve. Actually,
I've got several problems which seem to have a very similar structure.
I want to find a way to abstract them to solve other problems which
can be thought about in the same way. Here they are:
http://hpaste.org/307
http://hpaste.org/308
http://hpaste.org/309

Note that these are just sketches, the programs aren't done yet. The
general structure of the problem is that an object enters a system,
interacts with different parts of the system, and eventually leaves,
and we want to monitor some statistics about the interaction, so that
we can then make some changes, and run it again, and hopefully improve
it. Thanks in advance for any suggestions!
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Generalizing three programs

Yitzchak Gale
Andrew Wagner wrote:

> I've got several problems which seem to have a very similar structure.
> I want to find a way to abstract them to solve other problems which
> can be thought about in the same way. Here they are:
> http://hpaste.org/307
> http://hpaste.org/308
> http://hpaste.org/309
>
> Note that these are just sketches, the programs aren't done yet. The
> general structure of the problem is that an object enters a system,
> interacts with different parts of the system, and eventually leaves,
> and we want to monitor some statistics about the interaction, so that
> we can then make some changes, and run it again, and hopefully improve
> it.

I like your approach.

You have to watch out for the strictness bug in State/StateT
for this application. Try to keep your functions polymorphic -
using MonadState, as below - so it will be easy to switch
between them later as needed.

I would put a StdGen into the State. Generate the
StdGen in your main and pass it as a parameter to
your initialState function. Access it with something like

getRand :: (Random a, MonadState TheState m) => a -> a -> m a
getRand lo hi = do
  s <- get
  let (r, g) = randomR (lo, hi) $ randomGen s
  put $ s {randomGen = g}
  return r

Then write random distribution functions that look something like

theDistribution :: (MonadState TheState m) => stuff -> m [Event]
theDistribution stuff = do
  ...
  r <- getRand lo hi
  ...

You will probably want to base your random distributions
on the Poisson distribution if you want your simulations
to be realistic. Here are some Wikipedia links:

http://en.wikipedia.org/wiki/Queuing_theory
http://en.wikipedia.org/wiki/Poisson_distribution

Regards,
Yitz
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Generalizing three programs

Heinrich Apfelmus
In reply to this post by Andrew Wagner
Andrew Wagner wrote:

> Hi everyone,
> I've got an interesting problem here I'm trying to solve. Actually,
> I've got several problems which seem to have a very similar structure.
> I want to find a way to abstract them to solve other problems which
> can be thought about in the same way. Here they are:
> http://hpaste.org/307
> http://hpaste.org/308
> http://hpaste.org/309
>
> Note that these are just sketches, the programs aren't done yet. The
> general structure of the problem is that an object enters a system,
> interacts with different parts of the system, and eventually leaves,
> and we want to monitor some statistics about the interaction, so that
> we can then make some changes, and run it again, and hopefully improve
> it. Thanks in advance for any suggestions!

I'm unsure whether it's a good idea to simulate the situations, I'd
prefer a more denotational approach. To that extend,

http://haskell.org/haskellwiki/Research_papers/Data_structures#Probablistic_Programming

may help. Also, I think that in all three problems, the interesting
probability distributions (like the time a random customer has to wait
at the register) - perhaps depending on a chosen scheduling strategy -
can be calculated without sampling. At least, the sampling can be
integrated transparently into the probabilistic functional programming
framework cited above.

Besides, it's not specified what "efficiency" means in the grocery store
problem. The mean time a customer has to wait is not the only possible
cost measure. Customers have different "processing" times and one could
weight mean wait time with that, so that people buying few stuff have
much shorter waiting times than people with several full shopping carts.

Regards,
apfelmus

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: Generalizing three programs

Yitzchak Gale
apfelmus wrote:

> I'm unsure whether it's a good idea to simulate
> the situations, I'd prefer a more denotational
> approach...

Queuing theory is a very large and mature area of
research, with many important applications in
industry. It is not a coincidence that a certain
telephone company named a functional programming
language after Erlang, the founder of queuing
theory.

>From the little I know about it, the problem space
is quite complex. Simple cases can be calculated
easily, but the math starts getting messy very
quickly as the complexity increases.  On the other
hand, simulation is a very powerful tool that is
very generally applicable. Functional programming
languages, such as Er^H^H Haskell, are very good
at this.

> ...it's not specified what "efficiency" means in
> the grocery store problem...  one could weight
> mean wait time with that, so that people buying
> few stuff have much shorter waiting times than
> people with several full shopping carts.

And the relative cost to the supermarket of
various strategies will obviously be a factor in
any real-life application.

> http://haskell.org/haskellwiki/Research_papers/Data_structures#Probablistic_Programming
>
> may help... the sampling can be integrated
> transparently into the probabilistic functional
> programming framework cited above.

Hey, that is a very cute library.

Regards,
Yitz
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: Generalizing three programs

Bjorn Lisper
>Queuing theory is a very large and mature area of
>research, with many important applications in
>industry. It is not a coincidence that a certain
>telephone company named a functional programming
>language after Erlang, the founder of queuing
>theory.

Erlang actually stands for "Ericsson Language". I think the alternative
interpretation is intentional, though.

Björn Lisper
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: Generalizing three programs

Ketil Malde-2
Bjorn Lisper wrote:
> Erlang actually stands for "Ericsson Language". I think the alternative
> interpretation is intentional, though.
>  
According to this:

http://www.erlang.org/pipermail/erlang-questions/1999-February/000098.html

A.K.E. was the actual origin, but with an intentional ambiguity.

-k
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe