Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

bartoszmilewski.com

Post reply on HN
Print view View original

31–40 of 73 posts

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

#31

Post by TheLoneWolfling »

codygman wrote: post #29
TheLoneWolfling wrote: post #27

Earlier quoted context omitted.

And if you're willing to do that on every upgrade of the compiler or anything that may affect the compiler's exact execution path.

Performance regressions in GHC are taken seriously as far as I've seen. It's not that big of a deal since you should test/profile your program on any compiler upgrade. If you see any regressions, just post it to the ghc mailing list and it will probably be solved for you since it's much needed regression feedback/data.

That's good to know. Though I will note that I don't use Haskell. (Haven't had the time to properly learn it, and keep getting frustrated by minor things when I try to dabble with it.)

That being said, I used to think that about Java as well - and then the whole substring thing happened.

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

#32

Post by TheLoneWolfling »

TheLoneWolfling wrote: post #28
bpicolo wrote: post #21

Earlier quoted context omitted.

If you don't need other bases you can just string join them. : P

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.

Whoops. Miscopied. the second `=10` shouldn't be there.

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

#33

Post by TheLoneWolfling »

im3w1l wrote: post #23
TheLoneWolfling wrote: post #2

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.permutatio…

from functools import reduce def valueOf(*values, base=10): return reduce(lambda x,y: x*base+y, values)

Doesn't work with a zero-length input (although that's easily fixed).

That being said, that's much cleaner. Thanks!

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

#34

Post by im3w1l »

TheLoneWolfling wrote: post #33
im3w1l wrote: post #23

Earlier quoted context omitted.

from functools import reduce def valueOf(*values, base=10): return reduce(lambda x,y: x*base+y, values)

Doesn't work with a zero-length input (although that's easily fixed). That being said, that's much cleaner. Thanks!

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.

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

#35

Post by TheLoneWolfling »

im3w1l wrote: post #34
TheLoneWolfling wrote: post #33

Earlier quoted context omitted.

Doesn't work with a zero-length input (although that's easily fixed). That being said, that's much cleaner. Thanks!

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.

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.

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

#36

Post by tome »

jordigh wrote: post #17
acconsta wrote: post #16

Earlier quoted context omitted.

The Haskell Wiki has what seems like a clean and efficient implementation: https://wiki.haskell.org/Edit_distance

Yeah, it's got a completely different algorithm along the diagonal of the matrix. That's the O(m+n) algorithm. I still haven't been able to understand it. But that's not the point. The point is that Haskellers have a hard time translating an algorithm that's right in front of them and instead of writing down an O(m*n) algorithm they instinctively do O(m^n). This whole "many-worlds" approach of the original article is…

It seems a bit of a broad generalisation to say "Haskellers have a hard time translating an algorithm" based on who happened to be on the IRC channel at the time and decided to answer a challenge from a random C++ programmer who turned up.

Anyway, Haskell is perfectly decent at implementing your algorithm, and imperative algoritms in general. He's a more-or-less direct translation

    http://lpaste.net/132519
There's extra noise related to wrapping and unwrapping mutable cells which I could tidy up if I had the time, otherwise it's essentially identical.

In any case the author of the post in question, Bartosz Milewski, is an expert in C++ and not particularly an expert in Haskell, so your point seems misdirected.

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

#37

Post by dllthomas »

mafribe wrote: post #25
jordigh wrote: post #17

Earlier quoted context omitted.

Yeah, it's got a completely different algorithm along the diagonal of the matrix. That's the O(m+n) algorithm. I still haven't been able to understand it. But that's not the point. The point is that Haskellers have a hard time translating an algorithm that's right in front of them and instead of writing down an O(m*n) algorithm they instinctively do O(m^n). This whole "many-worlds" approach of the original article is…

Haskellers have a hard time translating an algorithm that's right in front of them That's no surprise: it is an open problem if this is possible in general. Some time ago Pippenger [1] showed that some programs cannot be transliterated into pure strict functional languages without suffering a slowdown. Later, Bird et al [2] show that the example given by Pippenger to show the slowdown really depends on strictness, an…

It's an open problem whether it can be translated into a pure, lazy language without an asymptotic slowdown. It's not at all an open problem as to whether it can be implemented in Haskell. The algorithm is mutating vectors - the direct translation is to use ST, and will have the same asymptotic behavior as the C++ version.

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

#38

Post by dllthomas »

TheLoneWolfling wrote: post #2

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.permutatio…

Satisfying arbitrary constraints is often exponential (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.

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

#39

Post by TheLoneWolfling »

dllthomas wrote: post #38
TheLoneWolfling wrote: post #2

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.permutatio…

Satisfying arbitrary constraints is often exponential ( 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.

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.

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

#40

Post by jordigh »

tome wrote: post #36
jordigh wrote: post #17

Earlier quoted context omitted.

Yeah, it's got a completely different algorithm along the diagonal of the matrix. That's the O(m+n) algorithm. I still haven't been able to understand it. But that's not the point. The point is that Haskellers have a hard time translating an algorithm that's right in front of them and instead of writing down an O(m*n) algorithm they instinctively do O(m^n). This whole "many-worlds" approach of the original article is…

It seems a bit of a broad generalisation to say "Haskellers have a hard time translating an algorithm" based on who happened to be on the IRC channel at the time and decided to answer a challenge from a random C++ programmer who turned up. Anyway, Haskell is perfectly decent at implementing your algorithm, and imperative algoritms in general. He's a more-or-less direct translation http://lpaste.net/132519 There's ext…

> It seems a bit of a broad generalisation to say "Haskellers have a hard time translating an algorithm" based on who happened to be on the IRC channel at the time and decided to answer a challenge from a random C++ programmer who turned up.

I'm not a "C++ programmer". I'm just a programmer. I happened to have the algorithm written in C++, but I could quite easily have written it in pseudocode.

I got about 6 responses in 20 minutes. Four of those were O(m^n). Yes, I think this is quite indicative that Haskellers have a hard time writing performant code.

Post reply on HN