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: applying map / foldl / foldr


Hi all,

I saw the earlier question relating to map (bit over my head
for the moment) but the person didn't appear to be asking
the same thing (but then he might have - ignorance, don't
leave home without it).

I'm able to use map, foldl and foldr on fairly simple things
where just param is involved.  I get lost when two or more
params are used.  Firstly, aside from looking at something
and thinking "this looks like map or foldl would do just
nicely", I'm uncertain about HOW to do it.  In hindsight,
probably WHEN to do it too.

Here is a very simple problem where I *think* map and
perhaps foldl might work (and I'm probably wrong).  It's a
problem in which items contained in a reference list (of
strings) match some predicate and I want to list, for each
matched item, a string that includes the matched item in
context with the adjacent 2 string items (string append 2
items in front and 2 behind the matched item).

The desired result would look something like this when an
item needs 2 adjacent items to produce the desired context,
on a list of indices '(1 2 5)
("a b c" "a b c d" "c d f")

Three matches - three contexts.  Can't place items in front
of the first item in the reference list and can't place
items after the last item in a reference list.

This is how I would go about it - please feel free to adjust
my approach if it is crap.

Produce a list of indices representing the beginning of the
context string.
Produce a list of indices representing the end of the
context string.
Loop through the list of 'beginning' indices
   string append the result of (list-ref a-list an-index)
   if not the last item then add a space " " (to avoid
having a trailing space)
   until the value for the beginning index equalled the
value of the correspond end index

That works but seems messy.  This process may be one that
could be mapped perhaps?  Here is what I've done so far:

x = the number context items
y = index of the matched item (from a list of strings)
z = is the max index of the reference list
d = reference list (document)

(define d (list "a" "b" "c" "d" "e" "f"))
(define z (- (length d)  1)); 0 base index

; get a list of the starting indiced
(define (front-ndx x)
  (define (front-ndx-helper y)
    (if (<= 0 (- y x))
        (- y x )
        (front-ndx-helper (+ y 1))))
    front-ndx-helper)
(define first-ndx (front-ndx 2))

(map first-ndx (list 1 2 4 6)); ==> (0 0 2 4) correct answer

(define (end-ndx x ) ; x is the number of contex words
  (define (end-ndx-helper y ) ; y is the index of a matched
word, z is doc-length
    (if (<= (+ x y) z  )
        (+ x y)
        (end-ndx-helper (- y 1) )))
  end-ndx-helper)
(define last-context (end-ndx 2 ) );

(map last-context  (list 1 2 4 6) ) ;  ==> (3 4 5 5) correct
answer

OK - so I was able to use map but it feels as if I cheated
in the end-ndx procedure because I defined a third param (z
the max index value) externally.  Or was this the 'right'
way to go about this?

The next step would be to map a procedure to construct the
context string.  Now, in the examples that I've seen with
foldl (numbers) it seems that maybe this problem would not
be suitable to that procedure?

I'm lost here.

The code (below) does the job fine and seemingly with far
less effort, but doesn't use map and is essentially basic.
How might you go about solving this?  And what is it about
the problem that would lead you to think that map (or foldl
perhaps) are 'good' in this context?  Trying to get into
your thought processes.

Hope all of this was clear.

Any suggestions / ideas - most welcome.

Kindest regards,

Mike
;;;;;;;;; code ;;;;;;;;
(define (first-ndx x y )
  (if (<= 0 (- x y))
         (- x y)
      (first-ndx x (- y 1))))
(define (last-ndx x y z)
  (if (<= (+ x y) z)
     (+ x y)
     (last-ndx x (- y 1) z)))
(define (build-context first-ndx last-ndx z)
  (if (> first-ndx last-ndx) ""
      (string-append (list-ref d first-ndx)
            (if (> (+ 1 first-ndx) last-ndx)
               ; last word to add?
                (build-context
                (+ 1 first-ndx) last-ndx d)
               ; last word.  No space seperator required.
                (string-append " "
                  (build-context
                  (+ 1 first-ndx) last-ndx d))))))

Hello, Mike,

maps and folds are indeed not all there is.

I offer here a different approach on your problem, using
a map-like procedure directly: move a window of length
five over a sequence, apply a given procedure to the
elements of each such window, and collect the results in
a list. The following implementation is too simple;
write a tail-recursive helper yourself to collect the
values in reverse order, if you like.

(define (five make them)
   (if (< (length them) 5)
       '()
       (help make
             (list-ref them 0)
             (list-ref them 1)
             (list-ref them 2)
             (list-ref them 3)
             (list-ref them 4)
             (list-tail them 5))))

(define (help make h0 h1 h2 h3 h4 rest)
   (cons (make h0 h1 h2 h3 h4)
         (more make h1 h2 h3 h4 rest)))

(define (more make h1 h2 h3 h4 rest)
   (if (null? rest)
       '()
       (help make h1 h2 h3 h4 (car rest) (cdr rest))))

Use like so:

(five string (string->list "supercilious"))
==>
("super" "uperc" "perci" "ercil" "rcili" "cilio" "iliou" "lious")

For keeping only the windows of interest, one could modify
the procedure FIVE to also take a filter procedure, or one
can filter the list of results afterwards:

(define (vowely a b c d e)
   (and (memv c '(#\e #\i #\o))
        (string a b c d e)))

(five vowely (string->list "supercilious"))
==>
(#f "uperc" #f #f "rcili" #f "iliou" "lious")

(keep values (five vowely (string->list "supercilious")))
==>
("uperc" "rcili" "iliou" "lious")

The filtering procedure KEEP here is again too simple to
be good. The standard fix is again to collect in reverse
order.

(define (keep cond them)
   (if (null? them)
       '()
       (if (cond (car them))
           (cons (car them) (keep cond (cdr them)))
           (keep cond (cdr them)))))

My instinct is to just miss the windows at beginning and
end where too little context is available. Change FIVE
to take a filler parameter if you want them, maybe.

This is just a toy design. It would be easy to change
and extend it for a particular application, far less
easy to come up with a generally useful and composable
design and implementation. Too many possibilities.

Thanks Jussi,

I need to go through what you written so I can better
understand where you are coming from and then see if I can
replicate in another context.  I'd never have thought of
that approach.

Based upon the original 'problem' that I posed, I could see
map having some potential value towards crafting a solution,
but use it only if it did not add more complexity.  In other
words, using it for the sake of using it is not sensible.
My original solution was not specifically 'pretty' and
didn't use any HOP of significance - because I saw no
purpose.  Since I'm still trying to develop skills in
problem definition and solution development I was uncertain
if I had defined the problem well.  And you are quite write
there an almost endless number of alternate solutions that
present themselves.  Generally speaking I go for whatever
works simply.  If I need to add additional steps to force a
solution to fit the use of map, then that makes no sense
(but what would I know).

A completed solution is below - hopefully the var names will
make it easier to read.  I know it's not elegant but it
works.

I'll be back :)  If only to show you than I understand what
you did and why you did it.  And hopefully with an example
to show the application of your approach in another context.

Kindest regards,

Mike
(define adjacent 2)
(define index-list (list 1 3 6))
(define doc (list "a" "b" "c" "d" "e" "f" "g"))

(define (first-ndx word-ndx adjacent )
  (if(<= 0 (- word-ndx adjacent))
     (- word-ndx adjacent)
     (first-ndx word-ndx (- adjacent 1))))

(define (last-ndx word-ndx adjacent max-ndx)
  (if (<= (+ word-ndx adjacent) max-ndx)
     (+ word-ndx adjacent)
     (last-ndx word-ndx (- adjacent 1) max-ndx)))

(define (build-context first-ndx last-ndx doc)
  (if (> first-ndx last-ndx) ""
      (string-append (list-ref doc first-ndx)
                     (if (> (+ 1 first-ndx) last-ndx)
                         (build-context
                          (+ 1 first-ndx) last-ndx doc)
                         (string-append " " (build-context
                                             (+ 1 first-ndx)
last-ndx doc))))))

(define [contexts index-list adjacent doc]
  (if (empty? index-list)
      '()
      (cons (build-context
             (first-ndx (car index-list) adjacent )
             (last-ndx (car index-list)  adjacent (- (length
doc) 1)) doc)
            (contexts (cdr index-list) adjacent doc))))

(contexts index-list adjacent doc); ==> ("a b c d" "b c d e
f" "e f g")

"Jussi Piitulainen" <jpiit@ling.helsinki.fi> wrote in
message news:qot4pmky0ue.fsf@ruuvi.it.helsinki.fi...
| Hello, Mike,
|
| maps and folds are indeed not all there is.
|
| I offer here a different approach on your problem, using
| a map-like procedure directly: move a window of length
| five over a sequence, apply a given procedure to the
| elements of each such window, and collect the results in
| a list. The following implementation is too simple;
| write a tail-recursive helper yourself to collect the
| values in reverse order, if you like.
|
| (define (five make them)
|   (if (< (length them) 5)
|       '()
|       (help make
|             (list-ref them 0)
|             (list-ref them 1)
|             (list-ref them 2)
|             (list-ref them 3)
|             (list-ref them 4)
|             (list-tail them 5))))
|
| (define (help make h0 h1 h2 h3 h4 rest)
|   (cons (make h0 h1 h2 h3 h4)
|         (more make h1 h2 h3 h4 rest)))
|
| (define (more make h1 h2 h3 h4 rest)
|   (if (null? rest)
|       '()
|       (help make h1 h2 h3 h4 (car rest) (cdr rest))))
|
| Use like so:
|
| (five string (string->list "supercilious"))
| ==>
| ("super" "uperc" "perci" "ercil" "rcili" "cilio" "iliou"
"lious")
|
| For keeping only the windows of interest, one could modify
| the procedure FIVE to also take a filter procedure, or one
| can filter the list of results afterwards:
|
| (define (vowely a b c d e)
|   (and (memv c '(#\e #\i #\o))
|        (string a b c d e)))
|
| (five vowely (string->list "supercilious"))
| ==>
| (#f "uperc" #f #f "rcili" #f "iliou" "lious")
|
| (keep values (five vowely (string->list "supercilious")))
| ==>
| ("uperc" "rcili" "iliou" "lious")
|
| The filtering procedure KEEP here is again too simple to
| be good. The standard fix is again to collect in reverse
| order.
|
| (define (keep cond them)
|   (if (null? them)
|       '()
|       (if (cond (car them))
|           (cons (car them) (keep cond (cdr them)))
|           (keep cond (cdr them)))))
|
| My instinct is to just miss the windows at beginning and
| end where too little context is available. Change FIVE
| to take a filler parameter if you want them, maybe.
|
| This is just a toy design. It would be easy to change
| and extend it for a particular application, far less
| easy to come up with a generally useful and composable
| design and implementation. Too many possibilities.

Mike  writes:
> Based upon the original 'problem' that I posed, I could see map
> having some potential value towards crafting a solution, but use it
> only if it did not add more complexity.  In other words, using it
> for the sake of using it is not sensible.

Using `map', `fold', `unfold' and friends has the advantage that
these operations have well-know algebraic properties (look up
"catamorphism" and "anamorphism" in Wikipedia).  These properties
allow one to transform your program in a way that is guaranteed to
preserve correctness.

Surely this argument is not always relevant.

--
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!

On May 10, 6:32 pm, "Mike" <mcu87@bigpond.net.au> wrote:

> Thanks Jussi,

> I need to go through what you written so I can better
> understand where you are coming from and then see if I can
> replicate in another context.  I'd never have thought of
> that approach.

Hi Mike -

it seems that my previous post to you got lost via google - so I will
post again, although I lost the original text of explanation, so the
explanation is shorter this time to ddressing your original question
(as I understood it) on map/fold.

Your problem can be expressed with map/fold succinctly if you use it
in two levels,  first for finding the match within the range of 2-
before & 2-after, and second to apply the first against the list of
indexes.  If you assume the first is already done, then your second
part would look like.

;; top level function to apply multiple indexes to the list.
(define (context indexes lst filter-func)
  (map
   (lambda (idx)
     (filter-func idx lst))
   indexes))

I explicitly pass in the filter function so you can experiment with
either map or fold(l), or any other filter function you wish. The
difference between the two is that map will return same # of elements
as the original list, where as fold(l) you can build up arbitrary
results.  If you use map you would need to use filter or delete to
remove the unwanted results - following are what the filter functions
can look like with either map or fold.

;; in-range is called to determine whether the index is within the
;; range...
(define (in-range i a b)
  (and (>= i a) (<= i b)))

;; this filter function uses map to return results and filter to
remove
;; non-matches (null)
(define (use-filter+map idx lst)
  (let ((i 0))
    (filter (lambda (x) (not (null? x)))
            (map
             (lambda (x)
               (set! i (+ i 1))
               (if (in-range i (- idx 2) (+ idx 2))
                   x
                   null))
             lst))))

;; this filter function uses fold instead.
(define (use-fold idx lst)
  (let ((i 0))
    (fold
     (lambda (x result)
       (set! i (+ i 1))
       (if (in-range i (- idx 2) (+ idx 2))
           (append result (list x))
           result))
     '()
     lst)))

Lastly - these functions don't care whether it's string or symbols as
long as it's a list.  You can use string->list to get your desired
effect.

;; test.
(define lst '(a b c d e f))
(define idxs '(1 3 6))
(context idxs lst use-filter+map) ; => ((a b c) (a b c d e) (d e f))
(context idxs lst use-fold) ; => ((a b c) (a b c d e) (d e f))

Hope it helps,
yinso

Hi Yinso,

Thank you so much, I really appreciate the trouble you went
too.

This is brilliant as was the info from Jussi.

My apologies for not responding sooner.  I'm going through
both code examples (and concepts) to make certain I
understand what is going on.  I can replicate both (having
seen the code) - more parrot than understanding so I have to
muddle through (do it, do it, do it again and again ...)

I suspect I was looking at this too long which can sometimes
interfere in learning.  Don't know if this happens to you or
not.  For me, sometimes I need to sleep on an issue and let
my brain do its work quietly.  Often I find that upon waking
up I can immediately cut the code without hesitation and I
*know* what I'm doing and why I'm doing it.

Weird I guess but it works (for me at least).

So ... more to follow - if only to let you and Jussi know
your efforts were not wasted.

Mike

<yinso.c@gmail.com> wrote in message

news:1178921407.677863.102340@y80g2000hsf.googlegroups.com...
| On May 10, 6:32 pm, "Mike" <mcu87@bigpond.net.au>
wrote:
| > Thanks Jussi,
| >
| > I need to go through what you written so I can better
| > understand where you are coming from and then see if I
can
| > replicate in another context.  I'd never have thought of
| > that approach.
|
| Hi Mike -
|
| it seems that my previous post to you got lost via
google - so I will
| post again, although I lost the original text of
explanation, so the
| explanation is shorter this time to ddressing your
original question
| (as I understood it) on map/fold.
|
| Your problem can be expressed with map/fold succinctly if
you use it
| in two levels,  first for finding the match within the
range of 2-
| before & 2-after, and second to apply the first against
the list of
| indexes.  If you assume the first is already done, then
your second
| part would look like.
|
| ;; top level function to apply multiple indexes to the
list.
| (define (context indexes lst filter-func)
|  (map
|   (lambda (idx)
|     (filter-func idx lst))
|   indexes))
|
| I explicitly pass in the filter function so you can
experiment with
| either map or fold(l), or any other filter function you
wish. The
| difference between the two is that map will return same #
of elements
| as the original list, where as fold(l) you can build up
arbitrary
| results.  If you use map you would need to use filter or
delete to
| remove the unwanted results - following are what the
filter functions
| can look like with either map or fold.
|
| ;; in-range is called to determine whether the index is
within the
| ;; range...
| (define (in-range i a b)
|  (and (>= i a) (<= i b)))
|
| ;; this filter function uses map to return results and
filter to
| remove
| ;; non-matches (null)
| (define (use-filter+map idx lst)
|  (let ((i 0))
|    (filter (lambda (x) (not (null? x)))
|            (map
|             (lambda (x)
|               (set! i (+ i 1))
|               (if (in-range i (- idx 2) (+ idx 2))
|                   x
|                   null))
|             lst))))
|
| ;; this filter function uses fold instead.
| (define (use-fold idx lst)
|  (let ((i 0))
|    (fold
|     (lambda (x result)
|       (set! i (+ i 1))
|       (if (in-range i (- idx 2) (+ idx 2))
|           (append result (list x))
|           result))
|     '()
|     lst)))
|
| Lastly - these functions don't care whether it's string or
symbols as
| long as it's a list.  You can use string->list to get your
desired
| effect.
|
| ;; test.
| (define lst '(a b c d e f))
| (define idxs '(1 3 6))
| (context idxs lst use-filter+map) ; => ((a b c) (a b c d
e) (d e f))
| (context idxs lst use-fold) ; => ((a b c) (a b c d e) (d e
f))
|
| Hope it helps,
| yinso
|
On May 13, 5:25 pm, "Mike" <mcu87@bigpond.net.au> wrote:

> I suspect I was looking at this too long which can sometimes
> interfere in learning.  Don't know if this happens to you or
> not.  For me, sometimes I need to sleep on an issue and let
> my brain do its work quietly.  Often I find that upon waking
> up I can immediately cut the code without hesitation and I
> *know* what I'm doing and why I'm doing it.

Hi Mike -

IMHO if you think of map/fold as looping constructs that returns a
list then it's easier to see how they can be used - just substitute
where you used to use for loops and you should be good to go ;)

To see past their magic you can consider how they are implemented -
below are a simple definition of map and fold for 1 list (you can
extend them to handle multiple lists):

(define (map-1 func lst)
  (cond
    ((null? lst) '())
    (else (cons (func (car lst))
                (map-1 func (cdr lst))))))

(define (fold-1 func result lst)
  (cond
    ((null? lst) result)
    (else (fold-1 func
                  (func (car lst) result)
                  (cdr lst)))))

Hope this helps,
yinso

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