[racket-users] Recursive stepping down a list patially?

[Meino . Cramer]

Hi,

I have a lng list of something. And I have a recursive serach
function to crawl down the list and search for a previously determined
item.
When found, the search processes stops and returns that item of the
list.

In a second step, I want to process the list starting with that
certain item til the end of the list.

Is it possible to jump right into a list at a certain item of
the list and to start processing there? Could the search function
return a certain extra information so that another function could
pick up that item directly and start recursing from there?
"""Distributed recursion""" somehow...?

(I know, that vectors can do that and that there is 
a function to convert a list to a vector and vice versa and
the real programmer would call the processing function from
the search function when the certain item is found --
but all this would make this email/question superflous... 
;)))

Cheers
Meino




-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Recursive stepping down a list patially?

[Jon Zeppieri]

On Mon, Oct 31, 2016 at 10:53 PM,  wrote:

> Hi,
>
> I have a lng list of something. And I have a recursive serach
> function to crawl down the list and search for a previously determined
> item.
> When found, the search processes stops and returns that item of the
> list.
>
> In a second step, I want to process the list starting with that
> certain item til the end of the list.
>
> Is it possible to jump right into a list at a certain item of
> the list and to start processing there? Could the search function
> return a certain extra information so that another function could
> pick up that item directly and start recursing from there?
> """Distributed recursion""" somehow...?
>
>
The tail of a non-empty list is simply a list, so, if I understand you
correctly, what you want to do is very straightforward. The `member` (and
`memq` / `memv` / `memf` ) functions are meant for exactly this sort of
thing. In your first step, instead of returning just the member of the list
you're interested in, you can return the sublist that starts with that
item. For example, let's say you have a list of strings that looks like
this:

(define xs '("one" "two" "three" "four" "five"))

And you want to find "three." Then you can do:

(member "three" xs)

... which returns:

'("three" "four" "five")

The first element of the result is the element you wanted, and the
remainder of the list is everything after it.

You'll want `memf` if you need to search by some arbitrary function. See
the documentation for this group of functions.

- Jon

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Recursive stepping down a list patially?

[Meino . Cramer]

Hi Jon,

thanks for reply! :)

My plan was, to return only one element from that list and
possibly some extra informations and pass that to the processing
function so it could right jump onto that train...

Is that possible?

Cheers
Meino



Jon Zeppieri  [16-11-01 04:20]:
> On Mon, Oct 31, 2016 at 10:53 PM,  wrote:
> 
> > Hi,
> >
> > I have a lng list of something. And I have a recursive serach
> > function to crawl down the list and search for a previously determined
> > item.
> > When found, the search processes stops and returns that item of the
> > list.
> >
> > In a second step, I want to process the list starting with that
> > certain item til the end of the list.
> >
> > Is it possible to jump right into a list at a certain item of
> > the list and to start processing there? Could the search function
> > return a certain extra information so that another function could
> > pick up that item directly and start recursing from there?
> > """Distributed recursion""" somehow...?
> >
> >
> The tail of a non-empty list is simply a list, so, if I understand you
> correctly, what you want to do is very straightforward. The `member` (and
> `memq` / `memv` / `memf` ) functions are meant for exactly this sort of
> thing. In your first step, instead of returning just the member of the list
> you're interested in, you can return the sublist that starts with that
> item. For example, let's say you have a list of strings that looks like
> this:
> 
> (define xs '("one" "two" "three" "four" "five"))
> 
> And you want to find "three." Then you can do:
> 
> (member "three" xs)
> 
> ... which returns:
> 
> '("three" "four" "five")
> 
> The first element of the result is the element you wanted, and the
> remainder of the list is everything after it.
> 
> You'll want `memf` if you need to search by some arbitrary function. See
> the documentation for this group of functions.
> 
> - Jon
> 
> -- 
> You received this message because you are subscribed to the Google Groups 
> "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an 
> email to racket-users+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Recursive stepping down a list patially?

[Jon Zeppieri]

On Mon, Oct 31, 2016 at 11:28 PM,  wrote:

>
> Hi Jon,
>
> thanks for reply! :)
>
> My plan was, to return only one element from that list and
> possibly some extra informations and pass that to the processing
> function so it could right jump onto that train...
>
> Is that possible?
>
>
I think I understand your concern, and I think it's misplaced. Here's what
I think you're suggesting: you don't want to return the entire remainder of
the list, because (as you said) it's a really long list, and you're
concerned about passing around (and possibly duplicating) a ton of data.
But that's not the way it works. In terms of in-memory representation, all
that the `member` functions return is a pointer to a position (a particular
pair) in the original list.

