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.du...@gmail.com>: > On Fri, Jun 19, 2009 at 6:17 AM, Matthew Brecknell<hask...@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@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