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

Stuck ... code mess.


Hi all,

My apologies for so many posts.

I've been playing with a small task to search for the existence of each item
in a list.  The procedure should return a list of lists containing the
search item and the index in which it exists in the reference list.  The
over-all intention is to cycle through a list of items in search-list and
return a list of lists containing the item / index - allowing duplicates.

Eventually the finished output should look like this using the search-list
and document variables below.
(("G" 1) ("G" 2) ("G" 5) ("G" 7) ("G" 9)
("M" 0) ("M" 3))

In the proof of concept code (below) the desired output should look like
this:
(("G" 1) ("G" 2) ("G" 5) ("G" 7) ("G" 9)) - and it does until I tinker :(

I haven't tidied it up yet - just want to get it to work properly first.  It
works perfectly well so long as I supply the item to the procedure (car
search-list).  But as soon as I substitute the argument "item" (a string in
this example) with a list (of strings) - call it a-list, and use (car
a-list) in the code body in each instance of the variable "item", it coughs
up and dies ...

I get an error message:

(define search-list (list "G" "M" ))
(define document (list "M" "G" "G" "M" "p" "G" "i" "G" "u" "G"))

(define (count-matches item document  doc-length)
  (cond
    [(or (null? item) (empty? document)) '()]
    [else
     (if (null? item)
         '()
         (if (member item document)
             (cons (list item (- doc-length (length (member item
document))))
                     (count-matches item (cdr (member item document))
doc-length))
             '()
             ))]))
(count-matches (car search-list) document (length document))
; ==> (("G" 1) ("G" 2) ("G" 5) ("G" 7) ("G" 9))

So, substitute "item" on the pram line with search-list and then with "(car
search-list)" in the code body, it produces this error: ** car: expects
argument of type <pair>; given "M"

Here is the modified code - using the same definitions for search-list and
document:

(define (count-matches search-list document  doc-length)
  (cond
    [(or (null? (car search-list)) (empty? document)) '()]
    [else
     (if (null? (car search-list))
         '()
         (if (member (car search-list) document)
             (cons (list (car search-list) (- doc-length (length (member
(car search-list) document))))
                     (count-matches (car search-list) (cdr (member (car
search-list) document))  doc-length))
             '()
             ))]))

(count-matches (car (cdr search-list)) document (length document))

I know it looks like a dog's breakfast and it will be tidied.  But I have no
clue as to why this should fall over - I'm not altering (car search-list)
anywhere and it works perfectly well as long as I just pass the value (car
a-list) in the call to the procedure, as shown in the first example of the
code.

I was hoping to use something along the lines of map but, so far as I can
tell, map requires lists of equal length and that may not be true in this
example.  It occurred to me that it might be useful to "pad" out the
search-list / or document list with null strings to make them equal in size
but that seems a tad over the top.  The important info to collect is the
item / index combination for each item in the search-list that appears in
the document.

I've played with this too long and suspect I'm missing the bleeding obvious.
Any suggestions - derisive laughs?

Kindest regards,

Mike

Hmmmm,

Must be tired to have missed the bleeding obvious.

The 'good code' is below.  Ignore the typo that called the 'bad' code ...

The problem was fundamental: each pass in the recursive process meant that
at some point, a string, and not a list was going to be passed - hence it
fell over.  It just needed a nested procedure to handle this recursive
consequence.  Nothing wrong with Scheme - just me being tired is all.

While this is a solution that will be able to both count the number of times
any item in list-1 is present in list-2 and show the indices (separate
issues), it seems like a clunky solution.  I'm **not** supposed to use let
or set! etc as yet ... a pain.

I could tidy it up a little but probably not all that much.  I still look at
the code and think it is clunky - must be a more elegant approach.

To be honest, if someone wanted this sort of info I'd do an SQL on its ass -
snap!  Done .. a couple of lines of code.  I'm finding it difficult to
squeeze my thoughts passed the database style solution on things like this
...

I figure it must be good (having the constraints and using Scheme) because
it does force me to think more deliberately about both problem definition
and solution construction.

(a) Without using let or set, how else might you solve a problem like this?
My concern is that I may not be defining the problem particularly well and /
or not designing efficient solutions (within the constraints I have to work
with).

Kindest regards,

Mike
_________
Solution:
(define search-list (list "G" "M" ))
(define document (list "M" "G" "G" "M" "p" "G" "i" "G" "u" "G"))

(define (search search-list doc doc-len)
  (define (search-helper item document doc-length)
    (cond
      [(empty? document) '()]
      [else
       (if (member item document)
           (cons (list item (- doc-length (length (member item document))))
                 (search-helper item (cdr (member item document))
doc-length))
           '())]))
  (if (empty? search-list)
      '()
      (append (search-helper (car search-list) doc doc-len)
            (search (cdr search-list) doc doc-len))))

(search search-list document (length document))
;==>(("G" 1) ("G" 2) ("G" 5) ("G" 7) ("G" 9) ("M" 0) ("M" 3))

; This is slightly different - seems cleaner but goes through a load more
iterations.  The first goes through about 7 iterations while the one below
must do about 20.  Cleaner doesn't necessarily mean faster - although I have
no idea about the relative overhead associated with using member as opposed
to straight object comparison operations.

(define (count-matches check-list document)
  (define (count-matches-helper counter item document)
    (cond
      [(empty? document) '()]
      [else
       (if (equal? item (car document))
           (cons (list item counter)
                 (count-matches-helper (+ 1 counter) item (cdr document)))
           (count-matches-helper (+ 1 counter) item (cdr document)))]))
  (cond
    [(empty? check-list)'()]
    [else
     (append (count-matches-helper 0 (car check-list) document)
           (count-matches  (cdr check-list) document))]))
(count-matches search-list document)

"Mike" <mcu87@bigpond.net.au> wrote in message

news:XjD_h.33601$M.27844@news-server.bigpond.net.au...

Mike wrote:
> (define search-list (list "G" "M" ))
> (define document (list "M" "G" "G" "M" "p" "G" "i" "G" "u" "G"))

> (define (search search-list doc doc-len)
>   (define (search-helper item document doc-length)
>     (cond
>       [(empty? document) '()]
>       [else
>        (if (member item document)
>            (cons (list item (- doc-length (length (member item document))))
>                  (search-helper item (cdr (member item document))
> doc-length))
>            '())]))

Why test for am empty document?

If document is empty, then (member item document) will return #f.

--
Jens Axel Sgaard

"Jens Axel Sgaard" <use@soegaard.net> wrote in message
news:463b358d$0$23930$edfadb0f@dread12.news.tele.dk...

[......]
Oh yeah ... doh

It's the Little Schemer showing through.  The book repeatedly drums in the
mantra that before using any list test to see if it is empty.  It's become a
habit (not a particularly bad one) but obviously unnecessary in this
instance.

Thanks for pointing it out.

Mike

There is something you should be aware.  Why the _variables_ of lisp
are not typed (you can bind them to values of any type, in lisp, it's
the _values_ that are typed), it is still a good idea to always know
what type of data you will get in a procedure and what type it will
return.

Here you write a function that takes a string (an "item"), and a list
of strings (a "document"), and returns a list of list of two elements,
a string and a number.

(Instead of passing the length of the document, and computing over and
over the length of the rest of the document, you could rather pass the
index of the first element of the document; see below).

But since there is no type declarations (usually; this is something
that could be added, but it's not in the standard scheme (it's in
standard Common Lisp)),  the type of the parameters and results are to
be infered, from what is expected or produced by the operators applied
to them (or computing them).

What type must search-list be, if you want to avoid the signaling of a
run-time error?

In this function, you call (car search-list), therefore search-list
must be a cons cell (a pair).

When (null? (car search-list)) you don't do anything else on
search-list.  So this function accepts a search list like: (() . x).

When (not (null?  (car search-list))) you call (member
... search-list).  For member, search-list must be a proper-list.  So
when the first elemement of the search list is not (), search list
must be a properlist.

The expected type is therefore: (or (cons () anything) proper-list).

In your example,  you call it with (car search-list),  which is "G", a
string, which is not a subtype of (or (cons () anything) proper-list).

> [...]
> I've played with this too long and suspect I'm missing the bleeding obvious.
> Any suggestions - derisive laughs?

Once you have a function to process one item, you can easily write a
function to process n items:

(define (process-one-item item ...) ...)

(define (process-several-items items ...)
   (mapcar (lambda (item) (process-one-item item ...) items)))

Sometimes, you want to "flatten" one level, that is, to accumulates
the values returned in lists by process-one-item into a single list:

(define (process-several-items items ...)
   (apply append (mapcar (lambda (item) (process-one-item item ...) items))))

But it seems to me that instead of processing each item first, and
then finding the positions in the document, you could rather process
the document and see if the current item is one you must process:

(define (collect-next-position items document position)
  (cond ((null? document) '())
        ((member (car document) items)
         (cons (list (car document) position)
               (collect-next-position items (cdr document) (+ 1 position))))
        (else
           (collect-next-position items (cdr document) (+ 1 position)))))

(define (collect-positions items document)
   (collect-next-position items document 0))

Or, using an accumulator to make a tail call:

(define (collect-next-position items document position result)
  (cond ((null? document)  result)
        ((member (car document) items)
         (collect-next-position items (cdr document) (+ 1 position)
              (cons (list (car document) position) result)))
        (else
           (collect-next-position items (cdr document) (+ 1 position) result))))

(define (collect-positions items document)
   (collect-next-position items document 0 '()))

;; (No code in this post has been tested)

--
__Pascal Bourguignon__                     http://www.informatimago.com/
Grace personified,
I leap into the window.
I meant to do that.

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