[Haskell-cafe] list comprehansion performance has hug different

[Junior White]

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 <artyom.kazak at gmail.com>wrote:

> 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)))
>       [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.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130129/39fc89bd/attachment.htm>