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

Thank you Pascal,

This is brilliant. My apologies for not responding earlier but I was busy
playing with the code to see what else I might be able to extrapolate from
it.

Unless I misunderstand your conceptual approach, you were (gently)
suggesting that I had not really defined the problem well. BTW - I really
appreciated you noting the missed opportunity of making a useful higher
order procedure based on one simple example.

Please excuse my ignorance here but I'm trying to understand certain parts
of your code (in context).

For example:
(let (((let ((item (what 'first from-where)))

'let' I understand. However, your use of 'first - no clue at all.

'first resolves to first - which is a symbol. I know (yeah - sure :) that I
can't use your symbol first on a string but in the context of your code, it
seems that first referred to the first 'word' of the string sentence defined
using position (to first locate the start position of the word 0 as default
and end position - positions start from 0 to length of string -1). Then
'rest which is the rest of the sentence as yet unprocessed. Your 'first and
'rest are the equivalent of first and rest (car and cdr) for lists???

I've never seen this used in Scheme code as yet: 'first 'rest. (Solution:
look at more code and annoy people politely :)

Would you mind explaining it to me?

I need to really look at what you did here ... just takes a bit to sink in
.... so I understand what is happening and why you did what you did. Such a
really nice solution.

Thanks again,

Mike
"Pascal Bourguignon" <pjb@xxxxxxxxxxxxxxxxx> wrote in message
news:87r6q27u38.fsf@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
"Mike" <mcu87992@xxxxxxxxxxxxxx> writes:
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).

For example, you could say that you want to collect the words of the
sentence:

(define sentence "This is a sentence.")

(collect word sentence)
--> ("This" "is" "a" "sentence.")


sentence is defined.

We need to define collect and word. For word we will need some kind
of representation of what a word is, that will allow us to find and
extract the words from the sentence. For this, we can use a
procedure. Therefore, collect will be a higher order procedure.

Let's try and see how we could define the action of collecting
something from some-where, abstractly:

(define (collect what from-where)
(let ((item (what 'first from-where)))
(if (null? item)
'()
(cons (car item)
(collect what (what 'rest from-where))))))

Sounds good, no?

So now we can try to implement the function word:

(define (word message sentence)
(cond
((eq? message 'first)
;; find the first word and extract it:
(if (string=? "" sentence)
'()
(list (substring sentence 0 (or (position #\space sentence)
(string-length sentence))))))
((eq? message 'rest)
;; find the rest of the sentence and extract it:
(let ((next-space (position #\space sentence)))
(if next-space
(substring sentence (+ 1 next-space) (string-length
sentence))
"")))))


(define (position char string)
(let loop ((p 0))
(cond
((<= (string-length string) p) #f)
((char=? char (string-ref string p)) p)
(else (loop (+ 1 p))))))



C/SCHEME[16]> (collect word sentence)
("This" "is" "a" "sentence.")


Yes, you're right, higher order function for higher order functions
are not necessarily a good thing. Functions can be used to represent
any kind of data structure. Closures are equivalent to objects, and
we can build all scheme from only lambda.

But what's interesting in collect is that it can be used to collect
other kind of things:


(define (odd-numbers message liste)
(cond
((eq? message 'first)
(cond
((null? liste) '())
((and (integer? (car liste))
(odd? (car liste))) (list (car liste)))
(else (odd-numbers message (cdr
liste)))))
((eq? message 'rest)
(cond
((null? liste) '())
((and (integer? (car liste))
(odd? (car liste))) (cdr liste))
(else (odd-numbers message (cdr
liste)))))))

C/SCHEME[29]> (collect odd-numbers '(1 2 3 4 5 "abc" def 7 8))
(1 3 5 7)

--
__Pascal Bourguignon__ http://www.informatimago.com/

PLEASE NOTE: Some quantum physics theories suggest that when the
consumer is not directly observing this product, it may cease to
exist or will exist only in a vague and undetermined state.


.

Relevant Pages

  • Re: Newbie - stuck - need a small push on higher order procedures
    ... practical for string procedures mainly. ... There are no multiple bindings, only multiple uses, no different from ... (define (odd-numbers message liste) ...
    (comp.lang.scheme)
  • Newbie: using first to mimic car in procedure.
    ... seems that first referred to the first 'word' of the string sentence defined ... 'rest are the equivalent of first and rest (car and cdr) for lists??? ... (define (odd-numbers message liste) ...
    (comp.lang.scheme)
  • Re: Newbie - stuck - need a small push on higher order procedures
    ... There are no multiple bindings, only multiple uses, no different from ... (define (position char string) ... (define (odd-numbers message liste) ...
    (comp.lang.scheme)
  • Re: hmmm ... a solution but not a high order procedure.
    ... you stayed with car cdr and a couple of minor procedures ... ... (define (position char string) ... Yes, you're right, higher order function for higher order ... (define (odd-numbers message liste) ...
    (comp.lang.scheme)
  • Re: hmmm ... a solution but not a high order procedure.
    ... Since ones that go together are likely to be adjacent in a sorted list, if you compare each pair of adjacent filenames with some sort of string difference function, and limit it to some magic number for "these two things are really different", then you can use my partition function to sort them for you. ... you stayed with car cdr and a couple of minor procedures ... ... (define (odd-numbers message liste) ...
    (comp.lang.scheme)
Loading