Checking whether an object is a “listdiff” in Scheme

Question

A listdiff is a pair whose car is L and whose cdr is eq? to either L, or to (cdr L), or to (cdr (cdr L))), etc. The cdr of a listdiff need not be a list; it may be any object.

A listdiff D represents the prefix of (car D) that precedes (cdr D). For example, suppose ils is the improper list (a e i o u . y). Then (cons ils ils) returns an empty listdiff, (cons ils (cdr (cdr ils))) returns a listdiff with the same elements as the list (a e), and (cons (cdr ils) 'y) returns a listdiff with the same elements as (e i o u). Conversely, neither (cons '() ils) nor (cons ils (append '(a e i o u) 'y)) returns a listdiff.

I want to create the following procedure on Racket:

(listdiff? obj)

Returns #t if obj is a listdiff, #f otherwise.

Can anyone give me indications to do it?

For what it's worth, this appears to be a homework assignment (that's from 2008, so perhaps a professor is reusing assignments, or you're working through some exercises). In either case, you should attribute the sources. — Joshua Taylor
The whole concept of "listdiff" seems a bit over-engineered. It'd be easier to say "a listdiff is a cons whose car is a list L and whose cdr is a tail of L". — Joshua Taylor

Sylwester Sylwester · Accepted Answer · 2017-02-28T15:23:32

Here is a skeleton you can use.

(define (listdiff? pair)
  (define l (car pair))      ; l
  (define needle (cdr pair)) ; needle is what to look for in l
  (define (search haystack)
    ;; #t when haystack looks the same as needle
    ;; #f if haystackk is the empty list
    ;; otherwise recurse to (cdr haystack)
    )

  (search l))

Checking whether an object is a “listdiff” in Scheme

1 Answers