qdunkan at gmail.com
Wed Jun 23 02:05:02 EDT 2010
> Right, I wouldn't use DList for this. Here's an alternative I use:
> data AList a = ANil | ASing a | Append (AList a) (AList a)
> lenA :: AList a -> Int
> lenA ANil = 0
> lenA (ASing _) = 1
> lenA (Append l r) = lenA l + lenA r
> appendA ANil r = r
> appendA l ANil = l
> appendA l r = Append l r
> Note how appendA is strict(ish) and eliminates ANils, so in a writer monad
> it shouldn't build up a space leak. I'm sure you can write toList (don't
> use (++) though).
I hope you're not overestimating me :) I thrashed around for a good
long time trying to get (++) to associate to the right, and then
stumbled across OrdList in ghc, which is apparently just this data
structure, with the addition of 'Many [a]'.
> I'd put the bang on ws:
> m>>= k = WriterT $ do
> (a, w) <- runWriterT m
> (b, w') <- runWriterT (k a)
> let !ws = w `mappend` w'
> return (b, ws)
> The problem with this monad is that >>= isn't tail-recursive, so it will
> cause stack overflows on recursive monadic functions. I suspect that a
> better alternative to the strict writer monad is the strict state monad in
> most cases, because its bind is tail-recursive.
Bang on 'ws' was my first instinct too, but it appeared to have no
effect. I tried to work out a manual reduction for >>= to figure out
exactly what is being forced when, but I got a headache and decided to
do something more relaxing, like watch Primer.
Yes, I suppose Writer's >>= isn't tail recursive... which seems like a
disaster for >>=, since they are usually composed into very long
chains. I know non-tail recursiveness isn't necessarily a disaster in
haskell because of laziness, but it seems like you need just one
strict monad in the stack, like ErrorT or IO and you are no longer
I implemented LoggerT as a strict state monad, and I think it got
better, but there's still a lot of garbage coming from somewhere.
AppendList actually seems slower in the face of repeated appends than
(:) followed by reverse, as I mentioned in the other email. Or it
could be I'm not measuring things right...
>> I also have a situation where -hb shows about 4mb of drag at the most,
>> but when I run with '-hc -hbdrag', I only see 10k peaks. Shouldn't
>> filtering the graph by drag add up to as much drag as when the graph
>> isn't filtered?
> That sounds suspicious. If you can make a self-contained example that
> demonstrates it and create a ticket, that would be a great help.
Ok, I'll try to reduce this to a manageable size. It's the same code
that produces the deadlock while profiling, so perhaps that's related.
thanks again for the advice!
More information about the Glasgow-haskell-users