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

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 :

...

On Fri, Jun 19, 2009 at 6:17 AM, Matthew Brecknell

...

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@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