[Haskell-cafe] Arithmetic expressions with random operators

[ok at cs.otago.ac.nz]

>
> On Thu, Jun 08, 2017 at 04:03:55PM +0300, Mahmoud Murad wrote:
>> I have the following problem, I want to randomly generate arithmetic
>> expressions based on a number, for example:
>> if I have n = 3, then the expression must have 3 operators like this
>> (4)*(((3+5)-2)).
>

I don't seem to have the original message in my mailbox,
so my response may be inappropriate.  Generating random
arithmetic expressions in Haskell has two parts: how to
generate random arithmetic expressions at all, and how to
do it in Haskell.

Assuming that "arithmetic expressions" means expressions
using numbers and the four binary operations + - * / (or
possibly the exponentiation operator as well), the basic
problem reduces to
 * generate a random binary tree with n internal nodes
 * assign random numbers to the leaves
 * assign random operators to the internal nodes
The last two subtasks are pretty easy.  This leaves
generating random binary trees as the main problem.

This paper may help:
http://www.cs.otago.ac.nz/staffpriv/mike/Papers/RandomGeneration/RandomBinaryTrees.pdf

There's a survey paper at
http://www.sis.uta.fi/cs/reports/A-1998-3.ps.Z
and the Atkinson/Sack approach does seem to be pretty good,
at least if you want to make *large* expressions.

This only matters if you want all expressions to be equally
likely.  You may not.