March 2009 - Haskell-Cafe

How to increment an Int in Haskell (stack overflow issue)
by Tim Bauer 25 Mar '09

25 Mar '09

I have a program that is currently blowing out the stack, Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize' to increase it. I am pretty sure I get to the end of the computation that increments various statistic counters (lazily?) and only when I go to print them out at the end, do things fail. I have state monad transformer (StateT) that is keeping the counters among other things. The counters are stored in a pair within a larger data structure. > data AState s a = AS { ... > asStats :: (Int,Int) > ... > } to increment them I initially just simply applied either of > incFst, incSnd :: (Int,Int) -> (Int,Int) > incFst (x,y) = (x + 1,y) > incSnd (x,y) = (x, y + 1) to the current pair. I thought this was safe since primitive arithmetic was strict, but when I go to print the counter out (evaluate it), it blows apart. I first decided this was because the addition was somehow not strict and I was getting: (0 + 1 + 1 ...millions of times..., ....) and the evaluation of that first coordinate blew things apart. So I tried was adding a strictness annotation to the arguments. > incFst (!x,y) = (x + 1,y) > incSnd (x,!y) = (x, y + 1) No dice (I also tried using seq manually all over the place to no avail). Just for fun, I tried both of > incFst _ = (0,0) > incSnd _ = (0,0) and > incFst (x,y) = (x,y) > incSnd (x,y) = (x,y) The problem goes away. But maybe an optimization is covering up the crime. So I tried > incFst (x,y) = (y,x) > incSnd (x,y) = (y,x) And indeed this again crashes. Any hints as to what is going on? If it is relevant, here is my code to access the counter within the state monad > countFst :: StateT (AState s a) IO () > countFst = modify $ \as -> as{asStats = incFst (asStats as)} and the monad transformer I am using is > import Control.Monad.State.Strict

4 3

ghci + hopengl
by Rafael Cunha de Almeida 25 Mar '09

25 Mar '09

Hello, I'm writing a program for plotting vectorial functions and maybe something else in the future. My goal is to be able to have the following usage: Prelude> :l Galo.hs Prelude Galo> show3Dvec (\t -> (t, t, 0)) [0.0,0.01 .. 1.0] * shows graph * Prelude Galo> show3Dvec (\t -> (t, t**2, 0)) [0.0,0.01 .. 1.0] * shows new graph * I already done something, the main module can be found here: http://github.com/aflag/galo/blob/0a54a53db0f66384cfc0775f12582931d0fb4205/… The whole project is found here: http://github.com/aflag/galo/tree/master I think mainLoop is somehow responsible to exit the whole thing. I tried to even call that function through forkIO. But didn't work quite well: my terminal started behaving really weird after I closed the window. Could you explain me what is going on and what should I look into for understanding how to solve the issue? []'s Rafael

4 4

Whats the use of "!"
by Harsh Verma 25 Mar '09

25 Mar '09

I have seen ! added in front of many values, is it related to strict evaluation? Please elaborate on it. TIA, gimli _________________________________________________________________ Windows Live Messenger. Multitasking at its finest. http://www.microsoft.com/india/windows/windowslive/messenger.aspx

2 1

central european functional programming school
by Roman Cheplyaka 25 Mar '09

25 Mar '09

Hi, I'm interested in 3rd central european functional programming school[1]. Maybe some haskellers attended previous CEFPs and want to share (or already shared) some experience? Who also is going to attend or participate in this year's CEFP? 1. http://plcportal.inf.elte.hu/en/tfp_cefp_2009/Pages/default.aspx -- Roman I. Cheplyaka :: http://ro-che.info/ "Don't let school get in the way of your education." - Mark Twain

1 0

Re: Exception handling in numeric computations
by John Lato 25 Mar '09

25 Mar '09

