PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf Of Jules
| Bean
| Sent: 10 December 2004 21:38
| To: GoldPython
| Cc: Henning Thielemann; haskell-cafe
| Subject: Re: [Haskell-cafe] Flattening tail recursion?
|
|
| On 10 Dec 2004, at 20:33, GoldPython wrote:
|
| Just compiled this with -O
Hi everyone,
I had the idea that, instead of using 'seq', one might check for parity:
countLines2 aux (_:l)
| even aux = ...
| odd aux = ...
that prevents stack overflow, but is much slower than
countLines1 aux (_:l)
| aux `seq` False = ...
| otherwise = ...
I
Will,
countLines [] = 0
countLines (_:ls) = 1 + countLines ls
I would have thought that this was tail recursive and would be
flattened into iteration by the compiler. Can anyone explain why? Is
it because the call is embedded in an expression?
This is the tail-recursive version:
\begin{code}
On Mon, Dec 13, 2004 at 11:56:45AM +0100, Daniel Fischer wrote:
I had the idea that, instead of using 'seq', one might check for parity:
countLines2 aux (_:l)
| even aux = ...
| odd aux = ...
that prevents stack overflow, but is much slower than
countLines1 aux (_:l)
intermediate thunk has already been built. You need a separate strict
foldl function, usually called foldl', which was unaccountably
omitted from the prelude.
There is one in Data.List.
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
countLines [] = 0
countLines (_:ls) = 1 + countLines ls
I would have thought that this was tail recursive and would be
flattened into iteration by the compiler. Can anyone explain why?
This function isn't tail recursive, because you do additional operations
to the result of the function
On 10 Dec 2004, at 15:34, Robert Dockins wrote:
So it should get flattened, but it still doesn't run in constant
space because the x parmeter isn't strict, so it will accumulate a
bunch of closures like (((0)+1)+1)+1)+1)+1) To make it strict,
do something like this:
Isn't this what the
Jules Bean wrote:
On 10 Dec 2004, at 15:34, Robert Dockins wrote:
So it should get flattened, but it still doesn't run in constant
space because the x parmeter isn't strict, so it will accumulate a
bunch of closures like (((0)+1)+1)+1)+1)+1) To make it strict,
do something like this:
GoldPython wrote:
I know there's
length to count the elements in a list and it works fine, but the
function below stack overflows on a large list.
countLines [] = 0
countLines (_:ls) = 1 + countLines ls
I would have thought that this was tail recursive and would be
flattened into iteration by
Jules Bean wrote:
On 10 Dec 2004, at 15:34, Robert Dockins wrote:
So it should get flattened, but it still doesn't run in constant
space because the x parmeter isn't strict, so it will accumulate a
bunch of closures like (((0)+1)+1)+1)+1)+1) To make it
strict, do something like this:
On 10 Dec 2004, at 16:35, Ben Rudiak-Gould wrote:
Jules Bean wrote:
On 10 Dec 2004, at 15:34, Robert Dockins wrote:
So it should get flattened, but it still doesn't run in constant
space because the x parmeter isn't strict, so it will accumulate a
bunch of closures like
I did this:
countLines ls = foldl (\x y - x + 1) 0 ls
Still overflows.
On Fri, 10 Dec 2004 19:07:04 +0100 (MEZ), Henning Thielemann
[EMAIL PROTECTED] wrote:
On Fri, 10 Dec 2004, Robert Dockins wrote:
countLines [] = 0
countLines (_:ls) = 1 + countLines ls
I would
Thanks to all for the good info. I see what tail recursion is now.
Robert's example above leads me to a couple questions:
I had actually written my countlines like Robert's before the other
one I mailed in and mine overflowed the stack just like his. According
to people's responses, this one
Duh, just read above a bit closer. Sorry for the clutter...
On Fri, 10 Dec 2004 13:53:38 -0500, GoldPython [EMAIL PROTECTED] wrote:
Thanks to all for the good info. I see what tail recursion is now.
Robert's example above leads me to a couple questions:
I had actually written my countlines
Hi Will,
you probably get confused with stack overflow through non-tail recursive
function and stack overflow because you accumulate all intermediate values in
the closure. It was allready posted before, that you need to enforce the
evaluation of the + in order to get the function run in
Georg Martius wrote:
It was allready posted before, that you need to enforce the evaluation
of the + in order to get the function run in constant space. The thing
is, that it is harder to achieve than I expected it to be.
countLines' ls = foldl (\x y - let x' = x + 1 in x' `seq` y `seq` x'
) 0
On 10 Dec 2004, at 20:33, GoldPython wrote:
Just compiled this with -O and it ran with no stack overflow.
Evidently, no `seq` needed for this one. Using ghc 6.2.2.
countLines l = countLines' 0 l
countLines' n [] = n
countLines' n (_:ls) = countLines' (n + 1) ls
That's presumably the answer. GHC's
I'm missing something, a functional idiom, whatever. I know there's
length to count the elements in a list and it works fine, but the
function below stack overflows on a large list.
countLines [] = 0
countLines (_:ls) = 1 + countLines ls
I would have thought that this was tail recursive
Will,
countLines [] = 0
countLines (_:ls) = 1 + countLines ls
I would have thought that this was tail recursive and would be
flattened into iteration by the compiler. Can anyone explain why? Is
it because the call is embedded in an expression?
This is the tail-recursive version:
\begin{code}
On 10 Dec 2004, at 15:06, GoldPython wrote:
I'm missing something, a functional idiom, whatever. I know there's
length to count the elements in a list and it works fine, but the
function below stack overflows on a large list.
countLines [] = 0
countLines (_:ls) = 1 + countLines ls
I would
On Fri, 10 Dec 2004, Robert Dockins wrote:
countLines [] = 0
countLines (_:ls) = 1 + countLines ls
I would have thought that this was tail recursive and would be
flattened into iteration by the compiler. Can anyone explain why?
countlines = aux 0
where aux x [] = x
Just compiled this with -O and it ran with no stack overflow.
Evidently, no `seq` needed for this one. Using ghc 6.2.2.
countLines l = countLines' 0 l
countLines' n [] = n
countLines' n (_:ls) = countLines' (n + 1) ls
On Fri, 10 Dec 2004 20:32:07 +0100, Georg Martius
[EMAIL PROTECTED]
Henning,
Why is Prelude.length not defined this way (according to the Haskell98
report)?
The Report itself answers your question (in Chapter 8):
It constitutes a _specification_ for the Prelude. Many of the
definitions are written with clarity rather than efficiency in mind,
and it is not
23 matches
Mail list logo
