The longest descending sequence in Lisp

Question

I am working on some issues for my upcoming exam and I need help with this Lisp function. I work at CLISP. I have to find the longest descending sequence consisting of only odd numbers in the list. Example:

(longest '(13 9 3 7 4 7 5 3 2 8 15 11 9 7 3)) 

Must return:

 (15 11 9 7 3) 

The only mandatory requirement is that the function must be implemented recursively :)

Answer 1

With continuous subsequences easy. Also, I am not lisp, so I have to explain it in words.

• Calling a recursive helper with additional arguments a) the longest found b) the length of this c) the current subsequence d) its length. Initially this is () 0 () 0.
• While the head of the list is even, repeat on the tail.
• Run current with the first odd sign, return to the tail.
• If the head is even or the head is not less than the previous element, the current sequence stops. Compare its length with the longest sequence previously found. If the current is longer, it becomes the longest, otherwise forget the current. Go to 2.

When the end of the list is reached, the longer of the two memorized lists will be the answer.

Answer 2

You can do this in one step using recursion (which will be faster and more efficient than the method I'm going to suggest), but it can be more readable, modular and simpler for the code, if you create all possible solutions first, filter those that are valid and then return the best of these solutions.

To do this, you will need a generator and matching function (I would suggest two nested lists for this problem), a filter function (write this, reduce oddness, then see lisp "remove-if-not funciton) and a decrease function (return the best solution (the longest list) from filtered).

The SICP section discusses this approach style: http://mitpress.mit.edu/sicp/full-text/book/book-ZH-15.html#%_sec_2.2

The signal processing engineer will find it natural to conceptualize these processes in terms of signals flowing through a cascade of stages ...

Answer 3

The algorithm, as Daniel answers , has been translated into Haskell with some settings:

 longest_sub xs = g2 xs [] 0 where g2 [] a _ = a g2 (x:t) ai | even x = g2 tai | otherwise = g4 t [x] 1 where g4 [] bj = if j>i then reverse b else reverse a g4 xs@ (x:t) bj | even x || x >= head b = if j>i then g2 xs bj else g2 xs ai | otherwise = g4 t (x:b) (j+1) 

In general, Lisp:

 (defun longest (xs) (prog ((a nil) (i 0) bjx) ; var decls G2 (if (null xs) (return (reverse a))) ; code (setf x (car xs) xs (cdr xs)) (if (evenp x) (go G2)) G3 (setf b (list x) j 1) G4 (if (null xs) (if (> ji) (return (reverse b)) (return (reverse a)))) (setf x (car xs) xs (cdr xs)) (when (evenp x) (if (> ji) (setf abij)) (go G2)) (when (>= x (car b)) (if (> ji) (setf abij)) (go G3)) (setf b (cons xb) j (+ j 1)) (go G4))) 

A function call is an illustrious GOTO after all, isn't it?

see also: prog doc page .