Re: Hints on recursion

zion_zii wrote:
> Hello to all!!
>
> I am just learning lisp and I was doing some exercises and got stuck.
> The problem is as follows:
> Given a list (lst) and a key (a), return true if a occurs twice in the
> list. There are stipulations however and they are;
>
> 1. You are to only use COND/IF, NULL, EQ and OR. That means that you

That's going to be difficult. All the solutions I can come up with also
require FIRST and REST. (Or CAR and CDR, if you prefer).

OR is not required. It's a special case of COND.

A form that fits the pattern (OR A B C D ...) can be written as (COND
(A) (B) (C) (D) ...)

So OR is just a special flavor of COND that you use when you don't need
to evaluate any additional expressions when you find one that is true,
and so the tested expressions don't have to be nested in lists.

If you can use FIRST and REST, the test breaks down into exactly three
cases:

If the list has fewer than two elements, the answer is false/NIL.

Otherwise, divide the list into two pieces: the first element, and the
rest of the list.

The element A occurs at least twice in the list if, and only if one of
these two cases is true:

Case 1: The list is shorter than two elements.
The answer is NIL.

Case 2: The first element is A
The answer is then whether the rest of the list contains at least one
A.

Case 3: The first element is not A:
The answer is then whether the rest of the list contains at least two
A.

The third case is a recursive definition: it calls upon the ``at least
two'' function itself, but on a shorter list, so progress is made
toward terminating the recursion.

The second case is incomplete: it requires a function that determines
whether a list contains at least one A. That function is one that
handles three cases also:

Case 1: The list is empty.
The answer is NIL

Case 2: The first element is A.
The answer is T.

Case 3: The first element is not A.
The answer is whether the rest of the list contains at least one A.

And so now the definition is complete.


Here is a solution which lets you write a test for ``at least N'' for
any integer N, without using arithmetic. A list containing N items is
used to represent the integer N. Doing CDR on that list is isomorphic
to subtracting 1.

There are four cases rather than three, because we check for the
special case of N being zero (the integer-list is empty). True must be
always returned for ``at least zero items'', even if the list is empty,
so that case is tested first:

(defun contains-at-least-n (list item &optional n-list)
(cond
((null n-list) t) ;; contains at least zero? Always!
((null list) nil)
((eq (car list) item)
(contains-at-least-n (cdr list) item (cdr n-list)))
(t (contains-at-least-n (cdr list) item n-list))))

(defun contains-at-least-5 (list item)
(contains-at-least-n list item '(x x x x x)))

(defun contains-at-least-2 (list item)
(contains-at-least-n list item '(x x)))

Sorry to spoil the solution, but I thought you might enjoy this. You
can see how cases 2 and 3 became generalized:

Case 2: The first element is A.
The answer is then whether the rest of the list contains at least N
- 1 A.

Case 3: The first element is not A.
The answer is whether the rest of the list contains at least N A.

And of course only one function is needed now, because it handles any
N, so it takes both the N case and the N - 1 case.

So that you don't feel cheated, here is a new assignment: You could
generalize this function into doing subsequence matching. . Change the
CONTAINS-AT-LEAST-N function into CONTAINS-SUBSEQUENCE. The new
function does not take an ITEM parameter any more and the items in the
N-LIST are now interesting, rather than dummy placeholders:

Example calls:

(contains-subseuqence '(a b c d e) '(x)) -> NIL

(contains-subseuqence '(a b c d e) '(b)) -> T

(contains-subsequence '(a b c d e) '(a c e)) --> T

(contains-subsequence '(a b c d e) '(e c a)) --> NIL

(contains-subsequence '(a b c d e) '(a b c d e)) --> T

(contains-subsequence '(a b c d e) '(a b c d e f')) -> NIL

(contains-subsequence '(a b c d e) '(a b d e f')) -> NIL

;; all lists contain the empty list as subsequence ...
(contains-subsequence '(a b c d e) '()) -> T

;; even the empty list does
(contains-subsequence '() '()) -> T

So as you can see, the list has to contain at least all of the items in
the subsequence, and in the same order.

.

Relevant Pages

  • Re: Scheme as a religion
    ... > parentheses are great for deliminating things, ... first element of the list they start, which determines what is going to ... Programs are made up of lists. ... 'if' is not a operator or a function, but a special form. ...
    (comp.lang.scheme)
  • Re: Enumerating combinations so that consecutive combinations have a Hamming distance of two?
    ... There are five boxes that can hold one ball each. ... Add the first element back to those permutations. ... a list of lists, containing every ... The combinations can also be perceived as nodes in a graph. ...
    (sci.math)
  • Re: A way to re-organize a list
    ... I have a simple list reconstruction problem, ... and then by the first element. ... This does one more "list" step, but if your lists aren't huge the ... readability may be worth the small slow-down. ...
    (comp.lang.python)
  • IllegalArg vs NullPtr Exceptions
    ... The utility accepts Lists as arguments to several public methods. ... NullPointerException or NoSuchElementException will be thrown, ... do is invoke List's iterator method. ... Iterator next method for the first element, ...
    (comp.lang.java.programmer)
  • Re: Algorithm for inserting numbers in a list?
    ... such that the number assigned to the first element ... The requirement that the ascending ... One solution might be to use a numbering system like used in the FOCAL ... use "skip lists" to do so. ...
    (comp.theory)