Re: using less stack
cpsfold f a [] ú cpsfold f a (x:xs) ÿ x a (\y -> cpsfold f y xs)
and f takes a continuation, Bob's my uncle, and I have a program that runs quickly in constant space!
Good. I'm curious to know from other readers whether continuations like this are the only way of solving it, though.
Actually, and quite apart from it being cumbersome to use, I've got my doubts about whether this cpsfold really does the job (is that just me missing some point?-). Also, I'm curious to know why the usual strict variant of foldl doesn't help in this case? foldl' f a [] = a foldl' f a (x:xs) = (foldl' f $! f a x) xs or, with the recently suggested idiom for strictness, tracing and other annotations:-) annotation = undefined strict a = seq a False foldl' f a l | strict a = annotation foldl' f a [] = a foldl' f a (x:xs) = foldl' f (f a x) xs Claus
strict a = seq a False
foldl' f a l | strict a = annotation foldl' f a [] = a foldl' f a (x:xs) = foldl' f (f a x) xs
Or, perhaps strict a = a `deepSeq` False or strict a = rnf a `seq` False if you prefer the rnf notation instead. depending on what you want... \begin{rant} I think the whole seq thing is very confusing for beginning/intermediate haskell programmers. I was very confused for a long time as to why
(unsafePerformIO (putStrLn "Hello")) `seq` 5
would print "Hello", but
[unsafePerformIO (putStrLn "Hello")] `seq` 5
would not. this goes back to the earlier discussion of "does a haskell programmer need to know how the compiler works." while you could argue this isn't exactly a compiler issue and that the semantics of seq *are* well defined outside any particular compiler, you do need to know something about how the graph reduction happens, etc., in order to understand exactly what is being evaluated on the left hand side of `seq`. I would almost prefer if the semantics of `seq` were instead those of rnf or deepSeq, so long as either (a) we were allowed to derive DeepSeq or NFData, or (b) if the compiler would just do it itself. Yes, this would cut down on the expressions which we could `seq`, but does that really matter. I mean, how often are we going to say:
(+) `seq` 5
What the heck is that supposed to mean? I would almost *prefer* if an expression like that didn't typecheck. Since seq isn't lambda definable anyway, I don't see any particular reason the compiler couldn't just reduce to normal form instead of weak head normal form for seqs. Perhaps artifically introduce an NFData instance for everything so the above doesn't typecheck. But that's just me :) \end{rant}
[cpsfold omitted]
Actually, and quite apart from it being cumbersome to use, I've got my doubts about whether this cpsfold really does the job (is that just me missing some point?-).
It does the job for me! In practical terms I can see it works. I'm not an expert - I may have this all wrong, but perhaps the point you're looking for is that the arguments to f are brought to the very outside of the expression, and hence available for evaluation. Imagine for [x1,x2,x3,x4] from foldr: f x1 (f x2 (f x3 (f x4 a))) from foldl: f (f (f (f a x1) x2) x3) x4 Neither are available for immediate evaluation. In the case of foldr the end of the list (x4) has to be reached before anything can be evaluated. In the case of foldl the first function to be pulled upon is the outermost f, which then can't do anything useful (in my case) without evaluating its second argument, and so on. with the cpsfold I get f x1 a (\y1 -> f x2 y1 (\y2 -> f x3 y3 (\y3 -> f x4 y4 (\y4 -> y4) so x1 and a are available immediately for f to use, and f x1 a is the outermost expression so will be evaluated first. See for yourself with the following (difference can be seen in ghc with standard 1M stack):
answer1 = foldr larger 0 [1..500000] answer2 = foldl larger 0 [1..500000] answer3 = cpsfold cpslarger 0 [1..500000]
larger x y = if x > y then x else y cpslarger x y k = if x > y then k x else k y
Also, I'm curious to know why the usual strict variant of foldl doesn't help in this case?
foldl' f a [] = a foldl' f a (x:xs) = (foldl' f $! f a x) xs
Because $! and seq only evaluates enough to make sure the answer is not bottom, and if my f is complex then it doesn't do enough. Amanda
with the cpsfold I get
f x1 a (\y1 -> f x2 y1 (\y2 -> f x3 y3 (\y3 -> f x4 y4 (\y4 -> y4)
so x1 and a are available immediately for f to use, and f x1 a is the outermost expression so will be evaluated first.
Yes, however, if f just calls its continuation without forcing the evaluation of at least its second argument, e.g. f x y k = k (g x y) you get f x1 a (\y1 -> f x2 y1 (\y2 -> f x3 y3 (\y3 -> f x4 y4 (\y4 -> y4)))) => f x2 (g x1 a) (\y2 -> f x3 y3 (\y3 -> f x4 y4 (\y4 -> y4))) => f x3 (g x2 (g x1 a)) (\y3 -> f x4 y4 (\y4 -> y4))) => f x4 (g x3 (g x2 (g x1 a))) (\y4 -> y4) => g x4 (g x3 (g x2 (g x1 a))) like the foldr.
larger x y = if x > y then x else y cpslarger x y k = if x > y then k x else k y
Yes, with this definition of `cpslarger' no stack is used, because the comparison forces evaluation. With cpslarger x y k = k (larger x y) it does not work. Still, if your definition of cpslarger is natural for your application, it is a nice solution of the problem. Ciao, Olaf -- OLAF CHITIL, Dept. of Computer Science, The University of York, York YO10 5DD, UK. URL: http://www.cs.york.ac.uk/~olaf/ Tel: +44 1904 434756; Fax: +44 1904 432767
You don't have to define cpsfold explicitly recursively since it can be expressed in terms of foldr: cpsfold f a xs = foldr (\x k y -> f x y k) id xs a The following definition would even be better (but not equivalent): cpsfold' f a xs = foldr (\x k y -> f y x k) id xs a The list members are now 'consumed' left-to-right by f, with initial value a. So, answer4 = foldr (\x k a -> if x > a then k x else k a) id [1..500000] 0 also works without a crash or insufficient stack space. Gertjan ----- Original Message ----- From: "Amanda Clare" <ajc99@aber.ac.uk> To: "C.Reinke" <C.Reinke@ukc.ac.uk> Cc: <haskell@haskell.org> Sent: Wednesday, March 20, 2002 7:45 PM Subject: Re: using less stack
[cpsfold omitted]
Actually, and quite apart from it being cumbersome to use, I've got my doubts about whether this cpsfold really does the job (is that just me missing some point?-).
It does the job for me! In practical terms I can see it works. I'm not an expert - I may have this all wrong, but perhaps the point you're looking for is that the arguments to f are brought to the very outside of the expression, and hence available for evaluation. Imagine for [x1,x2,x3,x4] from foldr: f x1 (f x2 (f x3 (f x4 a))) from foldl: f (f (f (f a x1) x2) x3) x4
Neither are available for immediate evaluation. In the case of foldr the end of the list (x4) has to be reached before anything can be evaluated. In the case of foldl the first function to be pulled upon is the outermost f, which then can't do anything useful (in my case) without evaluating its second argument, and so on.
with the cpsfold I get
f x1 a (\y1 -> f x2 y1 (\y2 -> f x3 y3 (\y3 -> f x4 y4 (\y4 -> y4)
so x1 and a are available immediately for f to use, and f x1 a is the outermost expression so will be evaluated first.
See for yourself with the following (difference can be seen in ghc with standard 1M stack):
answer1 = foldr larger 0 [1..500000] answer2 = foldl larger 0 [1..500000] answer3 = cpsfold cpslarger 0 [1..500000]
larger x y = if x > y then x else y cpslarger x y k = if x > y then k x else k y
Also, I'm curious to know why the usual strict variant of foldl doesn't help in this case?
foldl' f a [] = a foldl' f a (x:xs) = (foldl' f $! f a x) xs
Because $! and seq only evaluates enough to make sure the answer is not bottom, and if my f is complex then it doesn't do enough.
Amanda
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Hi,
You don't have to define cpsfold explicitly recursively since it can be expressed in terms of foldr:
Is this generally considered good design? That is, is it generally preferred to express functions in a nonrecursive style if that can be done using standard library functions like foldr and map and filter, etc? Okay, obviousloy everything *can* be done in that manner, so I guess my question is why should we write something using foldr when, imo, the explicitely recursive version is easier to parse (as a human). - Hal
Gertjan Kamsteeg <gkamsteeg@freeler.nl> writes:
You don't have to define cpsfold explicitly recursively since it can be expressed in terms of foldr:
Hal Daume III <hdaume@ISI.EDU> writes:
Is this generally considered good design? [...]
Three different attempts at an answer: As with all code-factoring it's in the eye of the beholder. If what you want to do is trace execution in detail, the less factored code is easier to understand. If what you want to do is understand the difference between 5 different recursive traversals of a list, then isolating those differences (by suppressing the invariant fact of recursion) is better. More concretely, some prefer to avoid the recursive formulations because: 1) It is trickier to reason about. Functional programmers (especially Squiggol afficianados) have all kinds of cunning ways to reason about programs written using standard library functions such as foldr. The techniques for reasoning directly about recursive functions are somewhat cruder and harder. 2) The ability to recursivly invoke the function from _anywhere_ in the function body has been compared (with some justification) to the use of goto in unstructured programming. If you buy into this line of reasoning then foldr, scanr, map, etc. are to functional programming as while, repeat and for are to structured programming. [These two points are connected!] And, finally, my personal preference is: - use explicit recursion when I don't understand what I'm doing well enough to know which standard recursive pattern it fits into (because it normally always fits a standard pattern). - use higher-order functions when I know what I'm doing or where setting up the infrastructure for the recursion costs more than coding it directly. -- Alastair Reid Reid Consulting (UK) Ltd
From: "Alastair Reid" <reid@cs.utah.edu>
Gertjan Kamsteeg <gkamsteeg@freeler.nl> writes:
You don't have to define cpsfold explicitly recursively since it can be expressed in terms of foldr:
Hal Daume III <hdaume@ISI.EDU> writes:
Is this generally considered good design? [...]
Three different attempts at an answer:
As with all code-factoring it's in the eye of the beholder.
If what you want to do is trace execution in detail, the less factored code is easier to understand.
If what you want to do is understand the difference between 5 different recursive traversals of a list, then isolating those differences (by suppressing the invariant fact of recursion) is better.
I agree. However, although *functionally* every list traversing function should be expressible in terms of foldr (because foldr represents the type theoretical elimination rule for lists in most type systems with inductive types (and without element depending types)), it's not just a matter of taste. Execution clearly *does* depend on how things are defined. When I said 'can be expressed', I meant extensionally equivalent, including behavior w.r.t. reductions. For example, if, in the Prelude, foldr had been defined in terms of foldl: foldr f a xs = foldl (\h x y -> h (f x y)) id xs a my definition of cpsfold in terms of foldr wouldn't go through. That is, some stack would again overflow. What I wanted to say is that the fact that Amanda's answer1 (maximum in terms of foldr) didn't work wasn't caused by the definition of foldr in the Prelude. Besides, (re)factoring is fun. So, here's another one (foldl in terms of foldr): foldl f a xs = foldr (\x h y -> h (f y x)) id xs a BTW, there may be another reason for expressing list traversing functions in terms of foldr: if one uses only functions representing 'standard' elimination rules, it is guaranteed that all reduction sequences eventually terminate. Gertjan
Hal Daume III writes:
You don't have to define cpsfold explicitly recursively since it can be expressed in terms of foldr:
Is this generally considered good design? That is, is it generally preferred to express functions in a nonrecursive style if that can be done using standard library functions like foldr and map and filter, etc?
One answer that Alastair Reid did not mention is that the nonrecursive style usually benefits from the deforestation optimization whereas IIUC the explicitly recursive style never does in contemporary compilers. Another answer, which I give because the factor does not enter enough into the thinking of academic language designers, is that the nonrecursive style inhibits adoption of Haskell by making it slightly more difficult for the average programmer or programmer-wannabe to learn --"slightly" because with recursion, lists and monadic interfaces Haskell already has a lot of significant learning barriers to adoption, and the nonrecursive style of definition is easier to learn (get used to) than any one of those last 3. -- Richard Uhtenwoldt
So, how popular is Haskell compared to other languages? Here are some Google search results that suggest how many web pages are devoted to particular langauges. (Google tells you how many pages match your query.) A better survey of language popularity would include newsgroup and mailing list traffic, but no time, no time. In this modest survey, Haskell is a little more popular than O'Caml, a little less popular than Eiffel (an OOPL) 5 to 6 times less popular than Smalltalk; 8 to 10 times less popular than Python, which is itself at least 2 and a half or 3 times less popular than Perl. On second thought, Eiffel and Smalltalk might be considerably more popular than suggested by page counts because the other languages surveyed have 100% open-source documentation. eg, in the GHC results I saw lots of duplicates of essentially the same document. This is characteristic of open-source-code-licensed content. In contrast, Eiffel and Smalltalk have commercial vendors, whose documentation is (I would think) underrepresented in this modest survey because of having licenses that restrict copying. perl 9,600,000 perl language OR program OR variable OR object 1,490,000. python -monty -snake -venom 809,000 python program OR language OR variable OR object 630,000 smalltalk 361,000 (say 10% false hits. 325,000 real.) lisp cmucl OR "common lisp" OR heap OR cdr OR cons OR lambda OR closure OR scheme 188,000 eiffel object OR program OR variable OR string -tower 74,700 (I say there's a few false hits there. 71,000 real hits.) ghc haskell OR compiler 63,100 ghc haskell OR compiler OR functional OR fp 66,800 haskell fp OR "programming" OR monad OR monadic OR functional OR lambda 63,600 haskell "programming" OR monad OR monadic OR functional OR lambda 55,500 (I say 63,000 is the most accurate) caml 88,700 (I can see some false hits) "objective caml" OR ocaml OR o'caml 41,700. (42,000) note that there is at least one open-source Linux package, unison, a file sync utility, written in O'Caml. no Linux packages written in Haskell except for Haskell compilers. other info useful for measuring language popularity. <LI><a href="http://www.dwheeler.com/sloc/redhat71-v1/summary">sloc in various RedHat 7.2 packages</a> <LI><a href="http://upgrade-cepis.org/issues/2001/6/up2-6Gonzalez.pdf">lines of code in Debian</a> <LI><a href="http://people.debian.org/~jgb/debian-counting/">Counting Debian //</a> <LI><a href="http://www.eros-os.org/pipermail/e-lang/2001-February/004594.html"> [E-Lang] popularity of programming languages among open source hackers // weak survey, of Sourceforge projects. see also Oct 2001 e-lang.</a> -- Richard Uhtenwoldt
Richard Uhtenwoldt <ru@river.org> writes:
Here are some Google search results that suggest how many web pages are devoted to particular langauges. (Google tells you how many pages match your query.) A better survey of language popularity would include newsgroup and mailing list traffic, but no time, no time.
I had a quick look at the Usenet statistics at www.ibiblio.org, but unfortunately Galeon had some problems navigating around the pages. comp.lang.perl.misc had 1624 posts per month, comp.lang.functional had 55. I guess Perl is rather popular, after all. But for some reason, c.l.f is recorded with 23K readers, compared to Perl's meagre 9500. Perhaps that's 1624 complaints about the ugly syntax? Or just a tribute to the devastating wit and intellect of functional programmers? -kzm -- If I haven't seen further, it is by standing in the footprints of giants
participants (8)
-
Alastair Reid -
Amanda Clare -
C.Reinke -
Gertjan Kamsteeg -
Hal Daume III -
ketil＠ii.uib.no -
Olaf Chitil -
Richard Uhtenwoldt