Re: [Haskell-cafe] Noob error: Type b -> c b Does not match IO a
Some simplifications might help you here...
prodList [] = 1 prodList (0:xs) = 0 prodList (x:xs) = x * prodList xs
Simplified: prodList xs = foldl (*) 1 xs But my original at least made some provision for short circuiting the whole operation if the list contained a 0. As far as I can figure, fold, map, etc., are not suitable for any situation in which short-circuiting would be desirable (e.g. and, or, etc.). Am I wrong? (I realize that, given that the function product is already available, there is no point in defining my function prodList above, but my question is a more general one, having to do with how best to implement short-circuiting.) Thanks! kj
On 2005 June 25 Saturday 17:49, kynn@panix.com wrote:
Simplified: prodList xs = foldl (*) 1 xs
But my original at least made some provision for short circuiting the whole operation if the list contained a 0. As far as I can figure, fold, map, etc., are not suitable for any situation in which short-circuiting would be desirable (e.g. and, or, etc.). Am I wrong?
Actually, foldr is applicable to short-circuiting. foldr (&&) True works fine for detecting whether all elements of a list are True, and does not evaluate the list beyond the first occurrence of False. Similarly, if `m` is defined as a short-circuiting multiplication operator, i.e. m x y = if x==0 then 0 else x*y then foldr m 1 does not evaluate the list beyond the first occurrence of 0. Unfortunately, `m` does not work as well with foldr as &&. The function (foldr m 1) creates a stack containing one (*) operation for every list element to be multiplied, which can cause undesirable memory usage. It's still possible to use fold and get short circuiting with good memory usage. upTo pred = foldr (\a -> \xs -> if pred a then [a] else a:xs) [] prodList = foldl' (*) 1 . upTo (== 0) It might be considered cheating, but AFAICT the test for ==0 needs to be separated from the multiplication proper. Note, foldl' is a more strict, more useful variant of foldl, located in Data.List.
Scott Turner wrote:
It's still possible to use fold and get short circuiting with good memory usage. upTo pred = foldr (\a -> \xs -> if pred a then [a] else a:xs) [] prodList = foldl' (*) 1 . upTo (== 0) It might be considered cheating, but AFAICT the test for ==0 needs to be separated from the multiplication proper.
They don't need to be separated, though the result is no longer as clear as one might wish: prodList xs = foldr (\x f a -> if x == 0 then 0 else f $! x * a) id xs 1 Udo. -- Wise men talk because they have something to say; fools, because they have to say something. -- Plato (429-347 BC)
Am Sonntag, 26. Juni 2005 06:06 schrieb Scott Turner:
On 2005 June 25 Saturday 17:49, kynn@panix.com wrote:
Simplified: prodList xs = foldl (*) 1 xs
But my original at least made some provision for short circuiting the whole operation if the list contained a 0. As far as I can figure, fold, map, etc., are not suitable for any situation in which short-circuiting would be desirable (e.g. and, or, etc.). Am I wrong?
Actually, foldr is applicable to short-circuiting. foldr (&&) True works fine for detecting whether all elements of a list are True, and does not evaluate the list beyond the first occurrence of False. Similarly, if `m` is defined as a short-circuiting multiplication operator, i.e. m x y = if x==0 then 0 else x*y then foldr m 1 does not evaluate the list beyond the first occurrence of 0. Unfortunately, `m` does not work as well with foldr as &&. The function (foldr m 1) creates a stack containing one (*) operation for every list element to be multiplied, which can cause undesirable memory usage.
It's still possible to use fold and get short circuiting with good memory usage. upTo pred = foldr (\a -> \xs -> if pred a then [a] else a:xs) [] prodList = foldl' (*) 1 . upTo (== 0) It might be considered cheating, but AFAICT the test for ==0 needs to be separated from the multiplication proper.
Plain foldr m 1 does fine, in fact much better than foldl' (*) 1 . upTo (== 0), both in hugs and ghc, regarding speed and memory usage. Cheers, Daniel
On Sun, 26 Jun 2005, Daniel Fischer wrote:
m x y = if x==0 then 0 else x*y
Plain
foldr m 1
does fine, in fact much better than
foldl' (*) 1 . upTo (== 0),
both in hugs and ghc, regarding speed and memory usage.
E.g. foldr m 1 [a,b,c] means m a (m b (m c 1))) That is, it is not possible for the runtime system to store interim numeric results, it can only accumulate function calls.
Am Sonntag, 26. Juni 2005 21:02 schrieben Sie:
On Sun, 26 Jun 2005, Daniel Fischer wrote:
m x y = if x==0 then 0 else x*y
Plain
foldr m 1
does fine, in fact much better than
foldl' (*) 1 . upTo (== 0),
both in hugs and ghc, regarding speed and memory usage.
E.g. foldr m 1 [a,b,c]
means m a (m b (m c 1)))
That is, it is not possible for the runtime system to store interim numeric results, it can only accumulate function calls.
Well, yes, but since 'm' is lazy in the second argument, the list isn't traversed past the first zero - like foldr (&&) True. Try a list like [1 .. 20000] ++ [0 .. 50000], compile for profiling and see. I'm not sure why, but upTo eats much more memory than foldr m 1. Cheers, Daniel
On Mon, 27 Jun 2005, Daniel Fischer wrote:
Am Sonntag, 26. Juni 2005 21:02 schrieben Sie:
On Sun, 26 Jun 2005, Daniel Fischer wrote:
m x y = if x==0 then 0 else x*y
Plain
foldr m 1
does fine, in fact much better than
foldl' (*) 1 . upTo (== 0),
both in hugs and ghc, regarding speed and memory usage.
E.g. foldr m 1 [a,b,c]
means m a (m b (m c 1)))
That is, it is not possible for the runtime system to store interim numeric results, it can only accumulate function calls.
Well, yes, but since 'm' is lazy in the second argument, the list isn't traversed past the first zero - like foldr (&&) True.
That was not the point. The point is that "m a (m b (m c..." can't be reduced immediately to, say, "(m (m a b) c) ...", since this is completely different. The computation can only start when the end of the list is reached.
Well, the case of the built-in numeric types is somewhat different,
but most functions automatically short circuit, since Haskell uses
lazy evaluation.
For instance, it's perfectly okay to define
myAnd = foldr (&&) True
Note that this terminates on infinite lists which contain False as a value:
myAnd (False : repeat True)
will evaluate to False pretty much immediately.
- Cale
On 25/06/05, kynn@panix.com
Some simplifications might help you here...
prodList [] = 1 prodList (0:xs) = 0 prodList (x:xs) = x * prodList xs
Simplified: prodList xs = foldl (*) 1 xs
But my original at least made some provision for short circuiting the whole operation if the list contained a 0. As far as I can figure, fold, map, etc., are not suitable for any situation in which short-circuiting would be desirable (e.g. and, or, etc.). Am I wrong?
(I realize that, given that the function product is already available, there is no point in defining my function prodList above, but my question is a more general one, having to do with how best to implement short-circuiting.)
Thanks!
kj
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Oops, somehow that reply by Scott Turner (which coincidentally
contained the same example) hadn't appeared for me yet :)
Anyway, seconded :)
On 26/06/05, Cale Gibbard
Well, the case of the built-in numeric types is somewhat different, but most functions automatically short circuit, since Haskell uses lazy evaluation.
For instance, it's perfectly okay to define myAnd = foldr (&&) True Note that this terminates on infinite lists which contain False as a value: myAnd (False : repeat True) will evaluate to False pretty much immediately.
- Cale
participants (6)
-
Cale Gibbard -
Daniel Fischer -
Henning Thielemann -
kynn＠panix.com -
Scott Turner -
Udo Stenzel