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

51–60 of 73 posts

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

#51

Post by dllthomas »

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…

And of course the root of this conversation was mistaken in the first place. The algorithm Bartosz is presenting is the b!/(b-n)! algorithm that just examines each permutation once.

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

#52

Post by mafribe »

dllthomas wrote: post #37
mafribe wrote: post #25

Earlier quoted context omitted.

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.

So you are saying Haskell is not a pure, lazy language?

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

#53

Post by dllthomas »

mafribe wrote: post #52
dllthomas wrote: post #37

Earlier quoted context omitted.

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.

So you are saying Haskell is not a pure, lazy language?

Why is that surprising? Haskell (as typically implemented; I'm slightly less confident about the details of the report) is lazy and pure by default, but that can be violated locally or more globally if you ask for it loud enough. So the language, as a whole, is not pure in the sense required for those theoretical questions to really apply.

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

#54

Post by tome »

mafribe wrote: post #52
dllthomas wrote: post #37

Earlier quoted context omitted.

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.

So you are saying Haskell is not a pure, lazy language?

What do "pure" and "lazy" mean to you?

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

#55

Post by mannykannot »

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

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

#56

Post by mafribe »

tome wrote: post #54
mafribe wrote: post #52

Earlier quoted context omitted.

So you are saying Haskell is not a pure, lazy language?

What do "pure" and "lazy" mean to you?

Lazy is easy: it's call-by-name evaluation, i.e. (lambda x.M)N -> M[N/x] with caching, ie. each argument is evaluated at most once.

Purity is more subtle. I don't think there's an agreed upon definition. [1] essentially ties purity to the equivalency of call-by-name, call-by-need and call-by-value evaluation orders (ignoring divergence and errors). I'm not totally sure that is the right definition.

[1] A. Sabry, What is a Purely Functional Language?

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

#57

Post by mafribe »

dllthomas wrote: post #53
mafribe wrote: post #52

Earlier quoted context omitted.

So you are saying Haskell is not a pure, lazy language?

Why is that surprising? Haskell (as typically implemented; I'm slightly less confident about the details of the report) is lazy and pure by default, but that can be violated locally or more globally if you ask for it loud enough. So the language, as a whole, is not pure in the sense required for those theoretical questions to really apply.

Sure, if you use some of the unsafe stuff ... but what about the safe core of Haskell, do you consider that pure?

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

#58

Post by dllthomas »

mafribe wrote: post #57
dllthomas wrote: post #53

Earlier quoted context omitted.

Why is that surprising? Haskell (as typically implemented; I'm slightly less confident about the details of the report) is lazy and pure by default, but that can be violated locally or more globally if you ask for it loud enough. So the language, as a whole, is not pure in the sense required for those theoretical questions to really apply.

Sure, if you use some of the unsafe stuff ... but what about the safe core of Haskell, do you consider that pure?

What's needed here is ST. It permits local O(1) mutable vectors, while enforcing referential transparency when viewed from outside the runST.

ST is clearly not pure in the sense that theory requires to make "can we implement this algorithm with the same complexity" an interesting question. It seems wrong to consider it part of "the unsafe stuff", however - it doesn't have the same kind of unenforced caveats as unsafePerformIO and unsafeCoerce and similar.

Separately, "the unsafe stuff" is still part of the language as used, and while it's certainly better practice to avoid it when you can, it's silly to exclude it when asking whether it's possible to do something - they are sometimes appropriate.

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

#59

Post by dllthomas »

mafribe wrote: post #56
tome wrote: post #54

Earlier quoted context omitted.

What do "pure" and "lazy" mean to you?

Lazy is easy: it's call-by-name evaluation, i.e. (lambda x.M)N -> M[N/x] with caching, ie. each argument is evaluated at most once. Purity is more subtle. I don't think there's an agreed upon definition. [1] essentially ties purity to the equivalency of call-by-name, call-by-need and call-by-value evaluation orders (ignoring divergence and errors). I'm not totally sure that is the right definition. [1] A. Sabry, What…

The most proximate question here, with respect to purity, is "can you do O(1) mutation (outside of the narrow case of replacing a thunk with its result)?" The theory is far more interesting when we say "no", but the answer in the case of Haskell is "yes".

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

#60

Post by [deleted] »

dllthomas wrote: post #58
mafribe wrote: post #57

Earlier quoted context omitted.

Sure, if you use some of the unsafe stuff ... but what about the safe core of Haskell, do you consider that pure?

What's needed here is ST. It permits local O(1) mutable vectors, while enforcing referential transparency when viewed from outside the runST. ST is clearly not pure in the sense that theory requires to make "can we implement this algorithm with the same complexity" an interesting question. It seems wrong to consider it part of "the unsafe stuff", however - it doesn't have the same kind of unenforced caveats as unsafe…

[deleted]
Post reply on HN