Encapsulating Certain Parts of List

Question

I'm trying to write a procedure that "encapsulates" (i.e. puts in a list) elements of a list between a "separator" element.

(my-proc '(1 + 2))
=> ((1) (2))

(my-proc '(x * y + z ^ 2 + 1 + 5))
=> ((x * y) (z ^ 2) (1) (5))

(my-proc '((x + 1) * y + 5))
=> (((x + 1) * y) (5))

In this case the procedure can be hard-coded to define the + symbol as the separator.

Assume that foldr (fold right operation) is defined, I'd prefer that it'd be in terms of it.

score 1 · Accepted Answer · edited Apr 09 '13 at 10:40

1

I'm not giving a full solution since this looks really homework-y.

(define (split-expr expr)
   (foldr (lambda (e es)
                  (if (eq? e '+)
                      <???>    ; do split
                      (cons (cons e (car es))
                            (cdr es))))
          <???>    ; what should start be?
          es))

edited Apr 09 '13 at 10:40

C. K. Young

219,335
46
382
435

answered Apr 09 '13 at 06:13

daniel gratzer

52,833
11
94
134

+1 for the right approach, but I'm going to edit your answer to add `??>` to indicate something to fill in. The comments on their own (without the placeholders) were really confusing. (I actually implemented the complete solution myself, of course.) – C. K. Young Apr 09 '13 at 10:39
I'm confused. start obviously can't be '(), because the operation calls on (car es) and (cdr es), but I'm not seeing what else it could be. Even then, I have no idea what the alternative clause of the if statement is supposed to accomplish, e,g, given e is 1 and es is (2 3), the result would be ((1 . 2) 3). Could you provide a little more hints please? – user1641398 Apr 09 '13 at 17:11
Well it can't be `'()` you're right, but what about `'( () )` – daniel gratzer Apr 09 '13 at 17:29
Thanks, I got it after that. But damn, just when I thought I was getting used to Scheme even something as simple as this gets beyond me without help. – user1641398 Apr 09 '13 at 17:48

score 0 · Answer 2 · edited May 23 '17 at 12:05

Just for fun, here's a version in continuation-passing style (no foldr, probably not suitable as a homework answer):

(define split/cps
  (λ (sep ls)
    (let loop ([ls ls] [k (λ (item acc)
                               (if item (cons item acc) acc))])
      (cond
        [(null? ls)
          (k #f '())]
        [(eq? sep (car ls))
          (loop (cdr ls)
                (λ (item acc)
                  (k #f (if item (cons item acc) acc))))]
        [else
          (loop (cdr ls)
                (λ (item acc)
                  (k (if item
                         (cons (car ls) item)
                         (list (car ls)))
                     acc)))]))))

Ben Kovitz · Answer 3 · 2013-04-10T13:48:46.600

Here's another way to do it, also without foldr:

(define split/values
  (λ (sep ls)
    (let loop ([ls ls])
      (cond
        [(null? ls)
          '()]
        [else
          (let-values ([(a d) (car-to-sep sep ls)])
            (if (null? a)
                (loop d)
                (cons a (loop d))))]))))

(define car-to-sep
  (λ (sep ls)
    (let loop ([ls ls] [a '()])
      (cond
        [(null? ls)
          (values '() '())]
        [(eq? sep (car ls))
          (values '() (cdr ls))]
        [else
          (let-values ([(a d) (loop (cdr ls) a)])
            (values (cons (car ls) a) d))]))))

Encapsulating Certain Parts of List

3 Answers3