## Inserting a letter recursively

Posted by

scheme, recursion, functional
**Alpheus**, 02 May 2013 - · 904 views
NOTE: This is not complete. Touch ups, corrections, and changes will be made. This may be an article in the first future. But this is more of me working through the logic of a problem I was working on earlier last week and this week. And I'm sharing.

function needed to make [rest of lists]

what we know:

letter to insert, (we'll call ins-ltr)

the original list (list e a r), (we'll call inserting-list)

therefore there will be (first inserting-list) (rest inserting-list)

what is the base case? (ins-one "w" empty)

we know that the function returns a list of lists

so it would return (list (list "w"))

so now we know this:

so this first iteration would look like

so (ins-one ins-ltr (list a r)) will create

that the first list of (ins-one "w" (list "e" "a" "r")) is (list "w" "e" "a" "r").

Therefore the general shape is: (cons (list "w" "e" "a" "r") [rest of lists])

or

(cons (list "w" "e" "a" "r") [f1])

Now that last iteration has returned the inserted letter as a new list of lists (list (list "w")),

we now can begin to construct [rest of lists].

In the template, I have all the values and calls that could be used. So let's see if we can remove whatever we don't need.

We are going to keep (cons ins-ltr inserting-list) and (ins-one ins-ltr (rest inserting-list)), for the reasons already mentioned.

[ins-ltr] is being used in the two functions that we are keeping and seems to have no use outside of that. So we'll remove it.

Also, [inserting-list] is also being used in the two functions and also seems to have no use outside of that. So we'll remove that as well.

So now our template with the next-3 iteration data looks like:

Since (first (list "r")) comes out to be "r", we can say that the first argument will be a letter. And (list (list "w")) will be a list of lists.

So the second argument will be a list of lists. So now our template for this auxilary function will look like:

a-letter -> "r"

list-of-lists -> (list (list "w"))

(first list-of-lists) -> (list "w")

(rest list-of-lists) -> empty

Let's look at the data:

(w e a r)

(e w a r)

(e a w r)

(e a r w)

We know that the first iteration of [ins-one] will give the first list and [rest of lists].

The second iteration of [ins-one] will give the second list and [rest of lists].

The third iteration of [ins-one] will give the third list and [rest of lists].

The fourth iteration of [ins-one] will give the fourth list.

[rest of lists] gives us partial lists which are passed to the previous recursive call to make those lists more complete.

The fourth iteration gives (list (list "w")). The third iteration gives the third list (cons "w" (list "r"))

and the [rest of lists] (f1 "r" (list (list "w"))). As we can see, the third iteration gives us a partial list of the third list.

As well as having [f1] work on "r" and partial list of lists (list (list "w")) of the fourth list.

[f1] produces a list of lists which is more complete as the previous recursive calls execute. We know that the partial list of the fourth list

must produce (list "r" "w"). A straightforward way to handle that is (cons "r" (list "w")) or (cons a-letter (first list-of-lists)). And since

this is a list-of-lists and [f1] must work on list-of-lists recursively.

So now our [f1] template looks like the following:

So that means when (f1 "r" empty) is called it should return empty. Now we know what the base case is. And with that we know we can remove

the standalone list-of-lists. And lastly we know what the structure of [f1] will be.

So now the template with the next-3 iteration data is the following:

(ins-one w (list e a r)) ;(w e a r) ;(e w a r) ;(e a w r) ;(e a r w)must be in this order

function needed to make [rest of lists]

what we know:

letter to insert, (we'll call ins-ltr)

the original list (list e a r), (we'll call inserting-list)

therefore there will be (first inserting-list) (rest inserting-list)

what is the base case? (ins-one "w" empty)

we know that the function returns a list of lists

so it would return (list (list "w"))

so now we know this:

(define (ins-one ins-ltr inserting-list) (cond [(empty? inserting-list) (list (list ins-ltr))] [else ... ins-ltr ... inserting-list ... (cons ins-ltr inserting-list) ; example (cons "w" (list "e" "a" "r")) ... (first inserting-list) ... (rest inserting-list)]))since we are solving this recursively we know that [ins-one] has to be applied to the rest of [inserting-list]

(define (ins-one ins-ltr inserting-list) (cond [(empty? inserting-list) (list (list ins-ltr))] [else ... ins-ltr ... inserting-list ... (cons ins-ltr inserting-list) ; example (cons "w" (list "e" "a" "r")) ... (first inserting-list) ... (ins-one ins-ltr (rest inserting-list))]))we also know that there is an auxilary function that creates [rest of lists], (we'll call it f1, for now)

so this first iteration would look like

(define (ins-one ins-ltr inserting-list) (cond [(empty? (list "e" "a" "r")) (list (list "w"))] [else ... "w" ... (list "e" "a" "r") ... (cons "w" (list "e" "a" "r") ... (first (list "e" "a" "r")) ; (first (list "e" "a" "r")) = "e" ... (ins-one "w" (rest (list "e" "a" "r")))])) ; (rest (list "e" "a" "r")) = (list "a" "r")the next-2 iteration of this function will work on (list a r)

so (ins-one ins-ltr (list a r)) will create

(define (ins-one ins-ltr inserting-list) (cond [(empty? (list "a" "r")) (list (list "w"))] [else ... "w" ... (list "a" "r") ... (cons "w" (list "a" "r") ... (first (list "a" "r")) ... (ins-one "w" (rest (list "a" "r")))]))the next-3 iteration would be

(define (ins-one ins-ltr inserting-list) (cond [(empty? (list "r")) (list (list "w"))] [else ... "w" ... (list "r") ... (cons "w" (list "r") ... (first (list "r")) ... (ins-one "w" (rest (list "r")))]))the last iteration would be

(define (ins-one ins-ltr inserting-list) (cond [(empty? empty) (list (list "w"))] [else ... "w" ... (empty ... (cons "w" empty) ... (first empty); you can't (first empty) ... (ins-one "w" (rest empty))])) ; you can't (rest empty)Because the last iteration returns (list (list "w")), so iteration next-3 now looks like

(define (ins-one ins-ltr inserting-list) (cond [(empty? (list "r")) (list (list "w"))] [else ... "w" ... (list "r") ... (cons "w" (list "r") ... (first (list "r")) ... (list (list "w"))])) ; replaced recursive call with returned value of last iteration ; in other words (ins-one "w" (rest empty)) = (list (list "w"))We know based on earlier analysis of the data that [f1] will create [rest of lists]. We also know

that the first list of (ins-one "w" (list "e" "a" "r")) is (list "w" "e" "a" "r").

Therefore the general shape is: (cons (list "w" "e" "a" "r") [rest of lists])

or

(cons (list "w" "e" "a" "r") [f1])

Now that last iteration has returned the inserted letter as a new list of lists (list (list "w")),

we now can begin to construct [rest of lists].

In the template, I have all the values and calls that could be used. So let's see if we can remove whatever we don't need.

We are going to keep (cons ins-ltr inserting-list) and (ins-one ins-ltr (rest inserting-list)), for the reasons already mentioned.

[ins-ltr] is being used in the two functions that we are keeping and seems to have no use outside of that. So we'll remove it.

Also, [inserting-list] is also being used in the two functions and also seems to have no use outside of that. So we'll remove that as well.

So now our template with the next-3 iteration data looks like:

(define (ins-one ins-ltr inserting-list) (cond [(empty? (list "r")) (list (list "w"))] [else ... (cons "w" (list "r") ... (first (list "r")) ... (list (list "w"))])) ; replaced recursive call with returned value of last iteration ; in other words (ins-one "w" (rest empty)) = (list (list "w"))To construct [rest of lists] (first (list "r")) and (list (list "w")) will have to be used somehow. [f1] will use both of these values.

Since (first (list "r")) comes out to be "r", we can say that the first argument will be a letter. And (list (list "w")) will be a list of lists.

So the second argument will be a list of lists. So now our template for this auxilary function will look like:

(define (f1 a-letter list-of-lists) (cond [(empty? list-of-lists) ...] [else ... a-letter ... list-of-lists ... (first list-of-lists) ... (rest list-of-lists)]))And the template for [ins-one] now looks like this:

(define (ins-one ins-ltr inserting-list) (cond [(empty? (list "r")) (list (list "w"))] [else ... (cons "w" (list "r") (f1 (first (list "r")) (list (list "w"))])) ; replaced recursive call with returned value of last iteration ; in other words (ins-one "w" (rest empty)) = (list (list "w"))Using next-3 iteration, let's look at the values we have so far:

a-letter -> "r"

list-of-lists -> (list (list "w"))

(first list-of-lists) -> (list "w")

(rest list-of-lists) -> empty

Let's look at the data:

(w e a r)

(e w a r)

(e a w r)

(e a r w)

We know that the first iteration of [ins-one] will give the first list and [rest of lists].

The second iteration of [ins-one] will give the second list and [rest of lists].

The third iteration of [ins-one] will give the third list and [rest of lists].

The fourth iteration of [ins-one] will give the fourth list.

[rest of lists] gives us partial lists which are passed to the previous recursive call to make those lists more complete.

The fourth iteration gives (list (list "w")). The third iteration gives the third list (cons "w" (list "r"))

and the [rest of lists] (f1 "r" (list (list "w"))). As we can see, the third iteration gives us a partial list of the third list.

As well as having [f1] work on "r" and partial list of lists (list (list "w")) of the fourth list.

[f1] produces a list of lists which is more complete as the previous recursive calls execute. We know that the partial list of the fourth list

must produce (list "r" "w"). A straightforward way to handle that is (cons "r" (list "w")) or (cons a-letter (first list-of-lists)). And since

this is a list-of-lists and [f1] must work on list-of-lists recursively.

So now our [f1] template looks like the following:

(define (f1 a-letter list-of-lists) (cond [(empty? list-of-lists) ...] [else (cons a-letter (first list-of-lists)) ... list-of-lists (f1 a-letter (rest list-of-lists))]))Now we know that [f1] should return a list of lists. Also based on the fourth list, this list of lists should be (list (list "r" "w")).

So that means when (f1 "r" empty) is called it should return empty. Now we know what the base case is. And with that we know we can remove

the standalone list-of-lists. And lastly we know what the structure of [f1] will be.

(define (f1 a-letter list-of-lists) (cond [(empty? list-of-lists) empty] [else (cons (cons a-letter (first list-of-lists)) (f1 a-letter (rest list-of-lists)))]))What we said earlier is that the first list is the first list of a list of lists. To make that happen, we have to combine the two.

So now the template with the next-3 iteration data is the following:

(define (ins-one "w" (list "r")) (cond [(empty? (list "r")) (list (list "w"))] [else (cons (cons "w" (list "r")) (f1 (first (list "r")) (list (list "w"))])) ; replaced recursive call with returned value of last iteration ; in other words (ins-one "w" (rest empty)) = (list (list "w"))The actual code for [ins-one] is:

(define (ins-one ins-ltr inserting-list) (cond [(empty? empty) (list (list ins-ltr))] [else (cons (cons ins-ltr inserting-list) (f1 (first inserting-list) (ins-one ins-ltr (rest inserting-list))))]))