Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

Scheme Programming Language

Newbie - need a small push on recursion / higher order procedures


Hi,

I'm trying to learn higher order procedures - my preferred result was to
have been to use a procedure as a param but I'm not close.  I can do
something simple:

Sum the values when a process is applied to each number between start-num
and end-num inclusive.  It was an attempt at a general purpose procedure and
based on this, I had hope to extrapolate to the word / string problem ... no
joy.

(define [sum process start-num next end-num]
  (if (> start-num end-num) ;
          0 ;
      (+ (process start-num)
           (sum process (next start-num) next end-num))))

(define [cube x]
  (* x x x ))
(define [inc x]
 (+ x 1))
(sum cube 1 inc 3) ;==> 36

I thought that a task of creating a list containing the individual words of
a sentence would be ideal because it appears to involve repetitions of two
steps: creating a word and adding that word to list of the words remaining
to be processed.

This is the desired result: ("This" "is" "a" "sentence").
This is what I am getting:
(("T" "h" "i" "s" ("i" "s" ("a" ("s" "e" "n" "t" "e" "n" "c" "e")))))

In English, I'm starting out with a string "This is a sentence".  I move the
characters of this string into a list.  Then create a new list of the words
in the list of characters (using #\space as separator) and add that word to
the rest of the words in
the list of characters that remain.

Creating one word is simple enough:

(define (create-word a-list)
  (if (empty? a-word)
    empty
    (if (eq? (first a-word) #\space)
       empty
       (cons (first a-word) (create-word (rest a-list))))

; This is the best I can come up with so far and it fails badly.

(define a-sentence (string->list "This is a sentence"))
(define space #\space)
(define (create-sentence words-left)
  (define (create-word sentence)
    (if (empty? sentence)
        empty
        (if (eq? (first sentence) space)
            ; space char suggests word present so create this word
            (create-sentence (rest sentence))
            ; calls the parent to build the word list
            (cons (list->string (list (first sentence)))
                  (create-word (rest sentence))))))
  (if (empty? words-left)
      empty
      (cons (create-word words-left) () )))
(create-sentence a-sentence)
;==>
;(("T" "h" "i" "s" ("i" "s" ("a" ("s" "e" "n" "t" "e" "n" "c" "e")))))

I thought it might be more efficient to convert a word (list of characters)
into a string and cons it to the list of remaining words.  It's wrong
clearly.

I've been at this for hours and suspect I'm missing the bleeding obvious.

Could someone please give me a nudge in the right direction to get this
basic code working?  Is this a problem in which you might consider using a
procedure as a param?  If so ... any hints?  If not ... your reasoning would
be much appreciated.

Also, how would you approach a task like this (excluding complex functions)?

Thanks in advance,

Mike

The problem is that "create-word" either returns a list of strings, or a
list of list of strings. You probably want to split create-word
into two functions.

Another problem is that "(list->string (list (first sentence)))" just
converts a char into a string. (You could just as well have written
"(string (first sentence))".) Instead of "(cons (string->string..) ...)",
you might want to use something like "(apply string (cons (first
sentence) ...))".

> Is this a problem in which you might consider using a
> procedure as a param?  If so ... any hints?  If not ... your reasoning would
> be much appreciated.

> Also, how would you approach a task like this (excluding complex functions)?

I would do it like this:

(let ((result '())
      (curr-word '()))
  (define (add-curr-word-to-result!)
     ...)
  (for-each (lambda (achar)
               (define (add-achar-to-curr-word!)
                  ...)
               (if (space? achar)
                   (add-curr-word-to-result!)
                   (add-achar-to-curr-word!)))
            (string->list sentence))
   ...)

The nice thing about lisp is that it doesn't force you to use one
programming technique (at least in the ideal world). I would say that this
problem is better solved by not using functional programming, but its up
to you to choose how to do things.

"Mike" <mcu87@bigpond.net.au> writes:
> I thought that a task of creating a list containing the individual words of
> a sentence would be ideal because it appears to involve repetitions of two
> steps: creating a word and adding that word to list of the words remaining
> to be processed.

> This is the desired result: ("This" "is" "a" "sentence").
> This is what I am getting:
> (("T" "h" "i" "s" ("i" "s" ("a" ("s" "e" "n" "t" "e" "n" "c" "e")))))

> In English, I'm starting out with a string "This is a sentence".  I move the
> characters of this string into a list.  Then create a new list of the words
> in the list of characters (using #\space as separator) and add that word to
> the rest of the words in
> the list of characters that remain.

So you have a string and you want to split it on spaces.

(define (split-string string separator)
   ...)

Splitting here means to collect in a list substrings.  

Let's say these substrings start from the position after the space (or
at the beginning if the first character is not a space), and end at
the position of the next space.

(This definition means that if there are several contiguous spaces, or
a space at the beginning or the end, we'll collect empty substrings).

So the algorithm becomes obvious:  we find the next space from the
start and take the substring from the start to this next space, and
loop (= recurse) on the rest of the string (ie the substring from 1 +
position of next space).  Note that it will be an iterative process,
whether you implement it with a recursive procedure or an iterative
procedure.

(define (split-string string separator)
  (let ((next-separator (position separator string)))
     (if next-separator
        (cons (substring string 0 next-separator)
              (split-string (substring string (+ 1 next-separator)
                                       (string-length string))
                             separator))
        (list string))))

Now, there's a problem here, since we are creating a lot of new
substrings (in the recursive call to split-string) that are not needed,
only to keep track of the start of the next word.  It would be better
to pass this start position as argument to the recursive call:

(define (split-string string separator)
  (split-string-1 string separator 0))

(define (split-string-1 string separator start)
  (let ((next-separator (position separator string start)))
     (if next-separator
        (cons (substring string start next-separator)
              (split-string-1 string separator (+ 1 next-separator)))
        (list (substring string start (string-length string))))))

(define (position char string start)
  (cond
    ((<= (string-length string) start)       #f)
    ((char=? char (string-ref string start)) start)
    (else                                    (position char string (+ 1 start)))))

Since this kind of recursive procedure to make a look occurs often, in
scheme we can use a named let to avoid creating a global function:

(define (split-string string separator)
    (let split-string-1 ((string    string)
                         (separator separator)
                         (start     0))
         (let ((next-separator (position separator string start)))
           (if next-separator
               (cons (substring string start next-separator)
                     (split-string-1 string separator (+ 1 next-separator)))
               (list (substring string start (string-length string)))))))

This is really the same as above, a recursive function, only that the
split-string-1 name is not in global, but only in the lexical scope of
the named let.  So now, since they never change, we can skip the string
and separator parameters of the split-string-1 function, and let it
refer them in the outer scope:

(define (split-string string separator)
    (let split-string-1 ((start     0))
         (let ((next-separator (position separator string start)))
           (if next-separator
               (cons (substring string start next-separator)
                     (split-string-1 (+ 1 next-separator)))
               (list (substring string start (string-length string)))))))

There remains a little problem: the recursive call is not a terminal
call, since cons must be called after it returns.  So we will use O(n)
stack space.   We can modify it as an accumulator recursive function
to have tail recursive call.  But since lists are better constructed
(with cons) from the head than from the tail, we'll accumulate the
result in the reverse order:

(define (split-string string separator)
    (reverse
     (let split-string-1 ((start 0)
                          (result '()))
          (let ((next-separator (position separator string start)))
            (if next-separator
                (split-string-1
                 (+ 1 next-separator)
                 (cons (substring string start next-separator)
                       result))
                (cons (substring string start (string-length string))
                      result))))))

So you can now easily implement the sentence word splitting:

(define (create-sentence  text)  (split-string text #\space))

(create-sentence "This is  a sentence! ")
--> ("This" "is" "" "a" "sentence!" "")

If you want to remove the empty strings you can do it in
create-sentence, keeping the original definition of split-string which
may be more useful in other places.

(define (remove item list equal?)
  (cond ((null? list) list)
        ((equal? item (car list)) (remove item (cdr list) equal?))
        (else    (cons (car list) (remove item (cdr list) equal?)))))

(define (create-sentence  text)  
   (remove "" (split-string text #\space) equal?))

--
__Pascal Bourguignon__                     http://www.informatimago.com/
Small brave carnivores
Kill pine cones and mosquitoes
Fear vacuum cleaner

Mike  writes:
> [...]
> I thought that a task of creating a list containing the individual words of
> a sentence would be ideal because it appears to involve repetitions of two
> steps: creating a word and adding that word to list of the words remaining
> to be processed.

There is a reason the authors of "The Little Schemer" use only numbers
and lists of atoms to explain recursion and HOP.  Playing with strings
is more complicated, as you can see from the other answers.

That's not to say you should not fiddle with strings if you want.  But
it's an orthogonal matter and you don't need this additional
complication when learning recursion.

--
Emlio C. Lopes                            Ich leb und wei nit wie lang,
Munich, Germany                            ich stirb und wei nit wann,
                                           ich fahr und wei nit wohin,
                 (Martinus von Biberach)   mich wundert, dass ich frhlich bin!

Hi all,

Thank you for all of the fantastic replies.  I'm looking at them all to see
how each approached the task.  It seems that it is possible to create a HOP
(courtesy Emilio Lopes) but perhaps the problem didn't specifically require
that approach.

Unless I misunderstood, I can see that a HOP can be created that allows me
to specify the character I use to separate the words in the string so that
it becomes more general purpose.

Please refer to my 'solution' - not elegant but getting there.  I think I
picked up on all of the observations about the errors I made in my original
attempt.  And kept repeating the mantra 'build lists with cons'.

If the problem was create a list containing the string values of the
individual words (separated by spaces) in a string.

Then the approach could be:

loop
  build a sentence (list of words)
    loop
     build a list (word)
        cons the first character onto
        the rest of the characters remaining
      until first instance of stop character (space)
  format list (word) to string
  cons this word onto
  the unprocessed words in the
  (leading spaces stripped) list
until the param list is empty

I didn't used the Scheme form of substring because it seemed unnecessary but
that may be my inexperience rather than anything else.  I think I can write
a procedure called substring with the little knowledge of Scheme that I
have.  And I think I could write a procedure called Pos (returns the
position in a string of the first occurrence of a string) which might have
been useful in this problem.

The code examples you provided are gold - thank you.  Will take time to
digest.

Kindest regards,

Mike

Hi all,

Sorry ... ended up as a new thread.

Before I look at any replies I thought I might give it another go.

The original objective was to create a higher order procedure using a
procedure as a param to construct a list of words contained in a string.

While I have a solution, it is not a higher order procedure of the type I
was hoping for.  It seemed to me that the task didn't lend itself to this
approach - your comments may prove me completely wrong (most likely).

I see no value of making a fake higher order procedure by placing
definitions inside the master procedure simply to show it can be done.  I
see more value having the contributing procedures kept outside the main one
because if necessary, these can be modified to get different results.  Be
interested in alternate thoughts about this.

I'm certain there are many ways to solve the problem - but I wanted to avoid
using more than the basic Scheme procedures.

I'd be interested in feedback on style / problem solving approach.  I have
yet to optimise the code but I wanted to make certain that what was
happening was easy to read (and worked!).

Minor adjustments can result in spaces being included either as individual
string elements containing one space or n spaces.

Now to see what others wrote.

Mike
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Problem: convert a string (sentence)
;                into a list of strings (word and punctuation)
;                excluding space characters.
;
; Expected Result: ("This" "is" "a" "sentence" ".")
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; CONSTANTS
;
(define a-list (string->list "This is    a  sentence   ."))
;;;;;;;;;;;;;;;;;;;;;;;;
(define [space? x]
  (eq? x #\space))
(define [make-word a-list] ; returns a list of chars (word)
  (cond
    [(empty? a-list) empty]
    [(space? (car a-list)) empty]
    [else
     (cons (car a-list) (make-word (cdr a-list)))]))
(define [strip-word a-list]
  (cond
    [(empty? a-list) empty]
    [(space? (car a-list)) (cdr a-list)]
    [else
     (strip-word (cdr a-list))]))
(define [make-string a-list]
  (list->string a-list))
(define [make-sentence a-list]

  (cond
    [(empty? a-list) empty] ; Nothing left.  Stop.
    [(space? (car a-list)) (make-sentence (cdr a-list))]
;                            ; list isn't empty.
;                            ; strip spaces
    [else
       (cons (make-string (make-word a-list))
           (make-sentence (strip-word a-list)))]))
; TEST
(make-sentence a-list)
; returns
;==> ("This" "is" "a" "sentence" ".")

[...]

Hi Emilio,

Thanks for the response.  I don't understand what you mean by "... it's and
orthogonal matter ...".  Orthogonal means 'related to or composed of right
angles' (English definition).  What does the term mean in the context of
programming?  Do you mean branching (binary) processes?  Please excuse me if
I am using the wrong phrasing - but I mean, a process that goes in one of
two directions based upon a predicate?

Kindest regards,

Mike

Mike writes:
> Thanks for the response.  I don't understand what you mean by
> "... it's and orthogonal matter ...".  Orthogonal means 'related to
> or composed of right angles' (English definition).  What does the
> term mean in the context of programming?  Do you mean branching

He means you can study strings or you can study recursion: they are
somewhat independent topics. There were certain people who called
themselves hackers, still do, even though they are not engaged in
breaking into your computer, and they like to play with language,
among other things. For them, this is actually the canonical meaning
of "orthogonal".

Search for the "Hacker's dictionary" on the web and look up "hacker",
"orthogonal", "canonical". Many of those hackers have been rather
influential.

Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc