Using Monads in C++ to Solve Constraints: 1. The List Monad
bartoszmilewski.com
Using Monads in C++ to Solve Constraints: 1. The List Monad
1–10 of 73 posts
Re: Using Monads in C++ to Solve Constraints: 1. The List Monad
#2This method is really inefficient. There are b! / (b - n)! ways to choose n of b unique numbers, whereas this solution is O(b^n).
That being said, it's still fast enough for this example.
Also, Python solution along the same lines:
import itertoolsdef
def valueOf(*values, base=10):
v = 0
for v in itertools.accumulate(values, lambda a,b: a*base+b):
pass
return v
def solve():
for s,e,n,d,m,o,r,y in itertools.permutations(range(10), r=8):
if valueOf(s,e,n,d) + valueOf(m,o,r,e) == valueOf(m,o,n,e,y):
yield (s,e,n,d),(m,o,r,e),(m,o,n,e,y)
Re: Using Monads in C++ to Solve Constraints: 1. The List Monad
#3This method is really inefficient. There are b! / (b - n)! ways to choose n of b unique numbers, whereas this solution is O(b^n). That being said, it's still fast enough for this example. Also, Python solution along the same lines: import itertoolsdef def valueOf(*values, base=10): v = 0 for v in itertools.accumulate(values, lambda a,b: a*base+b): pass return v def solve(): for s,e,n,d,m,o,r,y in itertools.permutatio…
I assume/hope that the big idea for part 2 is that this setup allows for efficiently pruning impossible sub solutions and will result in an optimal algorithm.
Why would you write an algorithm in C++ if the runtime will be bad?
Re: Using Monads in C++ to Solve Constraints: 1. The List Monad
#4This method is really inefficient. There are b! / (b - n)! ways to choose n of b unique numbers, whereas this solution is O(b^n). That being said, it's still fast enough for this example. Also, Python solution along the same lines: import itertoolsdef def valueOf(*values, base=10): v = 0 for v in itertools.accumulate(values, lambda a,b: a*base+b): pass return v def solve(): for s,e,n,d,m,o,r,y in itertools.permutatio…
I assume/hope that the big idea for part 2 is that this setup allows for efficiently pruning impossible sub solutions and will result in an optimal algorithm. Why would you write an algorithm in C++ if the runtime will be bad?
He even says explicitly "(never mind how we deal with uniqueness)" in the solution section and has already acknowledged that there are only around 2 million combinations to check.
ETA since he mentions the implementation is a translation of this Haskell implementation: http://blog.jle.im/entry/unique-sample-drawing-searches-with... presumably the uniqueness is done by updating the list of remaining possibilities for selection each time a new value is selected.
Re: Using Monads in C++ to Solve Constraints: 1. The List Monad
#5"Once you internalize the many-worlds approach to programming, the implementation is pretty straightforward." are you serious? this is why people don't take Haskell seriously.
Re: Using Monads in C++ to Solve Constraints: 1. The List Monad
#6This method is really inefficient. There are b! / (b - n)! ways to choose n of b unique numbers, whereas this solution is O(b^n). That being said, it's still fast enough for this example. Also, Python solution along the same lines: import itertoolsdef def valueOf(*values, base=10): v = 0 for v in itertools.accumulate(values, lambda a,b: a*base+b): pass return v def solve(): for s,e,n,d,m,o,r,y in itertools.permutatio…
Here's one possible implementation of valueOf:
import numpy as np
def valueOf(*v):
return sum( v * np.power(10,range(len(v)))[::-1] )
> valueOf( 2,3,4 ) # => 234
Re: Using Monads in C++ to Solve Constraints: 1. The List Monad
#7This method is really inefficient. There are b! / (b - n)! ways to choose n of b unique numbers, whereas this solution is O(b^n). That being said, it's still fast enough for this example. Also, Python solution along the same lines: import itertoolsdef def valueOf(*values, base=10): v = 0 for v in itertools.accumulate(values, lambda a,b: a*base+b): pass return v def solve(): for s,e,n,d,m,o,r,y in itertools.permutatio…
> This method is really inefficient.
That's what I've noticed with Haskellers. They have a tendency to write really slow code and don't have a clear idea of the execution model behind what they write down.
A while ago I asked in #haskell for translations into Haskell of the following C++ code:
This should be easy. The algorithm is right in front of you. There should not be a lot of thinking in transcribing an algorithm into Haskell. But most of them wrote down something with a fold which turned what is an O(m*n) algorithm in time and O(n) in space into something like O(m^n) in space and time. The only one who got close to the C++ implementation was one who used a lot of State monads.
Then, of course, there was someone who pointed me out to a radically different algorithm written in Haskell that I think is only O(n+m) in both space and time. I haven't been able to understand this other algorithm yet.
Re: Using Monads in C++ to Solve Constraints: 1. The List Monad
#8This method is really inefficient. There are b! / (b - n)! ways to choose n of b unique numbers, whereas this solution is O(b^n). That being said, it's still fast enough for this example. Also, Python solution along the same lines: import itertoolsdef def valueOf(*values, base=10): v = 0 for v in itertools.accumulate(values, lambda a,b: a*base+b): pass return v def solve(): for s,e,n,d,m,o,r,y in itertools.permutatio…
> This method is really inefficient. That's what I've noticed with Haskellers. They have a tendency to write really slow code and don't have a clear idea of the execution model behind what they write down. A while ago I asked in #haskell for translations into Haskell of the following C++ code: http://codepad.org/sQTXhqC2 This should be easy. The algorithm is right in front of you. There should not be a lot of thinkin…
> They have a tendency to write really slow code and don't have a clear idea of the execution model behind what they write down.
Of course, this isn’t unique to Haskellers. ;)
Granted, reasoning about performance in Haskell is still a relatively young art, and there aren’t many of us who are experienced with it.
Re: Using Monads in C++ to Solve Constraints: 1. The List Monad
#9This method is really inefficient. There are b! / (b - n)! ways to choose n of b unique numbers, whereas this solution is O(b^n). That being said, it's still fast enough for this example. Also, Python solution along the same lines: import itertoolsdef def valueOf(*values, base=10): v = 0 for v in itertools.accumulate(values, lambda a,b: a*base+b): pass return v def solve(): for s,e,n,d,m,o,r,y in itertools.permutatio…
> This method is really inefficient. That's what I've noticed with Haskellers. They have a tendency to write really slow code and don't have a clear idea of the execution model behind what they write down. A while ago I asked in #haskell for translations into Haskell of the following C++ code: http://codepad.org/sQTXhqC2 This should be easy. The algorithm is right in front of you. There should not be a lot of thinkin…
The responses you got on IRC don't necessarily represent Haskell best practice (or even good practice). Most people probably have better things to do than translate random toy programs from C++.
Certain highly stateful algorithms may be difficult to translate into Haskell, in the same way that certain highly structural or lazy algorithms may be difficult to translate to C++.
I'm curious if your time complexity analyses are accurate, given that you (admittedly) did not understand the faster algorithm. You could be getting tripped up by laziness.
In general, I've found that most production Haskell code is quite fast, in both big-O and absolute terms.
Re: Using Monads in C++ to Solve Constraints: 1. The List Monad
#10Earlier quoted context omitted.
> This method is really inefficient. That's what I've noticed with Haskellers. They have a tendency to write really slow code and don't have a clear idea of the execution model behind what they write down. A while ago I asked in #haskell for translations into Haskell of the following C++ code: http://codepad.org/sQTXhqC2 This should be easy. The algorithm is right in front of you. There should not be a lot of thinkin…
The responses you got on IRC don't necessarily represent Haskell best practice (or even good practice). Most people probably have better things to do than translate random toy programs from C++. Certain highly stateful algorithms may be difficult to translate into Haskell, in the same way that certain highly structural or lazy algorithms may be difficult to translate to C++. I'm curious if your time complexity analys…
Spoken like a true Haskell fanboy. Why don't you give it a shot, OP has posted the code.