Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: leaky folding (Daniel Fischer)
2. Re: monad nomad gonad gomad (Ertugrul Soeylemez)
3. Re: = vs <- (Ertugrul Soeylemez)
----------------------------------------------------------------------
Message: 1
Date: Sun, 15 Aug 2010 16:20:54 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] leaky folding
To: [email protected]
Cc: Travis Erdman <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On Sunday 15 August 2010 09:58:49, Travis Erdman wrote:
> in the code below, finalmap seems fast enough ... but it has a space
> leak. otoh, finalmap'rnf runs in constant space, but its performance is
> terrible, at least 4x slower than finalmap.
The performance isn't so bad, actually.
Consider that in each step it has to rnf the entire map. Even for small
maps like this one, that's quite a bit of work (and mostly unnecessary,
because almost everything is already in normal form).
>
> this is a common problem i'm having ... foldl' isn't strict enough, but
> foldl'rnf kills performance.
Firstly, foldl'rnf is a good idea *only* for small structures or if in each
step large parts of the structure are changed. If you change only small
parts of a large structure, you're wasting a lot of work.
Secondly, in this case your problem is a) the choice of a suboptimal data
structure b) a bad choice of functions to manipulate the structure c)
perhaps the lacking strictness of Data.IntMap.
a) STUArray would be better. But that makes itself really felt only for
larger n.
b) that's the biggo
c) Data.IntMap doesn't offer any strict versions of insertWith,
insertWithKey, adjust et al, which would often make it far easier to avoid
space leaks. Data.Map at least offers strict(er) versions of
insertWith[Key].
> And not only with IntMap as the cumulating
> data structure, but others as well.
>
> any ideas on this one?
Sure. See below.
> how can i get a fast fold in constant space?
>
> thanks again,
>
> travis
>
>
> {-# LANGUAGE BangPatterns #-}
>
> import System.Environment
> import Foreign (unsafePerformIO)
> import System.Random.Mersenne
> import Data.List
> import Control.DeepSeq
> import Control.Parallel.Strategies
> import qualified Data.IntMap as IntMap
>
> mersennegen = unsafePerformIO $ newMTGen Nothing
> infrandoms = unfoldr ( Just . splitAt 3) $ map (\x -> abs (x `mod` n))
> (unsafePerformIO $ (randoms mersennegen)::[Int])
Arrrgh! Use of unsafePerformIO in that way makes my head hurt. Pass things
as arguments, please.
>
> n = 200
>
> foldl'rnf :: NFData a => (a -> b -> a) -> a -> [b] -> a
> foldl'rnf f z xs = lgo z xs
> where
> lgo z [] = z
> lgo !z (x:xs) = lgo (runEval (rdeepseq (f z x))) xs
>
> startmap = IntMap.fromDistinctAscList $ zip [0..] [1..n]
That is almost certainly a bad idea. If the map contains a contiguous range
of keys, an array is practically guaranteed to be more appropriate (uses
less memory and is faster to boot).
>
> finalmap x = foldl' g startmap (take x infrandoms)
Okay, that looks reasonable.
> finalmap'rnf x = foldl'rnf g startmap (take x infrandoms)
As stated above, rnf'ing the entire map at each step is a baad idea.
You can get reasonable performance while squashing the leak by splitting
your list in chunks of size k and rnf'ing the map only after each chunk has
been processed.
finalmap'rnf x = foldl'rnf h startmap
(takeWhile (not . null)
(unfoldr (Just . splitAt 200) (take x infrandoms)))
where
h mp lst = foldl' g mp lst
The chunk size should be approximately the size of the map, so that after
each chunk
- a large part of the map has been changed
- no value has been changed too often.
Then rnf'ing the entire map doesn't waste too much work (since only a small
part of the map is already in NF) and no key maps to a too large thunk
(which can cause a space leak with vanilla foldl', though here the problem
is something else).
But, here at least, changing the folded function does better.
>
> g:: IntMap.IntMap Int -> [Int] -> IntMap.IntMap Int
> g !a [x,y,z] = IntMap.adjust (const $ y + (a IntMap.! z) `mod` n) x a
Oy gevalt!
The bang on the map parameter is superfluous since we foldl' anyway, but
that's no big deal.
IntMap.adjust (const val) is not the best if the key at which the map is to
be adjusted is guaranteed to be in the map. Then IntMap.insert is better.
But the difference is small, and if the key is not algorithmically
guaranteed to be present, adjust is cleaner. So the use of adjust is no big
deal either, even if insert is faster here.
What is bad is that you IntMap.adjust (const thunk).
Well, that alone isn't so bad.
What kills you is that the thunk refers to the map.
Thus each modified map contains a reference to the previous version, the
old contents can't be garbage collected, hello space leak (and finally
getting the values involves hopping through old cells).
If you modify a data structure, don't let the modified version contain any
thunks referencing the old. That spells space leak.
With
g a [x,y,z] = let !w = y + (a IntMap.! z) `mod` n
in IntMap.adjust (const w) x a
you're fine with foldl'.
Question by the way, did you really want
y + ((a ! z) `mod` n)
or rather
(y + (a ! z)) `mod` n
?
>
> main = do
> args <- getArgs
> print $ finalmap (read $ head args)
------------------------------
Message: 2
Date: Sun, 15 Aug 2010 16:43:09 +0200
From: Ertugrul Soeylemez <[email protected]>
Subject: [Haskell-beginners] Re: monad nomad gonad gomad
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=US-ASCII
prad <[email protected]> wrote:
> in any case, monads seem to be a rather important concept to getting
> anything done in haskell. for instance, i have a program which is
> generating the output it is supposed to (i can print it), but i can't
> seem to get it into another function and keep getting the error i've
> seen so many times:
>
> Couldn't match expected type `[String]'
> against inferred type `IO [String]'
>
> so it's time to understand them.
In an earlier thread titled "= vs <-" you asked for the difference
between equations (=) and monadic binding (<-). Since you didn't
respond, I'm not sure whether you are reading our posts, but we have
explained in detail the difference. Once understood, you won't get
errors like that anymore.
As a well meant suggestion, you have to actually read the answers to
your posts, even if they are long. Posting essentially the same
questions over and over gets you nowhere.
> besides, the stuff looks rather intriguing and certainly appears to
> take one into computer language design theory.
Not really. A monad is just a way to combine computations. You're
still thinking way too complicated.
> any sources others have found useful would be appreciated as well as
> suggestions on how to proceed through the above.
Well, I have the impression that writing monad tutorials is very hateful
in the Haskell community, independent of the tutorial's actual quality.
That's why I don't like to mention my own one, even though so far I have
only received very positive feedback (thanks to all, who have bothered
to write me).
I think that new tutorials aren't even reviewed by experienced Haskell
users anymore, especially since Brent Yorgey wrote his famous blog entry
[1]. I agree with Brent, but his post had a negative side effect, too.
New tutorials seem to be marked as spam by reflex now by most people.
Personally I find this very unfortunate, and I'm not sure whether that
was Brent's intention.
[1]
http://byorgey.wordpress.com/2009/01/12/abstraction-intuition-and-the-monad-tutorial-fallacy/
Greets,
Ertugrul
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/
------------------------------
Message: 3
Date: Sun, 15 Aug 2010 17:09:17 +0200
From: Ertugrul Soeylemez <[email protected]>
Subject: [Haskell-beginners] Re: = vs <-
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8
Kyle Murphy <[email protected]> wrote:
> Ertugrul Soeylemez <[email protected]> wrote:
> > I think, this is very misleading. Â You never get "out of a monad",
> > you get "into" it, and you can do that whenever you want. Â Remember
> > that the monadic world is inside of the pure world, not the pure
> > world inside of the monadic world. Â In fact, the monadic world is
> > part of it.
>
> Not really, it depends on how you look at things. If you want to use
> the result of something that returns an IO Monad inside of a pure
> function, you really can't do that without in turn making that
> function impure (that is, putting it inside of the IO Monad as well),
> so to one way of looking at it, values (and functions) exist inside
> Monads and with few exceptions are impossible to remove from those
> Monads. You can always embed your pure function inside a non-pure
> function, but the opposite is not true. Most of the monads do provide
> functions like fromJust, and unsafePerformIO (never use this,
> seriously) that can allow you to escape from the monad, but doing so
> is often risky. The monadic world as you put it, really isn't inside
> of the pure world except in theory. From a practical standpoint
> everything exists inside the IO monad at some level, it's just lower
> level functions that are pure (that is, functions can be pure, but at
> some point they MUST be called from the IO monad). I know
> theoretically monads are built on top of pure math, but to me the
> difference between monads as a concept and monads as implemented in
> Haskell, is similar to the difference between proving a program to be
> correct, and actually running it.
I don't agree. The pure world is the evaluation world -- the world,
where you write your program. The impure world is the execution world,
where your program gets run. You cannot pull a value generated by
execution into the evaluation world, because at that point there is no
execution. That's what people refer to as "escaping from IO". Escaping
from IO doesn't make sense in Haskell, hence it's an unsafe thing to do
using hacks like 'unsafePerformIO'.
However, you can give those values a name, either by using (>>=) or by
using '<-' in do-notation. This name can be referred to in the
evaluation world. The monadic world is part of the pure world, because
monads still belong to the evaluation world. The actual execution of
the program is independent and none is inside of the other.
There are lots of ways to pass results of IO actions to pure functions.
Trying to use a value from execution in evaluation is a completely wrong
line of thought. It doesn't make sense, and the types don't fit anyway.
If you need random numbers, pass a random number generator or the random
numbers needed. You can use state and reader monads to make this
passing implicit, if you wish.
Greets,
Ertugrul
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 26, Issue 32
*****************************************
