Hi all I've been reading the GHC docs and they say that strict functions are good for space and time. Section 6.2 goes on to explain how to read the .hi files to determine the strictness of a function. However, it doesn't explain all the cases I am seeing. Example of the ones I've noticed are: V S(L)V AAAb m C(V)L What do these mean? And more importantly, how good are they? Also, the prelude definition of zipWith has LVL whereas the following definition has LVV. Why is something like the following not used?
zipWith :: (a->b->c) -> [a] -> [b] -> [c] zipWith f (a:as) (b:bs) = f a b : zipWith f as bs zipWith _ _ [] = [] zipWith _ _ _ = []
Thanks Ian
G'day all. On Fri, Oct 19, 2001 at 02:30:59PM +0100, Ian Lynagh wrote:
Also, the prelude definition of zipWith has LVL whereas the following definition has LVV. Why is something like the following not used?
zipWith :: (a->b->c) -> [a] -> [b] -> [c] zipWith f (a:as) (b:bs) = f a b : zipWith f as bs zipWith _ _ [] = [] zipWith _ _ _ = []
Generally speaking, Haskell programmers don't like inserting more code with the only effect being to make the function less lazy. This goes double for standard library code. I say "generally" because occasionally there's a good reason (e.g. forcing evaluation can make a program more space-efficient). Is there a good reason behind your version of zipWith other than the strictness signature being more symmetrical? :-) If you really need a reason which doesn't involve bottom, consider a (fairly common) call such as: zipWith f xs [1..] If xs is finite, your version of zipWith would evaluate the infinite list [1..] one place beyond that which was really needed. Cheers, Andrew Bromage
On Sat, Oct 20, 2001 at 01:11:05AM +1000, Andrew J Bromage wrote:
G'day all.
On Fri, Oct 19, 2001 at 02:30:59PM +0100, Ian Lynagh wrote:
Also, the prelude definition of zipWith has LVL whereas the following definition has LVV. Why is something like the following not used?
zipWith :: (a->b->c) -> [a] -> [b] -> [c] zipWith f (a:as) (b:bs) = f a b : zipWith f as bs zipWith _ _ [] = [] zipWith _ _ _ = []
Generally speaking, Haskell programmers don't like inserting more code with the only effect being to make the function less lazy. This goes double for standard library code.
I say "generally" because occasionally there's a good reason (e.g. forcing evaluation can make a program more space-efficient). Is there a good reason behind your version of zipWith other than the strictness signature being more symmetrical? :-)
With the following code: main :: IO() main = putStrLn $ show $ last $ zipa list (cycle "hello world") where list = concat $ replicate 1000000000 $ replicate 10 'a' zipa :: [a] -> [b] -> [(a, b)] zipa (x:xs) (y:ys) = (x, y):zipa xs ys zipa _ _ = [] zipb :: [a] -> [b] -> [(a, b)] zipb (x:xs) (y:ys) = (x, y):zipb xs ys zipb _ [] = [] zipb _ _ = [] I get $ time nice -n 10 ./W ('a','h') real 148m50.013s user 146m37.930s sys 0m4.470s $ whereas changing the zipa to zipb gives me $ time nice -n 10 ./W ('a','h') real 136m56.882s user 135m13.690s sys 0m2.370s $ which is a speedup of around 7 or 8 percent.
If you really need a reason which doesn't involve bottom, consider a (fairly common) call such as:
zipWith f xs [1..]
If xs is finite, your version of zipWith would evaluate the infinite list [1..] one place beyond that which was really needed.
Sure, there is a single extra amount of evaluation needed to work out if there is a following list item (I guess this could be quite high in more complex cases - is this the reason?), but there is a constant time speedup on every zip(With) call that actually does some zipping. Ian
If xs is finite, your version of zipWith would evaluate the infinite list [1..] one place beyond that which was really needed.
Sure, there is a single extra amount of evaluation needed to work out if there is a following list item (I guess this could be quite high in more complex cases - is this the reason?)
Consider 1:2:if (2^2^2241 - 1) `mod` p == 0 then [p] else [] or whatever. The cost of determining whether there is another member of a list can be arbitrarily (up to infinite) large. -- Jón Fairbairn Jon.Fairbairn@cl.cam.ac.uk 31 Chalmers Road jf@cl.cam.ac.uk Cambridge CB1 3SZ +44 1223 570179 (after 14:00 only, please!)
participants (3)
-
Andrew J Bromage -
Ian Lynagh -
Jon Fairbairn