Re: Hints on recursion

"zion_zii" <nick.kigs@xxxxxxxxx> writes:

> 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
> cant use the
> (+ (recurse the same function) 1) construct nor introduce any symbol
> that keeps track of the count. (+ isnt included in what to use for this
> problem)
>
> 2. Use recursion only for the problem therefore, you cant use any of
> the loops
>
> 3. You cant use any of the binding forms either e.g let etc
>
> You cant use anything else not included in line 1 above.
>
> Okay. I know this is easy for almost all of you but Im learning. I
> would NOT like the answer to this problem just hints (otherwise Im
> going to despise myself for not thinking about the answer you give) so
> I can understand the solution better.
>
> Thanks in advance for your help. VIVA lisp!!

First, is it exactly twice or at least twice? Some think that if if
_occurs_ thrice, it occurs twice too...

Next, since you mustn't use arithmetic, you can use logic. (well, you
could build your own arithmetic, Church numbers ;-) but let's keep it simple).


Can you define several functions, or must you define only one big
recursive function?

For (twice 'e '(e . rest)) = (once 'e . rest)
and (once 'e '(e . rest)) = (none 'e . rest)

Solution at: http://paste.lisp.org/display/14113




If you can define only one function, then you'll need to track the
state. In effect, you'll be implementing a DFA:


NIL NIL T
^ ^ ^
| | |
(end) (end) (end)
| | |
| | |
o---->[zero]-----(e)----->[one]------(e)----[twice]------(e)---> NIL
| ^ | ^ | ^
| | | | | |
+----+ +----+ +----+ +----+ +----+ +----+
| | | | | |
+--(not e)--+ +--(not e)--+ +--(not e)--+


Here is an implementation of this DFA: http://paste.lisp.org/display/14113#1
(it's slightly different from the DFA drawn above; exercice: correct
the diagram to match the function).



--
__Pascal Bourguignon__ http://www.informatimago.com/
The rule for today:
Touch my tail, I shred your hand.
New rule tomorrow.
.

Relevant Pages

  • Hints on recursion
    ... I am just learning lisp and I was doing some exercises and got stuck. ... Given a list (lst) and a key, return true if a occurs twice in the ... cant use the ... (+ (recurse the same function) ...
    (comp.lang.lisp)
  • Re: Should the final have been postponed ?
    ... competition in the World and you cant see sweet bugger all. ... As the Premier Rugby competition in the world that doesn't involve ... He did get the ball thrown to ... I saw a stat saying he'd caught it twice! ...
    (rec.sport.rugby.union)
  • Re: Vienna
    ... Stallions thousands of times. ... I cant WAIT. ... Bring Kleenex. ... I've seen them twice and bawled through most of it. ...
    (rec.equestrian)
  • Re: The Chelsea disgrace
    ... United have already been asked to play twice in three days in the ... Passes a pointy hat with a big D on it.... ... Hey Ted I cant take from you your and only school achievement. ...
    (uk.sport.football.clubs.liverpool)
  • Re: The Chelsea disgrace
    ... United have already been asked to play twice in three days in the ... Passes a pointy hat with a big D on it.... ... Hey Ted I cant take from you your and only school achievement. ...
    (uk.sport.football.clubs.liverpool)