Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.






Inserting a letter recursively

Posted by Alpha_ProgDes, 02 May 2013 · 605 views

scheme recursion functional
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.

(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))))]))





December 2014 »

S M T W T F S
 123456
78910111213
14151617 18 1920
21222324252627
28293031   

Recent Entries

PARTNERS