[Haskell-cafe] list comprehansion performance has hug different

Artyom Kazak artyom.kazak at gmail.com
Tue Jan 29 10:48:31 CET 2013

Junior White <efiish at gmail.com> писал(а) в своём письме 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)))

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

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

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.

More information about the Haskell-Cafe mailing list