10 ms·

Using Monads in C++ to Solve Constraints: 1. The List Monad

61 points by andrzejsz 11y ago

TheLoneWolfling 11y ago
This 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) (If anyone knows of a better way to do valueOf, let me know)
- Bootvis 11y ago
  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?
  - kenko 11y ago
    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-list-and-statet 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.
- beambot 11y ago
  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 Also, in python 2.7, I don't think you can put a named variable proceeding a wildcard? At least, that doesn't work for me, so I left it out.
  - TheLoneWolfling 11y ago
    That is a) hauling in an awfully big external library for something that should be relatively trivial, b) inefficient (you're replacing a single multiplication by 10 and addition per digit with O(log x) multiplications and an addition per digit, assuming np.power uses a decent exponentiation algorithm), and c) if anything, less readable than my version. To put it simply, I don't see an improvement with that version. And Python 3 has some improvements w.r.t. wildcard arguments.
    - bpicolo 11y ago
      If you don't need other bases you can just string join them. : P
      - TheLoneWolfling 11y ago
        That's actually how I started, and `int` has a base parameter. But it's still relatively verbose, due to Python's whole "join-only-takes-strings" thing: def valueOf(*values, base=10): return int("".join(map(str, values)), base=10) Not to mention it's doing a whole lot of unnecessary work.
        TheLoneWolfling 11y ago
        Whoops. Miscopied. the second `=10` shouldn't be there.
- jordigh 11y ago
  > 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 http://codepad.org/sQTXhqC2 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.
  - evincarofautumn 11y ago
    > 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.
  - wyager 11y ago
    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.
    - tezka 11y ago
      Spoken like a true Haskell fanboy. Why don't you give it a shot, OP has posted the code.
- RodericDay 11y ago
  this was mine, brutey import itertools as it a = 'dog' b = 'food' c = 'tasty' letters = sorted(set(a+b+c)) for combo in it.permutations('0123456789', len(letters)): mapping = dict(zip(letters, combo)) if len(c) > max(len(a), len(b)) and mapping[c[0]] is '0': continue f = lambda string: int(''.join(map(mapping.get, string))) n1, n2, n3 = map(f, [a, b, c]) if n1 + n2 == n3: print( mapping ) print( n1, n2, n3 ) break seems haskell friendly given all the mappings, but not in the way that the blogpost did it. but also not with that big nested loop either.
- deleted 11y ago
  [deleted]
- im3w1l 11y ago
  from functools import reduce def valueOf(*values, base=10): return reduce(lambda x,y: x*base+y, values)
  - TheLoneWolfling 11y ago
    Doesn't work with a zero-length input (although that's easily fixed). That being said, that's much cleaner. Thanks!
    - im3w1l 11y ago
      Sure. But it isn't clear to me it should work with zero length input. Not working is consistent with the builtin int, int("") throws an exception.
      - TheLoneWolfling 11y ago
        It's straight from the definition of an integer. An integer is defined as sum(i=0 to n) d_n * base^n. A number with zero digits is just the empty sum, which is canonically defined to be zero. I'll also note that int() returns 0.
