Hi, I need to define a function called safetail; it's like tail except that this one maps the empty list to the empty list. It has to be defined using the following: 1. a conditional expression 2. guarded equation 3. pattern matching It's probably quite simple, but I am struggling on this, so help would be appreciated. Thanks Raj
On Wed, 27 Aug 2003 15:08:32 +0100 "Rajiv Patel" <raj_patel@cwcom.net> wrote:
1. a conditional expression
This one uses "case" so it should solve your homework; moreover it uses an orthogonal matrix (as long as you pay attention to the value assigned to f, of course) so it is safe. ---- cut here --- -- First of all, a simple auxiliary function, so everything is -- tail recursive safetailaux :: [b] -> ([b] -> Int) -> [b] safetailaux b d = a b c where c = d b f = f m = const False a c z = case z of 1 -> e g -- this matrix is orthogonal 0 -> g f -- so the function "a" is safe e g = filter m [] g e = drop 1 b -- like all functions it can be defined as -- a filter and a drop -- Now make it no longer tail recursive safetail x = safetailaux x ((\ z -> if z == 0 then 1 else 0) . length) --- cut here --- For the pattern matching case, it's easier: safetailPM [x,y,z] = tail [x,y,z] safetailPM a@[x,y] = tail a safetailPM x = x For the other one, try to figure out how it works from my examples Hope this helps Vincenzo
On 27-Aug-2003 Nick Name wrote:
-- First of all, a simple auxiliary function, so everything is -- tail recursive
safetailaux :: [b] -> ([b] -> Int) -> [b]
Apropos "tailrecursive": I have the following question in mind for some time: Rabhi/Lapalmes book about functional-styled algorithms mention a version of tail-recursion-optimization which relies on the availability of tail recursion elimination in Haskell compilers and interpreters. Does the notion "tail recursion elimination" mean something at all in the context of Haskell? For example: copyList (x:xs) = x : copyList xs is surely not tail-recursive in the traditional sense, but I think that most Haskell programmers take it for granted that it runs in constant stack space. Behind this there is a more general question concerning stack space complexity: Assuming primitive graph-reduction, the stack size (which holds pointers to strict functions whose arguments are under evaluation, if I remember things right) is bounded by the heap size. Does this estimation carry over to all current Haskell implementations, or is there need to pay special attention to stack size? Best, Elke. Software Development EsPresto AG ----------------------------------------------------------------- kasimir@espresto.com Breite Str. 30-31 Tel/Fax: +49-30-90 226-750/-760 10178 Berlin/Germany
participants (3)
-
Elke Kasimir -
Nick Name -
Rajiv Patel