[Haskell-cafe] Efficiency question
I'm pretty new to Haskell, so forgive me if my question is due to my non-functional way of thinking... I have the following code: module Main where main = print solution solution = solve 100 solve d = countUniqueFractions d 2 1 0 canBeSimplified (a,b) = gcd a b 1 countUniqueFractions stopD currentD currentN count | currentD stopD = count | currentN == currentD = countUniqueFractions stopD (currentD + 1) 1 count | canBeSimplified (currentN, currentD) = countUniqueFractions stopD currentD (currentN+1) count | otherwise = countUniqueFractions stopD currentD (currentN+1) (count + 1) When I run this code, I get a stack overflow. I don't understand why. Could anyone explain please? -- View this message in context: http://www.nabble.com/Efficiency-question-tf3823154.html#a10823572 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficiency question
rwiggerink: I'm pretty new to Haskell, so forgive me if my question is due to my non-functional way of thinking... I have the following code: module Main where main = print solution solution = solve 100 solve d = countUniqueFractions d 2 1 0 canBeSimplified (a,b) = gcd a b 1 countUniqueFractions stopD currentD currentN count | currentD stopD = count | currentN == currentD = countUniqueFractions stopD (currentD + 1) 1 count | canBeSimplified (currentN, currentD) = countUniqueFractions stopD currentD (currentN+1) count | otherwise = countUniqueFractions stopD currentD (currentN+1) (count + 1) When I run this code, I get a stack overflow. I don't understand why. Could anyone explain please? Lazy accumulators. Did you try compiling with ghc -O2 ? -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficiency question
On Sun, 27 May 2007, Evil Bro wrote: I'm pretty new to Haskell, so forgive me if my question is due to my non-functional way of thinking... I have the following code: Counting can be done elegantly by 'filter' and 'length': length $ filter (1) $ Monad.liftM2 gcd [2..1000] [2..1000] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficiency question
Counting can be done elegantly by 'filter' and 'length': I figured out the following code after posting: solve d = length [(y,x) | x - [2..d], y - [1..(x-1)], gcd x y == 1] main = print (solve 100) However when running it, it gave an answer of -1255316543. How on earth can a length be negative? length $ filter (1) $ Monad.liftM2 gcd [2..1000] [2..1000] Thanks... now I'll just have to figure out what it does and why it does what it does. -- View this message in context: http://www.nabble.com/Efficiency-question-tf3823154.html#a10873232 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficiency question
Evil Bro wrote: Counting can be done elegantly by 'filter' and 'length': I figured out the following code after posting: solve d = length [(y,x) | x - [2..d], y - [1..(x-1)], gcd x y == 1] main = print (solve 100) However when running it, it gave an answer of -1255316543. How on earth can a length be negative? Yu got an integer overflow - length returns an Int. You can use Data.List.genericLength instead, however, which can return its result in any Num instance. (In particular, Integer works) import Data.List solve :: Integer - Integer solve d = genericLength [(y,x) | x - [2..d], y - [1..(x-1)], gcd x y == 1] main = print (solve 100) (Note: untested.) HTH, Bertram ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Code review: efficiency question
Bulat Ziganshin wrote: [ideas including reverseMapM_] you will laugh, but speed of your two solutions depends on so many factors (including size of CPU cache) that noone can say that is better in general. although for small lists reverseMapM_ should be faster than reverse+mapM. what will be faster - using of higher-order function or direct recursion, i can't say, it's a really counter-intuitive area of ghc optimizer :) of course, i don't think that all that really matters for your program (drawing should anyway need much more time than looping). just use higher-level approach (that makes code simpler to write, understand and maintain) and don't bother your mind :) Hi Bulat! Thanks for the suggestions about reverseMapM_ etc. It seems that since the speeds of the two solutions can be relatively faster/slower on different platforms/CPUs I might as well just use the combination of existing functions mapM_ and reverse at the moment to get readable code with the least amount of effort :-) Best regards, Brian. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Code review: efficiency question
Brian, You might also want to take a look at the list fusion functionality in GHC which often can help optimize your programs when programming with lists. http://www.haskell.org/ghc/docs/latest/html/users_guide/rewrite-rules.html#id3153234 It doesn't help in your particular program but it might be usable for you in the future. Cheers, /Josef On 5/3/06, Brian Hulley [EMAIL PROTECTED] wrote: Bulat Ziganshin wrote: [ideas including reverseMapM_] you will laugh, but speed of your two solutions depends on so many factors (including size of CPU cache) that noone can say that is better in general. although for small lists reverseMapM_ should be faster than reverse+mapM. what will be faster - using of higher-order function or direct recursion, i can't say, it's a really counter-intuitive area of ghc optimizer :) of course, i don't think that all that really matters for your program (drawing should anyway need much more time than looping). just use higher-level approach (that makes code simpler to write, understand and maintain) and don't bother your mind :) Hi Bulat! Thanks for the suggestions about reverseMapM_ etc. It seems that since the speeds of the two solutions can be relatively faster/slower on different platforms/CPUs I might as well just use the combination of existing functions mapM_ and reverse at the moment to get readable code with the least amount of effort :-) Best regards, Brian. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Code review: efficiency question
Evan Martin wrote: I remember reading a tutorial that pointed out that you can often avoid explicit recusion in Haskell and instead use higher-level operators. For your code, I think drawModals = foldr (flip ()) (return ()) . map drawModal works(?). I think it would be foldl so that the (return()) would be nested as the leftmost element. Thanks for pointing out this point-free version of drawModals, although for readability at the moment I think I still prefer just to use mapM_ drawModal (reverse cs) Best regards, Brian. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Code review: efficiency question
Hello Brian, Tuesday, May 2, 2006, 3:12:48 AM, you wrote: -- Prolog style coding... drawModals :: [Control] - ManagerM () drawModals [] = return () drawModals (c:cs) = do drawModals cs drawModal c imho, it's typical functional style, but without using higher-level functions mapM_ drawModal (reverse cs) However, while this looks more elegant, it is less efficient? In other words, how much optimization can one assume when writing Haskell code? ghc will don't translate your later code into the former one. although in general ghc (but not other haskell compilers, afaik) is very good in replacing one code with another faster one and in particular in translating list producer + list consumer into straightforward loop how about this solution: reverseMapM_ f (x:xs) = do reverseMapM_ f xs; f x reverseMapM_ f [] = return () or you can define `reverseMapM_` via fold, if you have better FP skills than me :) I'm trying to get a rough idea so I can decide whether to write helper functions such as drawModals in future or whether I should always just use the most elegant code instead. Any ideas? you will laugh, but speed of your two solutions depends on so many factors (including size of CPU cache) that noone can say that is better in general. although for small lists reverseMapM_ should be faster than reverse+mapM. what will be faster - using of higher-order function or direct recursion, i can't say, it's a really counter-intuitive area of ghc optimizer :) of course, i don't think that all that really matters for your program (drawing should anyway need much more time than looping). just use higher-level approach (that makes code simpler to write, understand and maintain) and don't bother your mind :) -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficiency Question
Hi Daniel, On Fri, 14 Jan 2005 21:57:25 +0100, Daniel Fischer [EMAIL PROTECTED] wrote: snip Finally, in several contexts I needed to cons an element to one of a pair of lists, so I defined infixr 5 ,§ ^^^ Please be aware that you won't find this paragraph symbol on a uk or us keyboard. AFAIK it is just on the german one. () :: a - ([a],[b]) - ([a],[b]) x (xs,ys) = (x:xs,ys) (§) :: b - ([a],[b]) - ([a],[b]) y § (xs,ys) = (xs,y:ys). I find them useful (though I don't like the symbols, if you have any better ideas, thx) and for splitAt, () saves another reduction per step. I think these operators should be more related to : like : : or similar. However, in my opinion this special cons operators could be just functions with a meaningful name like consfst and conssnd. It would provide much more readability. Cheers, Georg -- Georg Martius, Tel: (+49 34297) 89434 --- http://www.flexman.homeip.net - ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficiency Question
Am Samstag, 15. Januar 2005 10:05 schrieben Sie: Hi Daniel, On Fri, 14 Jan 2005 21:57:25 +0100, Daniel Fischer [EMAIL PROTECTED] wrote: snip Finally, in several contexts I needed to cons an element to one of a pair of lists, so I defined infixr 5 ,§ ^^^ Please be aware that you won't find this paragraph symbol on a uk or us keyboard. AFAIK it is just on the german one. () :: a - ([a],[b]) - ([a],[b]) x (xs,ys) = (x:xs,ys) (§) :: b - ([a],[b]) - ([a],[b]) y § (xs,ys) = (xs,y:ys). I find them useful (though I don't like the symbols, if you have any better ideas, thx) and for splitAt, () saves another reduction per step. I think these operators should be more related to : like : : or Yes, but as Stefan Holdermans already wrote, (:) is illegal (operatornames beginning with ':' are infix Constructors). Since I use these operators mostly infix (up to now exclusively), I don't really want to type `consfst` all the time, hence I would need some stronger argument to convice me of using function names (after all, readability is to a large extent a matter of familiarity, you couldn't immediately understand ':', '+' ... either if you weren't thoroughly familiar with them). A stronger relation to ':' is absolutely desirable, maybe something like \: and /: would be better. Cheers, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Efficiency Question
Another thing, while toying, I found out that a comparison (n = 0) takes three reductions more than (n 1) according to my hugs, so changing the definition of splitAt thus, we require (3*n) reductions less. But the number of reductions and speed are different things, as witnessed by the above, so would it be an improvement to replace n = Integerliteral-queries by n Integerliteral-queries or doesn't that make any difference at all in execution time? I don't know about in Hugs, but in (compiled, optimized) GHC it should make no difference. Presumably, if you are running something in an interpreter micro-optimizing isn't worthwhile. Finally, in several contexts I needed to cons an element to one of a pair of lists, so I defined infixr 5 ,§ () :: a - ([a],[b]) - ([a],[b]) x (xs,ys) = (x:xs,ys) (§) :: b - ([a],[b]) - ([a],[b]) y § (xs,ys) = (xs,y:ys). Well, to start, the type signatures are unnecessarily restrictive. Then, the function that also is not in the Report, but does come up quite a bit by people who get into a point-free or categorical style is the bifunctor, (***) :: (a - b) - (c - d) - (a,c) - (b,d) f *** g = \(a,b) - (f a,g b) this is an instance of (***) in Control.Arrow, hence the name. So, your first function is, () x = (x:) *** id or using another function from Control.Arrow, () x = first (x:) I can say that I have wanted (***), I can't say that I've ever wanted your two functions. Also, first (x:) seems to be more self-documenting. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficiency Question
Am Samstag, 15. Januar 2005 14:36 schrieben Sie: Well, to start, the type signatures are unnecessarily restrictive. Yep, but since I always needed them for taking elements that satisfied either of two predicates from a list, that was the type that first came to mind (actually the zero'th type used ([a],[a]) ). Then, the function that also is not in the Report, but does come up quite a bit by people who get into a point-free or categorical style is the bifunctor, (***) :: (a - b) - (c - d) - (a,c) - (b,d) f *** g = \(a,b) - (f a,g b) this is an instance of (***) in Control.Arrow, hence the name. That's good to know, thanks. So, your first function is, () x = (x:) *** id or using another function from Control.Arrow, () x = first (x:) I can say that I have wanted (***), I can't say that I've ever wanted your two functions. Also, first (x:) seems to be more self-documenting. I haven't read Control.Arrow yet, but it seems at first glance that I should write first (x:) (xs,y) second (y:) (x,ys) instead? That looks good to me, more to type, alas, but much better to read. Many thanks, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficiency Question
Georg Martius wrote: infixr 5 ,§ ^^^ Please be aware that you won't find this paragraph symbol on a uk or us keyboard. AFAIK it is just on the german one. This reminds me, what symbols are valid for Haskell operators? I know that function names are: (in regex format) [A-Za-z_'][A-Za-z0-9_']*, but does that Haskell report define a definitive list of symbols that can be used in Haskell source... and how does that relate to the character set... can any symbol be used? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficiency Question
Keaan,
This reminds me, what symbols are valid for Haskell operators?
See Chapter 9 of the Report [1].
symbol - ascSymbol | uniSymbolspecial | _ | : | | '
ascSymbol - ! | # | $ | % | | * | + | . | / | | = | | ? | @ |
\ | ^ | | | - | ~
uniSymbol - any Unicode symbol or punctuation
varsym - ( symbol {symbol | :})reservedop | dashes
HTH,
Stefan
[1] http://haskell.org/onlinereport/syntax-iso.html
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficiency Question
Stefan Holdermans wrote:
symbol - ascSymbol | uniSymbolspecial | _ | : | | '
ascSymbol - ! | # | $ | % | | * | + | . | / | | = | | ? | @ |
\ | ^ | | | - | ~
uniSymbol - any Unicode symbol or punctuation
varsym - ( symbol {symbol | :})reservedop | dashes
So, does GHC accept more symbols than the report allows? Or would the
example with the sub-section symbol cause an error?
In which case what symbols are allowed in GHC, or Hugs?
Keean
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficiency Question
Keaan, (§) :: b - ([a],[b]) - ([a],[b]) y § (xs, ys) = (xs,y:ys) GHC gives a lexical error. Regards, Stefan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: efficiency question
On Saturday 09 February 2002 11:38, Jorge Adriano wrote: If you make it strict on the (,), like: test3 l = let s = foldr (\x (a,b) - ((,)$!x+a)$!x-b) (1,1) l in s Things will get worst. Well, that's what I expected, the elements of the list will b reduced to head normal form, and instead of a suspension of (%), you'll have a suspension of sums in the fst element of the pair *and* a suspension of differences in the second element of the pair. Eh... no need to comment on this one... this was kind of dumb. Forget it... :-) J.A. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: efficiency question
I'd say that's because in the second case you also got to apply the (,), besides the (+)/(-) constructor during the transversing... Am I right? opss... I meant to write: the (,) constructor besides the (+)/(-)... J.A. ___ 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
RE: efficiency question
(moved to haskell-café) I ran Hal's code on my computer, and with test2 I get a stack overflow (so I had to use +RTS option for it to finish). test1 does not overflow stack (of standard size, I mean without +RTS). Which implies that test2 uses more stack space than test1. why would it use more stack if not because of laziness? konst -Original Message- From: Hal Daume III [mailto:[EMAIL PROTECTED]] Sent: Friday, February 08, 2002 4:35 PM To: Jorge Adriano Cc: Konst Sushenko; [EMAIL PROTECTED] Subject: Re: efficiency question I agree that it's the overhead of (,), but I don't see why there would be any overhead for doing this. -- Hal Daume III Computer science is no more about computers| [EMAIL PROTECTED] than astronomy is about telescopes. -Dijkstra | www.isi.edu/~hdaume On Sat, 9 Feb 2002, Jorge Adriano wrote: On Friday 08 February 2002 23:52, Hal Daume III wrote: I've tried using a strict fold: foldl' f a [] = a foldl' f a (x:xs) = (foldl' f $! f a x) xs but that has no effect (or minimal effect). That wouldn't work even if if laziness is the problem because that would only cause the elements of the list to be evaluated to head normal form, the elements of the pair would not be evaluated so you'd have a 'suspension of (minus and plus) operations'. instead of (\x (a,b) - (x+a,x-b)) try (\x (a,b) - (((,) $! x-a)$! x-b) ) I just noticed that you were the one who sent me the DeepSeq module. This is the kind of place where I want to use it. Instead of $!, try $!!. And Konst Sushenko wrote: My guess is that it is due to the laziness of the addition/subtraction in (,) Seems to me like lazyness is not the right guess because both functions Hall first posted were lazy. So I think it's just the overhead of applying (,) besides (+) and (-) in each step. Do I make sense or am I missing something? J.A. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
