current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 5 down vote favorite

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

;Contract:
;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

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

;Definition:

(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

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

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

;Definition:

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

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

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

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

;Definition:

(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?

share|improve this question
    
You may have misunderstood the question. Also use standard procedures as much as possible. e.g. length instead of find-len. –  abuzittin gillifirca Mar 7 '13 at 7:10
    
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). –  200_success♦ Jul 29 at 9:20

2 Answers 2

up vote 2 down vote

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.

share|improve this answer
up vote 1 down vote

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))))))
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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