Junior White писал(а) в своём письме Tue, 29 Jan 2013 12:40:08 +0300:

Hi Artyom, Thanks! But I don't understand why in the first case "queens' (k-1)" is being recomputed n times?

Because your list comprehension is just a syntactic sugar for concatMap (\q -> concatMap (\qs -> if isSafe q qs then [q:qs] else []) (queens' (k-1))) [1..n] Here `queens' (k-1)` does not depend on `qs`, and therefore it *could* be floated out of the lambda: let queens = queens' (k-1) in concatMap (\q -> concatMap (\qs -> if isSafe q qs then [q:qs] else []) queens) [1..n] But it is an unsafe optimisation. Suppose that the `queens` list is very big. If we apply this optimisation, it will be retained in memory during the whole evaluation, which may be not desirable. That’s why GHC leaves this to you.

So this is a problem in lazy evaluation language, it will not appear in python or erlang, am i right? On Tue, Jan 29, 2013 at 5:54 PM, Junior White wrote:

Thanks again! I understand now. I'll be careful when the next time I use list comprehension.

On Tue, Jan 29, 2013 at 5:48 PM, Artyom Kazak wrote:

...

Junior White писал(а) в своём письме Tue, 29 Jan 2013 12:40:08 +0300:

Hi Artyom,

...

Thanks! But I don't understand why in the first case "queens' (k-1)" is being recomputed n times?

Because your list comprehension is just a syntactic sugar for

concatMap (\q -> concatMap (\qs -> if isSafe q qs then [q:qs] else []) (queens' (k-1))) [1..n]

Here `queens' (k-1)` does not depend on `qs`, and therefore it *could* be floated out of the lambda:

let queens = queens' (k-1) in concatMap (\q -> concatMap (\qs -> if isSafe q qs then [q:qs] else []) queens) [1..n]

But it is an unsafe optimisation. Suppose that the `queens` list is very big. If we apply this optimisation, it will be retained in memory during the whole evaluation, which may be not desirable. That's why GHC leaves this to you.

On 29/01/2013, at 10:59 PM, Junior White wrote:

So this is a problem in lazy evaluation language, it will not appear in python or erlang, am i right?

Wrong. Let's take Erlang: [f(X, Y) || X <- g(), Y <- h()] Does the order of the generators matter here? You _bet_ it does. First off, in all of these languages, it affects the order of the results. Let's take a toy case: g() -> [1,2]. h() -> [a,b]. % constants f(X, Y) -> {X,Y}. % a pair [f(X, Y) || X <- g(), Y <- h()] yields [{1,a},{1,b},{2,a},{2,b}] [f(X, Y) || Y <- h(), X <- g()] yields [{1,a},{2,a},{1,b},{2,b}] Now let's change it by giving g/0 and h/0 (benign) side effects. g() -> io:write('g called'), io:nl(), [1,2]. h() -> io:write('h called'), io:nl(), [a,b]. Generating X before Y yields 'g called' 'h called' 'h called' [{1,a},{1,b},{2,a},{2,b}] Generating Y before X yields 'h called' 'g called' 'g called' [{1,a},{2,a},{1,b},{2,b}] If a function call may yield side effects, then the compiler must not re-order or coalesce calls to that function. This applies to both Erlang and Python (and to SETL, which had set and tuple comprehensions before Erlang, Python, or Haskell were conceived).

The difference is what's called "dynamic programming" (an utterly non-intuitive and un-insightful name).

It was meant to be. The name was chosen to be truthful while not revealing too much to a US Secretary of Defense of whom Bellman wrote: "His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical." (http://en.wikipedia.org/wiki/Dynamic_programming) Every time I try to imagine this guy having Haskell explained to him my brain refuses to co-operate. The word "programming" here is used in the same sense as in "linear programming" and "quadratic programming", that is, "optimisation". "Dynamic" does hint at the multistage decision process idea involved.

The whole point here is to evaluate both lists inside the list comprehension only once. There is a very simple way to accomplish this: [q:qs | let qss = queens' (k-1), q <- [1..n], qs <- qss] Here, queens' (k-1) is only evaluated once, and is shared for all q. (Note: If queens' (k-1) is polymorphic (which it is) and you use -XNoMonomorphismRestriction, then you better add a type annotation to qss to ensure sharing.) Adrian On 2013/01/30 1:51, Doaitse Swierstra wrote:

From the conclusion that both programs compute the same result it can be concluded that the fact that you have made use of a list comprehension has forced you to make a choice which should not matter, i.e. the order in which to place the generators. This should be apparent from your code.

My approach is such a situation is to "define your own generator" (assuming here that isSafe needs both its parameters):

pl `x` ql = [ (p,q) | p <-pl, q <- ql]

queens3 n = map reverse $ queens' n where queens' 0 = [[]] queens' k = [q:qs | (qs, q) <- queens' (k-1) `x` [1..n], isSafe q qs] isSafe try qs = not (try `elem` qs || sameDiag try qs) sameDiag try qs = any (\(colDist,q) -> abs (try - q) == colDist) $ zip [1..] qs

Of course you can make more refined versions of `x`, which perform all kinds of fair enumeration, but that is not the main point here. It is the fact that the parameters to `x` are only evaluated once which matters here.

Doaitse

On Jan 29, 2013, at 10:25 , Junior White mailto:efiish@gmail.com> wrote:

...

Hi Cafe, I have two programs for the same problem "Eight queens problem", the link is http://www.haskell.org/haskellwiki/99_questions/90_to_94. My two grograms only has little difference, but the performance, this is my solution:

-- solution 1------------------------------------------------------------ queens1 :: Int -> [[Int]] queens1 n = map reverse $ queens' n where queens' 0 = [[]] queens' k = [q:qs | q <- [1..n], qs <- queens' (k-1), isSafe q qs] isSafe try qs = not (try `elem` qs || sameDiag try qs) sameDiag try qs = any (?(colDist, q) -> abs (try - q) == colDist) $ zip [1..] qs

-- solution 2-------------------------------------------------------------- queens2 :: Int -> [[Int]] queens2 n = map reverse $ queens' n where queens' 0 = [[]] queens' k = [q:qs | qs <- queens' (k-1), q <- [1..n], isSafe q qs] isSafe try qs = not (try `elem` qs || sameDiag try qs) sameDiag try qs = any (?(colDist,q) -> abs (try - q) == colDist) $ zip [1..] qs

the performance difference is: (set :set +s in ghci) *Main> length (queens1 8) 92 (287.85 secs, 66177031160 bytes) *Main> length (queens2 8) 92 (0.07 secs, 17047968 bytes) *Main>

The only different in the two program is in the first is "q <- [1..n], qs <- queens' (k-1)," and the second is "qs <- queens' (k-1), q <- [1..n]".

Does sequence in list comprehansion matter? And why? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org mailto:Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Wed, Jan 30, 2013 at 5:51 PM, Doaitse Swierstra wrote:

From the conclusion that both programs compute the same result it can be concluded that the fact that you have made use of a list comprehension has forced you to make a choice which should not matter, i.e. the order in which to place the generators. This should be apparent from your code.

My approach is such a situation is to "define your own generator" (assuming here that isSafe needs both its parameters):

pl `x` ql = [ (p,q) | p <-pl, q <- ql]

queens3 n = map reverse $ queens' n where queens' 0 = [[]]

queens' k = [q:qs | (qs, q) <- queens' (k-1) `x` [1..n], isSafe q qs] isSafe try qs = not (try `elem` qs || sameDiag try qs)

sameDiag try qs = any (\(colDist,q) -> abs (try - q) == colDist) $ zip [1..] qs

Of course you can make more refined versions of `x`, which perform all kinds of fair enumeration, but that is not the main point here. It is the fact that the parameters to `x` are only evaluated once which matters here.

Thanks for your reply! I must learn more to fully understand what's going on inside the list comprehension. But when I frist learn Haskell, it says sequence doesn't matter, but now it is a big matter, can compiler do some thing for us? I think this behavior is not friendly to newbies like me, I will take a very long time to work through it.

On Wed, Jan 30, 2013 at 5:32 PM, Junior White wrote:

Thanks for your reply! I must learn more to fully understand what's going on inside the list comprehension. But when I frist learn Haskell, it says sequence doesn't matter, but now it is a big matter, can compiler do some thing for us? I think this behavior is not friendly to newbies like me, I will take a very long time to work through it.

Good point. Being a programmer means having to juggle many hats -- two important ones being the mathematician-hat and the machine-hat, also called declaration and 'imperation' Get only the first and your programs will run very inefficiently. Get only the second and your program will have bugs. Specifically in the case of list comprehensions the newbie needs - to practice thinking of the comprehension like a set comprehension and ignoring computation sequences - to practice thinking of comprehension in terms of map/filter etc ie operationally Both views are needed. Rusi -- http://www.the-magus.in http://blog.languager.org