Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Re^2: map: chaining vs. nesting

by danderson (Beadle)
on Jun 18, 2004 at 18:42 UTC ( #368026=note: print w/replies, xml ) Need Help??


in reply to Re: map: chaining vs. nesting
in thread map: chaining vs. nesting

They are only inefficient to a point. If, in Lisp|Perl|C|whatever, you write a recursive function that runs a few thousand times, then you're going to suck up some RAM and the stack-push/pop CPU time. LISP, Scheme, ML, and their compadres are pretty well designed to minimize this. But, if you write a tail-recursive function, you're fine; overhead is exactly the same as for iteration.

So it's all about how you implement your algorithms. Any language can be inefficient - m/(a|b+)*/ being a simple example I can remember being horrible in Perl. Besides, though most style guides for functional languages don't encourage it, they almost all have iteration constructs, even if they're not popular. I know LISP does; I think Scheme and ML do.

Replies are listed 'Best First'.
Re^3: map: chaining vs. nesting
by Errto (Vicar) on Jun 19, 2004 at 01:17 UTC

    Indeed. I spent a year working rather intensively on both ML and Haskell (which are structurally similar but have some crucial differences) and one of the first things I learned is that while it's tempting to implement a factorial like this:

    fact 0 = 1 fact 1 = 1 fact n | n < 0 = error "Negative factorial!" | otherwise = n * fact (n - 1)

    your life will be vastly improved if you implement it like this:

    fact 0 = 1 fact 1 = 1 fact n | n < 0 = error "Negative factorial!" | otherwise = g 1 n where g x 1 = x g x n' = g (x * n') (n' - 1)

    because the latter uses tail recursion and the former doesn't.

Re^3: map: chaining vs. nesting
by FoxtrotUniform (Prior) on Jun 18, 2004 at 18:54 UTC
    If, in Lisp|Perl|C|whatever, you write a recursive function that runs a few thousand times, then you're going to suck up some RAM and the stack-push/pop CPU time. LISP, Scheme, ML, and their compadres are pretty well designed to minimize this. But, if you write a tail-recursive function, you're fine; overhead is exactly the same as for iteration.

    Tail recursion can be converted directly into iteration; this is part of the Scheme standard, I believe, and most implementations of other functional languages support it. If you're unlucky enough to have an implementation that doesn't, though, tail recursion will still suck up stack space for function calls.

    --
    F o x t r o t U n i f o r m
    Found a typo in this node? /msg me
    % man 3 strfry

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://368026]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (4)
As of 2019-10-21 04:47 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Notices?