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 <[email protected]>:
On Fri, Jun 19, 2009 at 6:17 AM, Matthew Brecknell<[email protected]
> 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
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
