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

11–20 of 73 posts

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

#11

Post by TheLoneWolfling »

beambot wrote: post #6
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…

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.

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.

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

#12

Post by GFK_of_xmaspast »

jordigh wrote: post #7
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…

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

If edit distance is bounded there appear to be algorithms that are linear in the input size:

http://en.wikipedia.org/wiki/Edit_distance and http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levensht...

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

#13

Post by alricb »

tezka wrote: post #10
wyager wrote: post #9

Earlier quoted context omitted.

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.

Shriram Krishnamurti to the rescue! Here's a memoized version in scheme: http://blog.racket-lang.org/2012/08/dynamic-programming-vers...

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

#14

Post by RodericDay »

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…

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.

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

#15

Post by tjradcliffe »

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

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.

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

#16

Post by acconsta »

jordigh wrote: post #7
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…

> 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 Haskell Wiki has what seems like a clean and efficient implementation:

https://wiki.haskell.org/Edit_distance

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

#17

Post by jordigh »

acconsta wrote: post #16
jordigh wrote: post #7

Earlier 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 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 also leading to a very inefficient algorithm.

The abstractions Haskellers prefer lead them towards slow code.

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

#19

Post by kenko »

jordigh wrote: post #7
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…

> 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 blog post explicitly says that the C++ is a translation of Haskell code, and links to the (efficient) Haskell original.

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

#20

Post by [deleted] »

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…

[deleted]
Post reply on HN