Arithmetic expressions with random operators

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

Arithmetic expressions with random operators

Mahmoud Murad
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)).

Any advice or hint? I am relatively new to Haskell. 

Thanks. 



_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Arithmetic expressions with random operators

Francesco Ariis
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)).

Hello Mahmoud,
    probably not the most flexible and posh solution, but datatypes
would do.

    data Exp = EInt Integer
             | Sum  Exp Exp
             | Diff Exp Exp
             | Mult Exp Exp

and then of course you want to write

    evaluate :: Exp -> Integer

and

    write :: Exp -> String
    -- maybe instance Show Exp where

Once you do that, picking Exp constructors at random should not be
difficult.

There are other ways to write a DSL like this (using GADTs, tagless
final style, etc.), each of those expands on/solves a specific problem
(extensibility, etc.); but there is no benefit in complicating your code
if you don't need it.

Does that help?
-F
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Arithmetic expressions with random operators

Mahmoud Murad
Thanks Francesco, I will try it

8 Haz 2017 16:55 tarihinde "Francesco Ariis" <[hidden email]> yazdı:
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)).

Hello Mahmoud,
    probably not the most flexible and posh solution, but datatypes
would do.

    data Exp = EInt Integer
             | Sum  Exp Exp
             | Diff Exp Exp
             | Mult Exp Exp

and then of course you want to write

    evaluate :: Exp -> Integer

and

    write :: Exp -> String
    -- maybe instance Show Exp where

Once you do that, picking Exp constructors at random should not be
difficult.

There are other ways to write a DSL like this (using GADTs, tagless
final style, etc.), each of those expands on/solves a specific problem
(extensibility, etc.); but there is no benefit in complicating your code
if you don't need it.

Does that help?
-F
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Arithmetic expressions with random operators

Ingo Blechschmidt
In reply to this post by Mahmoud Murad
Dear Murad,

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)).

Mark Dominus, well-known in the Perl community, likes this puzzle so
much that he collected several solutions and nonsolutions on his blog
(which I warmly recommend). He also lists several Haskell solutions:

    http://blog.plover.com/math/24-puzzle.html

Ideas for further optimizations of the Haskell solutions (regarding
clarity, elegance, and length of the code) are very much welcome:

 https://gist.github.com/iblech/e21b0a2f5a6e0184ba43c3b1e0e70337

Cheers,
Ingo
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Arithmetic expressions with random operators

Richard A. O'Keefe
In reply to this post by Mahmoud Murad
>
> 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.




_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.