You seem to be thinking of something like this: if you were using a vector,
you could return the element and the index where you found that element.
Then you could continue on from the next index. And you wouldn't want to do
this with a list, because if you start at the head of the original list,
you'd first have to follow it down to the nth element before continuing on,
and that would be inefficient. But what I'm saying is that if you simply
return the tail of the list using a `member` function, you don't incur that
extra iteration cost, and you don't duplicate any of the original list.

- Jon

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Recursive stepping down a list patially?

[David Storrs]

Hi Meino,

Good news!  There are built-ins that will do almost all of this for you:

On Mon, Oct 31, 2016 at 10:53 PM,   wrote:
> Hi,
>
> I have a lng list of something. And I have a recursive serach
> function to crawl down the list and search for a previously determined
> item.
> When found, the search processes stops and returns that item of the
> list.

Check the following pages:
https://docs.racket-lang.org/reference/pairs.html  (cf 'member' and 'memf')
https://docs.racket-lang.org/guide/for.html   (short intro on 'for')
https://docs.racket-lang.org/reference/for.html#%28form._%28%28lib._racket%2Fprivate%2Fbase..rkt%29._for%29%29
(full documentation of all versions of 'for')

>
> In a second step, I want to process the list starting with that
> certain item til the end of the list.
>
> Is it possible to jump right into a list at a certain item of
> the list and to start processing there?

Yes.  What you want is list-ref