> Jake McArthur <jake(a)pikewerks.com> writes: > >> Xiao-Yong Jin wrote: >> | The problem is that there will be many functions using such >> | a function to invert a matrix, making this inversion >> | function return Either/Maybe or packing it in a monad is >> | just a big headache. >> >> I disagree. If you try to take the inverse of a noninvertable matrix, >> this is an *error* in your code. Catching an error you created in pure >> code and patching it with chewing gum it is just a hack. A monadic >> approach (I'm putting Either/Maybe under the same umbrella for brevity) >> is the only solution that makes any sense to me, and I don't think it's >> ugly as you are making it out to be. >> > > Then, why is 'div' not of type 'a -> a -> ArithExceptionMonad a' ? > Why does it throws this /ugly/ /error/ when it is applied to > 0? Why is it not using some beautiful > 'ArithExceptinoMonad'? Is 'Control.Exception' just pure > /ugly/ and doesn't make any sense? > >> >> | It is impractical to use method (a), >> | because not every function that uses 'invMat' knows how to >> | deal with 'invMat' not giving an answer. So we need to use >> | method (b), to use monad to parse our matrix around. >> | >> |> > invMat :: Matrix -> NumericCancerMonad Matrix >> | >> | It hides the exceptional nature of numerical computations >> | very well, but it is cancer in the code. Whenever any >> | function wants to use invMat, it is mutated. This is just >> | madness. You don't want to make all the code to be monadic >> | just because of singularities in numeric calculation. >> >> For functions that don't know or don't care about failure, just use fmap >> or one of its synonyms. >> >> ~ scalarMult 2 <$> invMat x >> >> See? The scalarMult function is pure, as it should be. There is no >> madness here. > > Of course, 'scalarMult' is invulnerable and free of monad. > But take a look at the following functions, > >> f1 = scalarMult 2 . invMat >> f2 l r = l `multMat` invMat r >> ff :: Matrix -> Matrix -> YetAnotherBiggerMonad Matrix >> ff x y = do let ff' = f1 x + f2 y >> put . (addMat ff') . f1 << get >> tell $ f2 ff' >> when (matrixWeDontLike (f1 ff') $ >> throwError MatrixWeDontLike >> return $ scalarMult (1/2) ff' > > Yes, I know, it's not really complicate to rewrite the above > code. But, what do I really gain from this rewrite? Apologies if this discussion has moved on, but I wanted to comment on this. You gain correctness. Any functions that need to be rewritten in this case should be rewritten anyway, because they're already wrong. Your function ff can fail for certain inputs. This statement: >> | It is impractical to use method (a), >> | because not every function that uses 'invMat' knows how to >> | deal with 'invMat' not giving an answer. So we need to use >> | method (b), to use monad to parse our matrix around. is conceptually wrong. What does it mean to multiply the inverse of a non-invertible matrix by a scalar? Obviously this is nonsensical. If a computation can fail (as this can), the type of the function should reflect it. The above functions >> f1 = scalarMult 2 . invMat >> f2 l r = l `multMat` invMat r should be f1 :: Matrix -> Maybe Matrix f1 = fmap (scalarMult 2) . invMat f2 :: Matrix -> Matrix -> Maybe Matrix f2 l r = fmap (multMat l) $ invMat r Of course these could be written with Control.Applicative as well: f1 m = scalarMult 2 <$> invMat m f2 l r = multMat l <$> invMat r >> ff :: Matrix -> Matrix -> YetAnotherBiggerMonad Matrix >> ff x y = let ff' = f1 x + f2 y ... in scalarMult (1/2) ff' (I think you may be missing an argument to f2 here.) This computation can fail as well, if the constituent parts fail. The separate parts can be combined with applicative style: ff :: Matrix -> Matrix -> Maybe Matrix ff x y = scalarMult (1/2) <$> ( (+) <$> f1 x <*> f2 y) Compare this to the same code using monadic Maybe: ff :: Matrix -> Matrix -> Maybe Matrix ff x y = do x' <- f1 x y' <- f2 y scalarMult (1/2) $ x' + y' You gain clarity and brevity. Both examples are shorter and easier to understand because you aren't messing with all the plumbing of error handling using exceptions, although I find the Applicative version especially clear. If you would like to keep track of why a computation failed, then use Either instead of Maybe with the Left carrying a reason for failure (e.g. NonInvertibleMatrix) Finally, you gain safety. When you use a function f1 :: Matrix -> Matrix, you can be assured that you will get an actual, meaningful answer. If you use a function f2 :: Matrix -> Maybe Matrix, you know that you may not get a meaningful answer, and it is simple to handle at the appropriate level of your code. I (and many other Haskell users) find this to be conceptually cleaner than throwing dynamic exceptions or using undefined. Incidentally, this is one reason why many experienced Haskellers like the applicative style. It allows you to express your computations without obtrusive error handling mixed in. It's also more general than monads, so can be applied in more instances. div (and other non-total functions in the Prelude like head), are also frequently considered ugly hacks. Just because we're stuck with something from H98 doesn't mean that it's necessarily good or elegant (the fail monad method and Functor not being a superclass of Monad come to mind). In some ways FP has moved on since Haskell was formalized. There is an alternative approach that I believe was suggested by somebody else on the list: newtype InvMatrix = Invert {unWrap :: Matrix} then you can do invertMatrix :: Matrix -> Maybe InvMatrix invertMatrix = fmap Invert . invMat If you put these in a separate module and export InvMatrix, unwrap, and invertMatrix, but not Invert, then the only way to create an InvMatrix is with invertMatrix, so any data of type InvMatrix is guaranteed to be invertible (and inverted from what you used to create it). Then your ff function becomes: ff :: InvMatrix -> InvMatrix -> Matrix the final value of the function could be InvMatrix if you can prove that it's invertible after your operations (although to be efficient, this would require exporting the Invert constructor and a proof from the programmer). This keeps ff pure; you don't even have to deal with Maybe (although there are other ramifications to doing this that should be considered). John

2 1

Re: generalized shuffle
by Manlio Perillo 25 Mar '09

25 Mar '09

oleg(a)okmij.org ha scritto: > Hello! > >> The reason is that in a project I need to extract random elements >> from a list (and I need to extract a lot of them), and using "normal" >> methods [1] seems to be rather inefficient. Note that I have used an incorrect term, sorry. What I need, in detail, is to: Given a population of 100480507 elements, extract 17770 random samples, where each sample has a size between 1 and 480189. Yes, it is again my Netflix Prize project; here I'm trying to write a program to generate the entire training data set using random data. >> [1] by normal method I mean: extract a random number, in the range >> [0, n] (where n is the length of the sequence), and get the element >> indexed by that number. > > BTW, have you tried to use Data.IntMap? That is, put the sequence into > an IntMap (each element being indexed by its index) and then extract > elements at random; IntMap seems to be quite efficient... > This should be ok if I need independent random choices from a population, but I need random samples, instead, sorry for the confusion. Do you think that it is possible to further optimize your tree structure? Or to use IntMap, instead? > Cheers, > Oleg Thanks Manlio

1 0

STM orElse semantics
by Tom Davies 25 Mar '09

25 Mar '09

I'm not 100% clear on the behaviour of the STM function orElse. The documentation says: "Compose two alternative STM actions (GHC only). If the first action completes without retrying then it forms the result of the orElse. Otherwise, if the first action retries, then the second action is tried in its place. If both actions retry then the orElse as a whole retries." What is the definition of retrying in "If the first action completes without retrying then..." -- does it mean only explicitly retrying via the retry function, or does it include a retry caused by a write conflict at commit time of the first action? That is, if the first action could complete, but doesn't simply due to interference from another transaction, does orElse run the second action, or rerun the first?

2 1

The votes are in!
by Eelco Lempsink 25 Mar '09

25 Mar '09

The results of the Haskell logo competition are in! You can view them at http://www.cs.cornell.edu/w8/~andru/cgi-perl/civs/ results.pl?num_winners=1&id=E_d21b0256a4fd5ed7&algorithm=beatpath Congratulations Jeff Wheeler! I'll set up a page with the results visibile. -- Regards, Eelco Lempsink

18 24

Are there performant mutable Arrays in Haskell?
by Brettschneider, Matthias 25 Mar '09

25 Mar '09

Hey There, I am trying to write a hash-algorithm that in fact is working, but as you might have guessed the problem is the performance :) At the moment I am 40 times worse than the same implementation in C. My problem is, I need mutable arrays which are the heart of that hash. The algorithm is round-based and within each round I need the value of certain positions in that array. At the moment I work with an unboxed ST-Array at the crucial part --- snip --- test list = runSTUArray $ do a_arr <- newListArray (0, 1752) list let round i = do ain <- readArray a_arr (i-n) at0 <- readArray a_arr (i-t0) at1 <- readArray a_arr (i-t1) at2 <- readArray a_arr (i-t2) at3 <- readArray a_arr (i-t3) at4 <- readArray a_arr (i-t4) let li = ls $ (i - n) mod 16 ri = rs $ (i - n) mod 16 writeArray a_arr i $ (step4 li) . (step3 ri) . (step2 at1 at2 at3 at4) $ (step1 ain at0 i) mapM_ round [n..(n+t-1)] return a_arr --- snap --- I also played around with peekElemOff and pokeElemOff, but this isn't much faster. It took ~30sec with my Haskell-Code while the C-implementation need only ~1sec. Is there someone who may have some hints for me, what I can do better, or just lead me in the right direction? :) Thanks a lot in advance -- Matthias

5 7

Re: [Haskell-cafe] Definition of "tail recursive" wrt Folds
by Tammo Spalink (司馬泰) 25 Mar '09

25 Mar '09

wikipedia is your friend... http://en.wikipedia.org/wiki/Fold_(higher-order_function) Tammo 2009/3/25 Mark Spezzano <mark.spezzano(a)chariot.net.au>: > Hi, > > > > Just looking at the definitions for foldr and foldl I see that foldl is > (apparently) tail recursive while foldr is not. > > > > Why? > > > > Is it because foldl defers calling itself until last whereas foldr evaluates > itself as it runs? > > > > What, strictly speaking, is the definition of ”tail recursive” as opposed to > just “recursive”? > > > > Cheers, > > > > Mark Spezzano > > > > No virus found in this outgoing message. > Checked by AVG. > Version: 7.5.557 / Virus Database: 270.11.27/2021 - Release Date: 24/03/2009 > 4:00 PM > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > >

1 0