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

[Thomas Hartman]

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
>