(define my-list '(a b c d e f g))

(list-ref

 (list

 'a 'b 'c) 0)

'a


>  Could the search function
> return a certain extra information so that another function could
> pick up that item directly and start recursing from there?
> """Distributed recursion""" somehow...?

Yes.  There's various ways, but the simplest would be:

(define my-list '(a b c d e f g))
(define search (lambda (x) (equal? x 'd)))
(define further-processing (lambda (lst) ( ... do something here ...)))

(memf search my-list)  ;;   =>  returns '(d e f g)


;;   Find the interesting element, save the list from that point on for
future use
(define interesting-part-of-list
(memf search my-list))

;;   Or, alternatively, find the interesting element, then send it and the
rest of the list directly to 'further-processing'
(further-processing
(memf search my-list))


Side note:  The following two ways of defining a function are equivalent:

(define foo (lambda (x) 7))
(define (foo x) 7)


Hope this helps.

Dave

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Recursive stepping down a list patially?

['John Clements' via Racket Users]

> On Nov 1, 2016, at 8:02 AM, David Storrs  wrote:
> 
...
> > Is it possible to jump right into a list at a certain item of
> > the list and to start processing there?
> 
> Yes.  What you want is list-ref 
> 
> (define my-list '(a b c d e f g))
> 
> (list-ref (list 'a 'b 'c) 0)
> 'a


Oog, no, don’t do that. The earlier solution, by returning the list (or, if you 
prefer, “a pointer to the list”), ensure that the entire (resumed) search takes 
time linear in the length of the list. But indexing into the list with 
‘list-ref’ will require re-traversing the first part of the list, probably 
turning an O(n) operation into an O(n^2) operation.

Right?

John



-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Recursive stepping down a list patially?

[Meino . Cramer]

'John Clements' via Racket Users  [16-11-01 
18:47]:
> 
> > On Nov 1, 2016, at 8:02 AM, David Storrs  wrote:
> > 
> ...
> > > Is it possible to jump right into a list at a certain item of
> > > the list and to start processing there?
> > 
> > Yes.  What you want is list-ref 
> > 
> > (define my-list '(a b c d e f g))
> > 
> > (list-ref (list 'a 'b 'c) 0)
> > 'a
> 
> 
> Oog, no, don’t do that. The earlier solution, by returning the list (or, if 
> you prefer, “a pointer to the list”), ensure that the entire (resumed) search 
> takes time linear in the length of the list. But indexing into the list with 
> ‘list-ref’ will require re-traversing the first part of the list, probably 
> turning an O(n) operation into an O(n^2) operation.
> 
> Right?
> 
> John
> 
> 
> 
> -- 
> You received this message because you are subscribed to the Google Groups 
> "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an 
> email to racket-users+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
> 

Hi John,

thanks for your reply! :)

My first assumption was, that returning the tail of a list would
return a FULL COPY (*>S<*) of that tail made me feels not very
comfortable about that kind of solution.

But...
:)

If under the hood racket transfers references...NO PROBLEM!
I like that! 8)

Cheers
Meino

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Recursive stepping down a list patially?

[Meino . Cramer]

Hi David,

thanks for your...:) DOCUMENTATION PROJECT :).!!!
Whow!
Now I have a lot to read! 

Cheers
Meino


David Storrs  [16-11-01 18:47]:
> Hi Meino,
> 
> Good news!  There are built-ins that will do almost all of this for you:
> 
> On Mon, Oct 31, 2016 at 10:53 PM,   wrote:
> > Hi,
> >
> > I have a lng list of something. And I have a recursive serach
> > function to crawl down the list and search for a previously determined
> > item.
> > When found, the search processes stops and returns that item of the
> > list.
> 
> Check the following pages:
> https://docs.racket-lang.org/reference/pairs.html  (cf 'member' and 'memf')
> https://docs.racket-lang.org/guide/for.html   (short intro on 'for')
> https://docs.racket-lang.org/reference/for.html#%28form._%28%28lib._racket%2Fprivate%2Fbase..rkt%29._for%29%29
> (full documentation of all versions of 'for')
> 
> >
> > In a second step, I want to process the list starting with that
> > certain item til the end of the list.
> >
> > Is it possible to jump right into a list at a certain item of
> > the list and to start processing there?
> 
> Yes.  What you want is list-ref
> 
> 
> (define my-list '(a b c d e f g))
> 
> (list-ref
> 
>  (list
> 
>  'a 'b 'c) 0)
> 
> 'a
> 
> 
> >  Could the search function
> > return a certain extra information so that another function could
> > pick up that item directly and start recursing from there?
> > """Distributed recursion""" somehow...?
> 
> Yes.  There's various ways, but the simplest would be:
> 
> (define my-list '(a b c d e f g))
> (define search (lambda (x) (equal? x 'd)))
> (define further-processing (lambda (lst) ( ... do something here ...)))
> 
> (memf search my-list)  ;;   =>  returns '(d e f g)
> 
> 
> ;;   Find the interesting element, save the list from that point on for
> future use
> (define interesting-part-of-list
> (memf search my-list))
> 
> ;;   Or, alternatively, find the interesting element, then send it and the
> rest of the list directly to 'further-processing'
> (further-processing
> (memf search my-list))
> 
> 
> Side note:  The following two ways of defining a function are equivalent:
> 
> (define foo (lambda (x) 7))
> (define (foo x) 7)
> 
> 
> Hope this helps.
> 
> Dave
> 
> -- 
> You received this message because you are subscribed to the Google Groups 
> "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an 
> email to racket-users+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Recursive stepping down a list patially?

[Meino . Cramer]

Hi Jon,

thank you for your mind reading! :::)))

Exactly! 
Now I know, that racket passes references under the hood
and the world is getting a better place again.

Cheers
Meino



Jon Zeppieri  [16-11-01 04:40]:
> On Mon, Oct 31, 2016 at 11:28 PM,  wrote:
> 
> >
> > Hi Jon,
> >
> > thanks for reply! :)
> >
> > My plan was, to return only one element from that list and
> > possibly some extra informations and pass that to the processing
> > function so it could right jump onto that train...
> >
> > Is that possible?
> >
> >
> I think I understand your concern, and I think it's misplaced. Here's what
> I think you're suggesting: you don't want to return the entire remainder of
> the list, because (as you said) it's a really long list, and you're
> concerned about passing around (and possibly duplicating) a ton of data.
> But that's not the way it works. In terms of in-memory representation, all
> that the `member` functions return is a pointer to a position (a particular
> pair) in the original list.
> 
> You seem to be thinking of something like this: if you were using a vector,
> you could return the element and the index where you found that element.
> Then you could continue on from the next index. And you wouldn't want to do
> this with a list, because if you start at the head of the original list,
> you'd first have to follow it down to the nth element before continuing on,
> and that would be inefficient. But what I'm saying is that if you simply
> return the tail of the list using a `member` function, you don't incur that
> extra iteration cost, and you don't duplicate any of the original list.
> 
> - Jon

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Recursive stepping down a list patially?

[David Storrs]

On Tue, Nov 1, 2016 at 1:34 PM, John Clements 
wrote:

>
> > On Nov 1, 2016, at 8:02 AM, David Storrs  wrote:
> >
> ...
> > > Is it possible to jump right into a list at a certain item of
> > > the list and to start processing there?
> >
> > Yes.  What you want is list-ref
> >
> > (define my-list '(a b c d e f g))
> >
> > (list-ref (list 'a 'b 'c) 0)
> > 'a
>
>
> Oog, no, don’t do that. The earlier solution, by returning the list (or,
> if you prefer, “a pointer to the list”), ensure that the entire (resumed)
> search takes time linear in the length of the list. But indexing into the
> list with ‘list-ref’ will require re-traversing the first part of the list,
> probably turning an O(n) operation into an O(n^2) operation.


> Right?
>

Yep.  I should perhaps have been more clear that what I was saying was "to
answer your immediate question: yes, list-ref is a thing, but in general
the solutions I am about to propose are better."



>
> John
>
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.