- dllthomas 11y ago
  Satisfying arbitrary constraints is often exponential (http://en.wikipedia.org/wiki/Boolean_satisfiability_problem http://en.wikipedia.org/wiki/Boolean_satisfiability_problem). I'd certainly be interested in seeing more efficient implementations, but the approach taken by the example Haskell code (and duplicated in your Python) is substantially more efficient than the example non-Haskell code provided in the article.
  - TheLoneWolfling 11y ago
    I know about BSAT / BIP / ILP / MLP and the problems thereof in the general case. However, this doesn't mean we have to punt the easy cases just because there are hard cases.
    - dllthomas 11y ago
      It certainly doesn't mean we have to punt the easy cases, but it seems inappropriate to lambaste the current solution without establishing that we are in fact looking at an easy case. That no one seems to have produced (or pointed at) an asymptotically better solution in any language, I think that's some small evidence that there isn't such a solution and substantially more evidence that it's not easy to find.
      - TheLoneWolfling 11y ago
        There's an easy better method: assign variables starting from the lower order digits, greedily check correctness, and skip over all permutations with that prefix if it fails. Although I don't know how one would go about proving or disproving if this is asymptotically better or just a (substantial) constant-factor speedup.
        dllthomas 11y ago
        Oh! I had misread your original comment to be, "There are b! / (b - n)! ways to choose n of b unique numbers, [so] this solution is O(b^n)." You were contrasting! I believe that b!/(b-n)! is asymptotically the same class as b^n (whether we're varying b or n), hence my confusion. I had initially skimmed the article, and assumed he was already handling uniqueness. With the correct definition of StateL, the solution presented is equivalent to what you describe here, but apparently that definition is deferred to a future article. The idea would be that, for StateL, for_each would pick one value and pass that value to the lambda, interpreting the result in a context where the sel only sees the remaining values in the list.
- mannykannot 11y ago
  This post should be read in the context of the related posts in Milewski's highly informative blog. The goal is not to show a solution, it is to demonstrate some aspects of monads, and in this particular case, that the concept is not confined to Haskell or functional languages.
- dllthomas 11y ago
  Note that the later parts of this series havd been published, and in fact the definition of StateL does inforce uniqueness as expected, in a way that makes the proposed solution O(n!). For details, look at the first code block in the "The Client Side" section, here: http://bartoszmilewski.com/2015/05/18/using-monads-in-c-to-solve-constraints-3-the-tale-of-two-monads/ http://bartoszmilewski.com/2015/05/18/using-monads-in-c-to-s...
awruef 11y ago
"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.
tjradcliffe 11y ago
It is disingenous in the extreme to ask, "So what’s all this talk about mutation and state? Well, who said you can’t have state in functional programming?" when the very first line of the very first hit on "functional programming mutation state" is the Wikipedia article on functional programming, which says: "In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data." -- https://en.wikipedia.org/wiki/Functional_programming https://en.wikipedia.org/wiki/Functional_programming So the answer to the question "Who said you can't have state in functional programming?" is: "Every introduction to functional programming ever." This is why people hate Haskell and make fun of Haskellers. In their quest to appear more clever than the rest of us, they engage in utterly disingenous rhetoric. Which is too bad, because I'm pretty sure they are actually more clever than the rest of us--certainly more clever than me--and don't need this nonsense. Haskell is an amazingly cool language, and I've talked to people at meetups who are using it for interesting things, and learning a bit of it myself has been an interesting and educational challenge. But getting around to learning it took five years longer than it should have because I was so put off by the rhetorical nonsense the language community engages in.
- jjnoakes 11y ago
  "Having state" != "Changing-state and mutable data". 5 years?
zeroonetwothree 11y ago
I would just use std::next_permutation (or equivalent partial permutation from a library). This produces pretty clean code.
taeric 11y ago
Do you get bonus points for knowing that these are Alphametics? And covered in ridiculous detail in volume 4A of The Art of Computer Programming? I'm curious how the solutions there stack up to what is in mind here.

61 points by andrzejsz 11y ago

This 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) (If anyone knows of a better way to do valueOf, let me know)

Bootvis 11y ago
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?
- kenko 11y ago
  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-list-and-statet 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.
beambot 11y ago
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 Also, in python 2.7, I don't think you can put a named variable proceeding a wildcard? At least, that doesn't work for me, so I left it out.
- TheLoneWolfling 11y ago
  That is a) hauling in an awfully big external library for something that should be relatively trivial, b) inefficient (you're replacing a single multiplication by 10 and addition per digit with O(log x) multiplications and an addition per digit, assuming np.power uses a decent exponentiation algorithm), and c) if anything, less readable than my version. To put it simply, I don't see an improvement with that version. And Python 3 has some improvements w.r.t. wildcard arguments.
  - bpicolo 11y ago
    If you don't need other bases you can just string join them. : P
    - TheLoneWolfling 11y ago
      That's actually how I started, and `int` has a base parameter. But it's still relatively verbose, due to Python's whole "join-only-takes-strings" thing: def valueOf(*values, base=10): return int("".join(map(str, values)), base=10) Not to mention it's doing a whole lot of unnecessary work.
      - TheLoneWolfling 11y ago
        Whoops. Miscopied. the second `=10` shouldn't be there.
jordigh 11y ago
> 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 http://codepad.org/sQTXhqC2 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.
- evincarofautumn 11y ago
  > 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.
- wyager 11y ago
  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.
  - tezka 11y ago
    Spoken like a true Haskell fanboy. Why don't you give it a shot, OP has posted the code.
RodericDay 11y ago
this was mine, brutey import itertools as it a = 'dog' b = 'food' c = 'tasty' letters = sorted(set(a+b+c)) for combo in it.permutations('0123456789', len(letters)): mapping = dict(zip(letters, combo)) if len(c) > max(len(a), len(b)) and mapping[c[0]] is '0': continue f = lambda string: int(''.join(map(mapping.get, string))) n1, n2, n3 = map(f, [a, b, c]) if n1 + n2 == n3: print( mapping ) print( n1, n2, n3 ) break seems haskell friendly given all the mappings, but not in the way that the blogpost did it. but also not with that big nested loop either.
deleted 11y ago
[deleted]
im3w1l 11y ago
from functools import reduce def valueOf(*values, base=10): return reduce(lambda x,y: x*base+y, values)
- TheLoneWolfling 11y ago
  Doesn't work with a zero-length input (although that's easily fixed). That being said, that's much cleaner. Thanks!
  - im3w1l 11y ago
    Sure. But it isn't clear to me it should work with zero length input. Not working is consistent with the builtin int, int("") throws an exception.
    - TheLoneWolfling 11y ago
      It's straight from the definition of an integer. An integer is defined as sum(i=0 to n) d_n * base^n. A number with zero digits is just the empty sum, which is canonically defined to be zero. I'll also note that int() returns 0.
