This is HtDP Excercise 12.4.2:

Develop a function insert-everywhere. It consumes a symbol and a list of words. The result is a list of words like its second argument, but with the first argument inserted between all letters and at the beginning and the end of all words of the second argument.

This is what I wrote:

#lang racket

;Data Definition:
;a symbol, list of symbols

;insert-everywhere: symbol, list of symbols -> list of list of symbols
;The function returns a list of list of symbols wherein the symbol is inserted at every position

; (insert-everywhere 'a '(b c d)) -> '((a b c d) (b a c d) (b c a d) (b c d a))


(define (insert-everywhere sym los)
  (define lst-len (find-len los))
  (define (iter n)
    (cond ((= n (+ lst-len 1)) '())
          (else (cons (insert n sym los) (iter (+ n 1))))))
  (iter 0))
;The above function first finds the list length. 
;Then it itereratively inserts the symbol at every position one by one, including in the end.

;Data Definition:
;list of symbols

;find-len : list of symbols-> number
;find the length of the list

;(find-len (list 'b 'c 'd)) -> 3


(define (find-len los)
  (cond ((null? los) 0)
        (else (+ 1 (find-len (cdr los))))))

;Data Definition:
;number , symbol, list of symbols

;insert : position, element, list of symbols-> list of symbols
;insert the element in the given position in the list

;(insert 2 'a '(b c d)) -> '(b c a d)


(define (insert pos elm los)
  (cond ((= pos 0) (cons elm los))
        (else (cons (car los) (insert (- pos 1) elm (cdr los))))))

Here is the tests I conducted:

(insert-everywhere 'a '()) ; returns '((a))
(insert-everywhere 'a '(b)) ; returns '((a b) (b a))
(insert-everywhere 'a '(b c d)) ; returns '((a b c d) (b a c d) (b c a d) (b c d a))

It works, but I think this is not the way it was supposed to be solved. In their hint, they ask to use only recursion and append, but I didn't really get it. Could someone suggest a better answer?

  • \$\begingroup\$ You may have misunderstood the question. Also use standard procedures as much as possible. e.g. length instead of find-len. \$\endgroup\$ – abuzittin gillifirca Mar 7 '13 at 7:10
  • \$\begingroup\$ I also think you may have misunderstood the challenge. I believe (insert-everywhere 'a '(b c d)) should produce '(a b a c a d a). \$\endgroup\$ – 200_success Jul 29 '15 at 9:20

Check this Stack Overflow question out, which has a solution to the same problem. A simplified version would look like this

(define (insert-at pos elmt lst)
 (if (empty? lst) (list elmt)
 (if (= 1 pos)
  (cons elmt lst)
  (cons (first lst) 
        (insert-at (- pos 1) elmt (rest lst))))))

(define (insert-everywhere sym los)
  (map (lambda (i)
         (insert-at i sym los)
       (range 1 (+ 2 (length los)))))
  1. There is a function written for inserting at a particular position.

  2. Then we have our iterative function that maps over the elements in the list.

Alternatively, there is the recursive solution found in the link above. It does this by using conditions and cons (which appends to lists together). It seams a bit clunky, but map really cleans it up.

| improve this answer | |

Inserting an element into a list at some index is not really idiomatic in Lisp-like languages. With proper use of recursion, indexing is not necessary at all, and the solution is much simpler.

(define (insert-everywhere sym los)
   (define (prepend a) (lambda (as) (cons a as)))
   (if (empty? los)
       (list (list sym))
       (cons (cons sym los)
             (map (prepend (car los)) 
                  (insert-everywhere sym (cdr los))))))
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.