Arithmetic expressions with random operators
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.
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
Thanks Francesco, I will try it
8 Haz 2017 16:55 tarihinde "Francesco Ariis"
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.
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/RandomBinar... 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.
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
participants (4)
-
Francesco Ariis -
Ingo Blechschmidt -
Mahmoud Murad -
ok＠cs.otago.ac.nz