dllthomas 11y ago
Satisfying arbitrary constraints is often exponential (http://en.wikipedia.org/wiki/Boolean_satisfiability_problem http://en.wikipedia.org/wiki/Boolean_satisfiability_problem). I'd certainly be interested in seeing more efficient implementations, but the approach taken by the example Haskell code (and duplicated in your Python) is substantially more efficient than the example non-Haskell code provided in the article.
- TheLoneWolfling 11y ago
  I know about BSAT / BIP / ILP / MLP and the problems thereof in the general case. However, this doesn't mean we have to punt the easy cases just because there are hard cases.
  - dllthomas 11y ago
    It certainly doesn't mean we have to punt the easy cases, but it seems inappropriate to lambaste the current solution without establishing that we are in fact looking at an easy case. That no one seems to have produced (or pointed at) an asymptotically better solution in any language, I think that's some small evidence that there isn't such a solution and substantially more evidence that it's not easy to find.
    - TheLoneWolfling 11y ago
      There's an easy better method: assign variables starting from the lower order digits, greedily check correctness, and skip over all permutations with that prefix if it fails. Although I don't know how one would go about proving or disproving if this is asymptotically better or just a (substantial) constant-factor speedup.
      - dllthomas 11y ago
        Oh! I had misread your original comment to be, "There are b! / (b - n)! ways to choose n of b unique numbers, [so] this solution is O(b^n)." You were contrasting! I believe that b!/(b-n)! is asymptotically the same class as b^n (whether we're varying b or n), hence my confusion. I had initially skimmed the article, and assumed he was already handling uniqueness. With the correct definition of StateL, the solution presented is equivalent to what you describe here, but apparently that definition is deferred to a future article. The idea would be that, for StateL, for_each would pick one value and pass that value to the lambda, interpreting the result in a context where the sel only sees the remaining values in the list.
mannykannot 11y ago
This post should be read in the context of the related posts in Milewski's highly informative blog. The goal is not to show a solution, it is to demonstrate some aspects of monads, and in this particular case, that the concept is not confined to Haskell or functional languages.
dllthomas 11y ago
Note that the later parts of this series havd been published, and in fact the definition of StateL does inforce uniqueness as expected, in a way that makes the proposed solution O(n!). For details, look at the first code block in the "The Client Side" section, here: http://bartoszmilewski.com/2015/05/18/using-monads-in-c-to-solve-constraints-3-the-tale-of-two-monads/ http://bartoszmilewski.com/2015/05/18/using-monads-in-c-to-s...

awruef 11y ago

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

tjradcliffe 11y ago

It is disingenous in the extreme to ask, "So what’s all this talk about mutation and state? Well, who said you can’t have state in functional programming?" when the very first line of the very first hit on "functional programming mutation state" is the Wikipedia article on functional programming, which says: "In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data." -- https://en.wikipedia.org/wiki/Functional_programming https://en.wikipedia.org/wiki/Functional_programming So the answer to the question "Who said you can't have state in functional programming?" is: "Every introduction to functional programming ever." This is why people hate Haskell and make fun of Haskellers. In their quest to appear more clever than the rest of us, they engage in utterly disingenous rhetoric. Which is too bad, because I'm pretty sure they are actually more clever than the rest of us--certainly more clever than me--and don't need this nonsense. Haskell is an amazingly cool language, and I've talked to people at meetups who are using it for interesting things, and learning a bit of it myself has been an interesting and educational challenge. But getting around to learning it took five years longer than it should have because I was so put off by the rhetorical nonsense the language community engages in.

jjnoakes 11y ago
"Having state" != "Changing-state and mutable data". 5 years?

zeroonetwothree 11y ago

I would just use std::next_permutation (or equivalent partial permutation from a library). This produces pretty clean code.

taeric 11y ago

Do you get bonus points for knowing that these are Alphametics? And covered in ridiculous detail in volume 4A of The Art of Computer Programming? I'm curious how the solutions there stack up to what is in mind here.