- Haskell-Cafe - Haskell.org

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

Definition of "tail recursive" wrt Folds
by Mark Spezzano 25 Mar '09

25 Mar '09

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

1 0

Hugs on iPhone
by Kirk Martinez 24 Mar '09

24 Mar '09

I saw Miguel Mitrofanov ( http://www.nabble.com/Hugs-on-the-iphone-td19478992.html) successfully ported Hugs to the iPhone. I'm now wondering if anyone has tried to get Apple's blessing to put this in the App Store? It would be really great to be able to try out little Haskell ideas as the mood strikes. Of course, it's kind of essential to have an editor of some kind for more significant programs... Thanks, Kirk

13 24

ACM Task for C++ and Java programmers in Haskell. How to make code faster?
by Vasyl Pasternak 24 Mar '09

24 Mar '09

Hi! Recently I've found interesting ACM research on C++ and Java efficiency. This task also was been solved on lisp/scheme and is described on http://www.flownet.com/ron/papers/lisp-java/ I tried to solve this task on Haskell but stuck with efficiency problems (approx in 1000 times slower and takes 20 times more memory). I hope the approach, I've used is correct and problem with data structures and implementation. It took more than 81% of time for garbage collection. I tried to use ByteStrings instead of Strings, but unfortunately it didn't help. The entire code I placed on http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2764 The original instructions are on: http://www.flownet.com/ron/papers/lisp-java/instructions.html Dictionary file could be downloaded from: http://www.flownet.com/ron/papers/lisp-java/dictionary. Input data: http://www.flownet.com/ron/papers/lisp-java/input.txt Expected output: http://www.flownet.com/ron/papers/lisp-java/output.txt Could someone help me to make this code faster? I'd like to see solution that will be elegant and fast, without heavy optimizations, that will make code unreadable. Also, if it possible, prepare the program to support SMP parallelism. Very thanks in advance. Hope you'll enjoy this task :) -- Best regards, Vasyl Pasternak

3 4

GHC 6.10.2 - PCap package - affected by the change of Finalizers?
by Neil Davies 24 Mar '09

24 Mar '09

Hi Looks like pcap package needs a little tweek for 6.10.2 - programs compiled with it bomb out with ......error: a C finalizer called back into Haskell. use Foreign.Concurrent.newForeignPtr for Haskell finalizers. Is my interpretation of this error message correct? Cheers Neil

1 0