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: lists and indexing


Hi all,

I need to identify the position of a value in a list.

I know (list-ref  (list "a" "b" "c" "d") 2) ;==> "c" (0 is base index value)
but that is useful so long as I know the value of element 2 in the list.

It's not a chore to loop through a list (using a counter) and when a match
is found, return the counter or #f.  But is there any way to locate a value
in a list other than checking each item in turn?

Kindest regards,

Mike

Mike skrev:

> Hi all,

> I need to identify the position of a value in a list.

> I know (list-ref  (list "a" "b" "c" "d") 2) ;==> "c" (0 is base index value)
> but that is useful so long as I know the value of element 2 in the list.

> It's not a chore to loop through a list (using a counter) and when a match
> is found, return the counter or #f.  But is there any way to locate a value
> in a list other than checking each item in turn?

<http://srfi.schemers.org/srfi-1/srfi-1.html#find>
<http://srfi.schemers.org/srfi-1/srfi-1.html#list-index>

 > (require (lib "list.ss" "srfi" "1"))
 > (find even? (list 1 3 4 5))
4

 > (list-index even? (list 1 3 4 5))
2

 > (member 4 (list 1 2 4 5))
(4 5)

--
Jens Axel Sgaard

Thanks Jens!

This ones a keeper for sure - I've never come across this document, or
rather, I may have seen a reference to it on occasion but had no idea it was
gold in a bucket.  Happy happy - joy joy (small jig being danced).

This is so cool!

Is there any similar document that shows the code behind these procedures?
I've provided code for foldl and foldr below to give you and idea of what I
mean.

Also, you used  (require (lib "list.ss" "srfi" "1")).  I gather it adds
functionality to DrScheme (Schemes?) but I've not had reason to use it
before now.

"list.ss" is the file?? (library of functions?) but I was unable to find it
in my PC - does it live within one of the DLL files?  Just curious ... you
see, if Scheme does use DLL files then it may be possible to access other
DLL's too.

Kindest regards,

Mike
----------
; FOLDR is defined recursively
(define [foldr op init seq]
  (if (empty? seq)
      init
      (op (first seq)
          (foldr op init (rest seq)))))
(foldr - 2 (list 1 2 3))
(- 1 (- 2 ( - 3 2)))

; and FOLDL is defined iteratively
(define [foldl op init items]
  (define [foldl-iter result todo]
    (if (empty? todo)
      result
      (foldl-iter (op (first todo) result)
                  (rest todo))))
  (foldl-iter init items))
(foldl - 1 (list 1 2 3))

So much to play with and so little time.

Thank you heaps,

Mike

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

Mike skrev:

> This ones a keeper for sure - I've never come across this document, or
> rather, I may have seen a reference to it on occasion but had no idea it was
> gold in a bucket.  Happy happy - joy joy (small jig being danced).

> This is so cool!

> Is there any similar document that shows the code behind these procedures?

<http://ja.soegaard.net/planet/html/collects/srfi/1/>

> I've provided code for foldl and foldr below to give you and idea of what I
> mean.

> Also, you used  (require (lib "list.ss" "srfi" "1")).  I gather it adds
> functionality to DrScheme (Schemes?) but I've not had reason to use it
> before now.

Yes, in DrScheme that loads srfi-1.

> "list.ss" is the file?? (library of functions?) but I was unable to find it
> in my PC - does it live within one of the DLL files?  Just curious ... you
> see, if Scheme does use DLL files then it may be possible to access other
> DLL's too.

On my computer it lives in

   c:\Programs\PLT Scheme\collects\srfi\1\

It is included in the normal distribution of DrScheme.

--
Jens Axel Sgaard

Mike  writes:
> This ones a keeper for sure - I've never come across this document, or
> rather, I may have seen a reference to it on occasion but had no idea it was
> gold in a bucket.  Happy happy - joy joy (small jig being danced).

:)

See also the SRFI 13.  It's another treasure, but for manipulating
strings.

> Is there any similar document that shows the code behind these
> procedures?

The reference implementation is linked from the SRFI document:

    http://srfi.schemers.org/srfi-1/srfi-1-reference.scm

Some of them are developed along the book "Structure and
Interpretation of Computer Programs", called SICP:

    http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-4.html

--
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 Jens,

Just curious.  How do you feel about the "find" compared to "member" or
"list-index"?  With find, you get the first instance of a but not the index.
Member returns the item and cdr of the reference list which allows you to
calculate the index.  list-index ... well, I'm still trying to work that one
out so I'm uncertain about how to use it properly.

I'm familiar with binary trees - haven't needed to use them (RDBMS) - but I
figure I can create them using Scheme easily enough.  Wouldn't it be faster
using something like a binary tree, for example, to work out where items are
and their position?  Inserting new elements would be interesting but
solvable.

Just curious.

Kindest regards,

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

Mike skrev:

> Hi Jens,

> Just curious.  How do you feel about the "find" compared to "member" or
> "list-index"?  With find, you get the first instance of a but not the index.
> Member returns the item and cdr of the reference list which allows you to
> calculate the index.  list-index ... well, I'm still trying to work that one
> out so I'm uncertain about how to use it properly.

Depends. These days I have a tendency to use srfi-42. Here
is an example of find the first even number and its index.

 > (require (lib "42.ss" "srfi"))

 > (define xs '(1 3 5 6 8 3 ))

 > (first-ec 'not-found
            (: x (index i) xs)
            (if (even? x))
            (list i x))
(3 6)

The standard approach is to use a named loop:

(let loop ([xs xs]
            [i  0])
    (cond
      [(null? xs)        'not-found]
      [(even? (car xs))  (list i (car xs))]
      [else              (loop (cdr xs) (+ i 1))]))

Which you eventually will be able to write, without
to think twice, if you stick with Scheme.

--
Jens Axel Sgaard

Jens Axel Sgaard skrev:

And here is the Haskell-in-Scheme solution:

(require (lib "list.ss" "srfi" "1"))

(define xs '(1 3 5 6 7 9))

(find (compose even? car)
       (zip xs
            (iota (length xs) 0)))

Here are the intermediate results:

 > (iota (length xs) 0)
(0 1 2 3 4 5)

 > (zip xs
        (iota (length xs) 0))
((1 0) (3 1) (5 2) (6 3) (7 4) (9 5))

 > (find (compose even? car)
         (zip xs
              (iota (length xs) 0)))
(6 3)

--
Jens Axel Sgaard

And here is the Haskell-in-Scheme solution:

  With Scheme on top:

    (define (find-match p? lst)
      (call-with-current-continuation
        (lambda (k)
          (fold
            (lambda (elt cnt) (if (p? elt) (k (list elt cnt)) (1+ cnt)))
            0 lst)
          #f)))

    guile> (find-match even? '(1 3 5 7 10))
    (10 4)
    guile> (find-match even? '(1 3 5 7))
    #f
    guile> (find-match even? '())
    #f
    guile>

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