[Haskell-cafe] Re: Need some help with an infinite list

[Miguel Mitrofanov]

Well, I'm hardly the one knowing GHC internals, but...

In allstrings you continue calling "strings" with same arguments again  
and again. Don't fool yourself, it's not going to automagically  
memorize what you were doing before. In fact, I'd expect much more  
speed loss. If you increase your "wanted" constant, you'll probably  
notice it.

Anyway, you allstrings2 is much nicer - the problem you're solving has  
nothing to do with numbers, so "map whatever [1..]" seems out of place.

On 20 Jun 2009, at 22:16, Thomas Hartman wrote:

> could someone explain sharing?
>
> In the code below, allstrings2 is 6X as fast as allstrings. I assume
> because of sharing, but I don't intuitively see a reason why.
>
> can someone give me some pointers, perhaps using debug.trace or other
> tools (profiling?) to show where the first version is being
> inefficient?
>
>
> ***********
>
> letters = ['a'..'z']
>
> strings 0 = [""]
> strings n = [ c : s | c <- letters, s <-  strings (n-1) x ]
>
> allstrings = concat $ map strings [1..]
>
> allstrings2 = let sss = [""] : [ [ c:s | c <- letters, s <- ss ] |  
> ss <- sss ]
>              in concat $ tail sss
>
> t = allstrings !! wanted
> t2 = allstrings2 !! wanted
>
> wanted = (10^2)
>
>
> 2009/6/18 Lee Duhem <lee.duhem at gmail.com>:
>> On Fri, Jun 19, 2009 at 6:17 AM, Matthew Brecknell<haskell at brecknell.org 
>> > wrote:
>>> On Thu, 2009-06-18 at 23:57 +0800, Lee Duhem wrote:
>>>> [...] I have prepared a blog post for how
>>>> I worked out some of these answers, here is the draft of it, I  
>>>> hope it
>>>> can help you too.
>>>
>>> Nice post! Certainly, pen-and-paper reasoning like this is a very  
>>> good
>>> way to develop deeper intuitions.
>>>
>>>>       Answer 1 (by Matthew Brecknell):
>>>>
>>>>       concat $ tail $ iterate (map (:) ['a' .. 'z'] <*>) [[]]
>>>
>>> I actually said "tail $ concat $ iterate ...", because I think the
>>> initial empty string is logically part of the sequence. Tacking  
>>> "tail"
>>> on the front then produces the subsequence requested by the OP.
>>
>> Yes, I changed your solution from "tail $ concat $ iterate ..." to
>> "concat $ tail $ iterate ...", because I think cut useless part out  
>> early
>> is good idea, forgot to mention that, sorry.
>>
>>>
>>> I should have given more credit to Reid for this solution. I'm  
>>> always
>>> delighted to see people using monadic combinators (like  
>>> replicateM) in
>>> the list monad, because I so rarely think to use them this way.  
>>> Sadly,
>>> my understanding of these combinators is still somewhat stuck in IO,
>>> where I first learned them. I never would have thought to use <*>  
>>> this
>>> way if I had not seen Reid's solution first.
>>
>> Actually, I first figure out how Reid's solution works, then figure  
>> out yours.
>> After that, I found, for me, your solution's logic is easier to  
>> understand,
>> so I take it as my first example. As I said at the end, or as I'll
>> said at the end,
>> Reid' solution and yours are the same (except effective)
>>
>> lee
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe