Topic: List in Lists--(alanjt)

[Peter Jamtgaard]

Or maybe

Code: [Select]


(defun RecurseList (lstSublist)
 (if (= (type lstSublist) 'LIST)
  (apply 'append
   (mapcar 'recurselist
    (if (cdr lstSublist)
     (list (car lstSublist) (cdr lstSublist))
     lstSublist
    )
   )
  )
  (list lstSublist)  
 )
)
Definitely not as elegant but think that is as short as this method can go

[Peter Jamtgaard]

I like that vl-list-length function solution.

[JohnK]

Can i ask how are you guys defining "tail recursive" functions. How i learned `tail recursion' there are no instructions after the recursive call ("snapshots in time" if you will) on the stack. ...I am severely out of practice when it comes to lisp so i could be reading it wrong but some of those functions labeled as `tail recursive' are not by my knowledge.

[gile]

Hi se7en,

It's quite difficult for me to explain this in English but I *do* think the functions I posted are tail recursive.

A way to see if a LISP recursive function is tail recursive is to trace the function. If the last call on the stack returns the final result, then the function is tail recursive.

Example with the famous factorial function:

fact1 is not tail recursive:

Code: [Select]

(defun fact1 (n)
  (if (<= n 1)
    1
    (* n (fact1 (1- n)))
  )
)
fact2 calls f which is tail recursive (with an accumulator):

Code: [Select]

(defun fact2 (n / f)
  (defun f (n a)
    (if (<= n 1)
      a
      (f (1- n) (* n a))
    )
  )
  (f n 1)
)
Tracing both: (trace fact1 f) and running: (fact1 5) (fact2 5), the vlide trace window displays:

Code: [Select]

Saisie (FACT1 5)
  Saisie (FACT1 4)
    Saisie (FACT1 3)
      Saisie (FACT1 2)
        Saisie (FACT1 1)
        Résultat:  1
      Résultat:  2
    Résultat:  6
  Résultat:  24
Résultat:  120
Saisie (F 5 1)
  Saisie (F 4 5)
    Saisie (F 3 20)
      Saisie (F 2 60)
        Saisie (F 1 120)
        Résultat:  120
      Résultat:  120
    Résultat:  120
  Résultat:  120
Résultat:  120
Doing the same thing with the memb function (wich is tail recursive without accumulator) and the trunc function (the complementary function which is not tail recursive:

Code: [Select]

(defun memb (ele lst)
  (if lst
    (if (equal (car lst) ele)
      lst
      (memb ele (cdr lst))
    )
  )
)

(defun trunc (ele lst)
  (if lst
    (if (equal (car lst) ele)
      nil
      (cons (car lst) (trunc ele (cdr lst)))
    )
  )
)
Tracing both (trace memb trunc) and runing (memb 2 '(0 1 2 3)) (trunc 2 '(0 1 2 3)):

Code: [Select]

Saisie (MEMB 2 (0 1 2 3))
  Saisie (MEMB 2 (1 2 3))
    Saisie (MEMB 2 (2 3))
    Résultat:  (2 3)
  Résultat:  (2 3)
Résultat:  (2 3)
Saisie (TRUNC 2 (0 1 2 3))
  Saisie (TRUNC 2 (1 2 3))
    Saisie (TRUNC 2 (2 3))
    Résultat:  nil
  Résultat:  (1)
Résultat:  (0 1)
In both examples, with non tail recursive functions (fact1 and trunc) the last call calls the recursive function within another statement: (* n (fact1 (1- n))) and (cons (car lst) (trunc ele (cdr lst))) so that the final result can't be solved until unstacking.
With the tail recusive functions (f and memb) the last call directly calls the function: (f (1- n) (* n a)) and (memb ele (cdr lst)) and the final result is returned soon the head of the stack.

If you're no more comfortable with LISP, you can try with F# (which optimises the tail recursion).
Here're F# traductions of the memb and trunc functions, you can try here if you do not have F# (VS 2010) installed.

Code: [Select]

let rec memb ele lst =
    match lst with
    | [] -> []
    | h::t when h = ele -> lst
    | _ -> memb ele lst.Tail
   
let rec trunc ele lst =
    match lst with
    | [] -> []
    | h::t when h = ele -> []
    | _ -> lst.Head :: trunc ele lst.Tail
Then, try:
memb 199999 [0 .. 200000]
and
trunc 199999 [0 .. 200000]

The return in F# interactive should be:

Code: [Select]

> memb 199999 [0 .. 200000];;
val it : int list = [199999; 200000]

> trunc 199999 [0 .. 200000];;
Session termination detected. Press Enter to restart.

Process is terminated due to StackOverflowException.

[Lee Mac]

The way I understood 'tail-recursive' functions was that when a result was reached (perhaps n levels deep), that same result would be carried back (unmodified) through the recursive calls and be returned - hence, as you say, no expressions are to be evaluated following the return of the recursive call.

I think it is better understood from a 'trace' of the function (using gile's 'memb' function as an example):

Code: [Select]

Entering (MEMB 3 (0 1 2 3 4 5))
  Entering (MEMB 3 (1 2 3 4 5))
    Entering (MEMB 3 (2 3 4 5))
      Entering (MEMB 3 (3 4 5))
      Result:  (3 4 5)
    Result:  (3 4 5)
  Result:  (3 4 5)
Result:  (3 4 5)

The result (3 4 5) being identical for each return of the recursive call.

EDIT: Gile beat me to it

[VovKa]

How i learned `tail recursion' there are no instructions after the recursive call

how i thought 'tail recursion' there are no instructions before the recursive call.
now i'm stuck

[Lee Mac]

How i learned `tail recursion' there are no instructions after the recursive call

how i thought 'tail recursion' there are no instructions before the recursive call.
now i'm stuck

But LISP is evaluated 'inside-out' so I think you both mean the same thing - i.e. the expressions appear before the recursive call, but are evaluated using the return of the recursive call.

Am I right?

[JohnK]

Thanks gile. I will have to wait untill i get back at work (back to a computer with AutoCAD) to study the code.


My `after' statement was refering to the "backtrace". in that, there wouldnt be one with `tail recusion'.

For the record; This is how i learned to do `tail recursion'. I think i tried to start a discussion on this at one time or another...huh.

Code: [Select]

(map-car-iter
  (lambda (x) (+ x 1))
             '(1 2 3) )

(defun map-car-iter ( proc lst)
   (map-iter '() proc lst) )

(defun map-iter (sofar proc lis)
   (if (null lis)
       (reverse sofar)
       (map-iter (cons (proc (car lis))
                       sofar)
                 proc
                 (cdr lis))) )

[gile]

My `after' statement was refering to the "backtrace". in that, there wouldnt be one with `tail recusion'.

Even your 'map-iter':

Code: [Select]

Saisie (MAP-ITER nil #<USUBR @000000002b88fe80 -lambda-> (1 2 3))
  Saisie (MAP-ITER (2) #<USUBR @000000002b88fe80 -lambda-> (2 3))
    Saisie (MAP-ITER (3 2) #<USUBR @000000002b88fe80 -lambda-> (3))
      Saisie (MAP-ITER (4 3 2) #<USUBR @000000002b88fe80 -lambda-> nil)
      Résultat:  (2 3 4)
    Résultat:  (2 3 4)
  Résultat:  (2 3 4)
Résultat:  (2 3 4)

[jmcshane]

Code: [Select]

(defun My-Member ......


Classic!!!