From: Scott
Subject: processing a sequence
Date: 
Message-ID: <7c976803-1008-4ad2-8a49-07d697ce6fe0@33g2000yqm.googlegroups.com>
Hi All,

I am trying to process a sequence like:

(0 1 2 3 0 1 2 3 0 1 2 3)

and produce:

((0 1 2 3)(0 1 2 3)(0 1 2 3))

i.e. create sub-sequences beginning whenever the value decreases.

However, I am not having much luck (being pretty new to LISP). My
attempt was to use a loop with two collect statements, collecting each
number into one until its value decreases compared to the last one,
which then gets collected into another, then reset. Something like
this:

(loop
  for num in seq
  when (and (not (null subseq)) (<= num (car (last subseq)))
    collect subseq into answer and
    do (setf subseq nil)
  collect num into subseq
  finally (return answer))

But, subseq never seems to get reset, and it seems that there are
references at work as the return value contains multiple copies of the
original sequence.

Would someone kindly be able to offer some advice or a nudge in the
right direction?

Best,
Scott

From: ······@corporate-world.lisp.de
Subject: Re: processing a sequence
Date: 
Message-ID: <90fd3b10-a7c4-4d11-a405-1b96e1c1aef0@n41g2000yqh.googlegroups.com>
On Dec 8, 1:08 am, Scott <·······@gmail.com> wrote:
> Hi All,
>
> I am trying to process a sequence like:
>
> (0 1 2 3 0 1 2 3 0 1 2 3)
>
> and produce:
>
> ((0 1 2 3)(0 1 2 3)(0 1 2 3))
>
> i.e. create sub-sequences beginning whenever the value decreases.
>
> However, I am not having much luck (being pretty new to LISP). My
> attempt was to use a loop with two collect statements, collecting each
> number into one until its value decreases compared to the last one,
> which then gets collected into another, then reset. Something like
> this:
>
> (loop
>   for num in seq
>   when (and (not (null subseq)) (<= num (car (last subseq)))
>     collect subseq into answer and
>     do (setf subseq nil)
>   collect num into subseq
>   finally (return answer))
>
> But, subseq never seems to get reset, and it seems that there are
> references at work as the return value contains multiple copies of the
> original sequence.
>
> Would someone kindly be able to offer some advice or a nudge in the
> right direction?
>
> Best,
> Scott

(defun collect-sublists (list)
  (flet ((collect-sublist ()
           (loop for element = (pop list)
                 while element collect element
                 while (and list
                            (<= element (first list))))))
    (loop for sublist = (collect-sublist)
          while sublist collect sublist)))
From: Scott
Subject: Re: processing a sequence
Date: 
Message-ID: <db0bdd2c-48d4-44ab-b74e-813abc48ff1b@f3g2000yqf.googlegroups.com>
On Dec 7, 7:49 pm, ·······@corporate-world.lisp.de" <······@corporate-
world.lisp.de> wrote:
> (defun collect-sublists (list)
>   (flet ((collect-sublist ()
>            (loop for element = (pop list)
>                  while element collect element
>                  while (and list
>                             (<= element (first list))))))
>     (loop for sublist = (collect-sublist)
>           while sublist collect sublist)))

Thanks for the quick response! This does exactly what I need, although
I will certainly have to look at it closely to see exactly how.

Best,
Scott
From: ··················@gmail.com
Subject: Re: processing a sequence
Date: 
Message-ID: <4521e445-0148-47b4-b2cd-07233e931968@j38g2000yqa.googlegroups.com>
On Dec 7, 9:47 pm, Scott <·······@gmail.com> wrote:
> On Dec 7, 7:49 pm, ·······@corporate-world.lisp.de" <······@corporate-
>
> world.lisp.de> wrote:
> > (defun collect-sublists (list)
> >   (flet ((collect-sublist ()
> >            (loop for element = (pop list)
> >                  while element collect element
> >                  while (and list
> >                             (<= element (first list))))))
> >     (loop for sublist = (collect-sublist)
> >           while sublist collect sublist)))
>
> Thanks for the quick response! This does exactly what I need, although
> I will certainly have to look at it closely to see exactly how.
>
> Best,
> Scott

Here is a great function from "On Lisp"

(defun group (source n)
  (if (zerop n) (error "zero length"))
  (labels ((rec (source acc)
		(let ((rest (nthcdr n source)))
		  (if (consp rest)
		      (rec rest (cons (subseq source 0 n) acc))
		    (nreverse (cons source acc))))))
    (if source (rec source nil) nil)))

http://www.bookshelf.jp//texi/onlisp/onlisp_5.html
------------

I did it by copy paste, that's 0 lines of code :)
Is one of those functions I keep in my utilities.
From: Alex Mizrahi
Subject: Re: processing a sequence
Date: 
Message-ID: <493d5a3f$0$90273$14726298@news.sunsite.dk>
 acl> Here is a great function from "On Lisp"

i dunno if this one is faster (it might be because it uses
CL library functions, but theoretically it won't matter for "sufficiently
smart compiler"), but Rainer's one is at least order of magnitude easier
to read/understand, and algorithmically it is same O(N).

 acl> (defun group (source n)
 acl>   (if (zerop n) (error "zero length"))
 acl>   (labels ((rec (source acc)
 acl>   (let ((rest (nthcdr n source)))
 acl>     (if (consp rest)
 acl>         (rec rest (cons (subseq source 0 n) acc))
 acl>       (nreverse (cons source acc))))))
 acl>     (if source (rec source nil) nil)))
From: ··················@gmail.com
Subject: Re: processing a sequence
Date: 
Message-ID: <1b2f2889-0e7e-49c6-a2ab-1e59c2e34b6b@v13g2000yqm.googlegroups.com>
On Dec 8, 12:32 pm, "Alex Mizrahi" <········@users.sourceforge.net>
wrote:
> Rainer's one is at least order of magnitude easier
> to read/understand, and algorithmically it is same O(N).

That is true, although I was kind of hoping he might open the link and
keep reading after not understanding the function (Rainer's is in
there somewhere, I believe). :-P
From: William James
Subject: Re: processing a sequence
Date: 
Message-ID: <gho7hs$r6f$1@aioe.org>
··················@gmail.com wrote:

> On Dec 7, 9:47�pm, Scott <·······@gmail.com> wrote:
> > On Dec 7, 7:49�pm, ·······@corporate-world.lisp.de"
> > <······@corporate-
> > 
> > world.lisp.de> wrote:
> > > (defun collect-sublists (list)
> > > � (flet ((collect-sublist ()
> > > � � � � � �(loop for element = (pop list)
> > > � � � � � � � � �while element collect element
> > > � � � � � � � � �while (and list
> > > � � � � � � � � � � � � � � (<= element (first list))))))
> > > � � (loop for sublist = (collect-sublist)
> > > � � � � � while sublist collect sublist)))
> > 
> > Thanks for the quick response! This does exactly what I need,
> > although I will certainly have to look at it closely to see exactly
> > how.
> > 
> > Best,
> > Scott
> 
> Here is a great function from "On Lisp"
> 
> (defun group (source n)
>   (if (zerop n) (error "zero length"))
>   (labels ((rec (source acc)
> 		(let ((rest (nthcdr n source)))
> 		  (if (consp rest)
> 		      (rec rest (cons (subseq source 0 n) acc))
> 		    (nreverse (cons source acc))))))
>     (if source (rec source nil) nil)))

That's extremely prolix, convoluted, and hideous.
If that's the best that Paul Graham can do ...

Ruby:

def group source, n
  acc = []
  0.step(source.size - 1, n){|i|
    acc << source[i,n] }
  acc
end

p group( %w(a b c d e f g), 2)

--- output ---
[["a", "b"], ["c", "d"], ["e", "f"], ["g"]]
From: Kenny
Subject: Re: processing a sequence
Date: 
Message-ID: <493caf8b$0$20284$607ed4bc@cv.net>
Scott wrote:
> On Dec 7, 7:49 pm, ·······@corporate-world.lisp.de" <······@corporate-
> world.lisp.de> wrote:
> 
>>(defun collect-sublists (list)
>>  (flet ((collect-sublist ()
>>           (loop for element = (pop list)
>>                 while element collect element
>>                 while (and list
>>                            (<= element (first list))))))
>>    (loop for sublist = (collect-sublist)
>>          while sublist collect sublist)))
> 
> 
> Thanks for the quick response! This does exactly what I need, although
> I will certainly have to look at it closely to see exactly how.

Nonsense! Your request was:

> Would someone kindly be able to offer some advice or a nudge in the
> right direction?

You received an alternative solution that did not identify why your 
solution was not working. No advice, no nudge.

As Lao Tzu might have said, "The subseq you can setf is not the true 
subseq".

hth,kzo
From: André Thieme
Subject: Re: processing a sequence
Date: 
Message-ID: <ghhrtg$cbk$1@news.motzarella.org>
······@corporate-world.lisp.de schrieb:

> (defun collect-sublists (list)
>   (flet ((collect-sublist ()
>            (loop for element = (pop list)
>                  while element collect element
>                  while (and list
>                             (<= element (first list))))))
>     (loop for sublist = (collect-sublist)
>           while sublist collect sublist)))

Nearly 15 minutes passed since you posted your solution, and William
James still didn�t show his Ruby one-liner that outperforms the Lisp
solution by a factor of 20 (speedwise). ;-)


Andr�
-- 
From: Dimiter "malkia" Stanev
Subject: Re: processing a sequence
Date: 
Message-ID: <ghjvq3$os4$1@malkia.motzarella.org>
Andr� Thieme wrote:
> ······@corporate-world.lisp.de schrieb:
> 
>> (defun collect-sublists (list)
>>   (flet ((collect-sublist ()
>>            (loop for element = (pop list)
>>                  while element collect element
>>                  while (and list
>>                             (<= element (first list))))))
>>     (loop for sublist = (collect-sublist)
>>           while sublist collect sublist)))
> 
> Nearly 15 minutes passed since you posted your solution, and William
> James still didn�t show his Ruby one-liner that outperforms the Lisp
> solution by a factor of 20 (speedwise). ;-)
> 
> 
> Andr�

Chubby Ruby,
My Dear Hubby,
I love you dear,
But can't you hear,
I'm talking lisp,
... takin' all the risk.

Oh, chubby rubby!
Badooby-booby!
From: William James
Subject: Re: processing a sequence
Date: 
Message-ID: <gho56s$hp3$1@aioe.org>
Andr� Thieme wrote:

> ······@corporate-world.lisp.de schrieb:
> 
> > (defun collect-sublists (list)
> >  (flet ((collect-sublist ()
> >           (loop for element = (pop list)
> >                 while element collect element
> >                 while (and list
> >                            (<= element (first list))))))
> >    (loop for sublist = (collect-sublist)
> >          while sublist collect sublist)))

"We don't need no stinkin' loops!"

Ruby:

list = [0,1,2,3] * 3

def collect_sublists list, prev=nil, accum=[[]]
  return accum if not element = list.first
  if prev and element < prev
    accum << [element]
  else
    accum[-1] << element
  end
  collect_sublists( list[1..-1], element, accum )
end

p collect_sublists( list )

# This could be slower if getting the last element in a list
# is expensive.

def collect_sublists_2 list, accum=[[]]
  return accum if not element = list.first
  if accum != [[]] and accum[-1][-1] > element
    accum << [element]
  else
    accum[-1] << element
  end
  collect_sublists_2( list[1..-1], accum )
end

> 
> Nearly 15 minutes passed since you posted your solution, and William
> James still didn�t show his Ruby one-liner that outperforms the Lisp
> solution by a factor of 20 (speedwise). ;-)
> 
> 
> Andr�

Ruby is about the slowest "scripting language".
JavaScript is faster.

SpiderMonkey and jslibs:

LoadModule('jsstd')

list = [0,1,2,3,0,1,2,3,1,2,3]

function collect_groups( list, prev, accum )
{ accum = accum || [[]]
  var element = list[0]
  if ( typeof element == "undefined" )
    return accum
  if (prev && element < prev)
    accum.push( [element] )
  else
    accum.slice(-1)[0].push( element )
  return collect_groups( list.slice(1), element, accum )
}

Print( collect_groups(list).toSource(), '\n')

--- output ---
[[0, 1, 2, 3], [0, 1, 2, 3], [1, 2, 3]]
From: ······@corporate-world.lisp.de
Subject: Re: processing a sequence
Date: 
Message-ID: <dbc85b8c-cab3-41bf-b19d-781c05d324be@p2g2000prf.googlegroups.com>
On 10 Dez., 11:21, "William James" <·········@yahoo.com> wrote:
> André Thieme wrote:
> > ······@corporate-world.lisp.de schrieb:
>
> > > (defun collect-sublists (list)
> > >  (flet ((collect-sublist ()
> > >           (loop for element = (pop list)
> > >                 while element collect element
> > >                 while (and list
> > >                            (<= element (first list))))))
> > >    (loop for sublist = (collect-sublist)
> > >          while sublist collect sublist)))
>
> "We don't need no stinkin' loops!"
>
> Ruby:
>
> list = [0,1,2,3] * 3
>
> def collect_sublists list, prev=nil, accum=[[]]
>   return accum if not element = list.first
>   if prev and element < prev
>     accum << [element]
>   else
>     accum[-1] << element
>   end
>   collect_sublists( list[1..-1], element, accum )
> end
>

 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1,
2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0,
1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3,
0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3]
>> p collect_sublists( list )
SystemStackError: stack level too deep
	from (irb):8:in `collect_sublists'
	from (irb):8:in `collect_sublists'
	from (irb):11
	from :0
>>

Oops, you don't need loops?

You need Lisp.

) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3
4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3
4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4))

CL-USER 3 >
From: William James
Subject: Re: processing a sequence
Date: 
Message-ID: <ghosr9$cec$1@aioe.org>
······@corporate-world.lisp.de wrote:

> On 10 Dez., 11:21, "William James" <·········@yahoo.com> wrote:
> > Andr� Thieme wrote:
> > > ······@corporate-world.lisp.de schrieb:
> > 
> > > > (defun collect-sublists (list)
> > > > �(flet ((collect-sublist ()
> > > > � � � � � (loop for element = (pop list)
> > > > � � � � � � � � while element collect element
> > > > � � � � � � � � while (and list
> > > > � � � � � � � � � � � � � �(<= element (first list))))))
> > > > � �(loop for sublist = (collect-sublist)
> > > > � � � � �while sublist collect sublist)))
> > 
> > "We don't need no stinkin' loops!"
> > 
> > Ruby:
> > 
> > list = [0,1,2,3] * 3
> > 
> > def collect_sublists list, prev=nil, accum=[[]]
> > � return accum if not element = list.first
> > � if prev and element < prev
> > � � accum << [element]
> > � else
> > � � accum[-1] << element
> > � end
> > � collect_sublists( list[1..-1], element, accum )
> > end
> > 
> 
>  3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1,
> 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0,
> 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3,
> 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3]
> >> p collect_sublists( list )
> SystemStackError: stack level too deep
> 	from (irb):8:in `collect_sublists'
> 	from (irb):8:in `collect_sublists'
> 	from (irb):11
> 	from :0
> > > 
> 
> Oops, you don't need loops?

Correct.  You are learning.

> 
> You need Lisp.
> 
> ) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3
> 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3
> 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4))
> 
> CL-USER 3 >

You need Ruby, one line of which does the work of 8 lines of
COBOL Lisp.

# inject is reduce.

list = [2,3,4,5] * 9999

clump=proc{|a| c=[[a[0]]]; a.inject{|p,x| x<p ? c<<[x] : c[-1]<<x;x};c}

p clump[ list ]

....
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5],
[2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5], [2, 3, 4, 5]]
From: William James
Subject: Re: processing a sequence
Date: 
Message-ID: <ghoug3$j45$1@aioe.org>
······@corporate-world.lisp.de wrote:

> On Dec 8, 1:08�am, Scott <·······@gmail.com> wrote:
> > Hi All,
> > 
> > I am trying to process a sequence like:
> > 
> > (0 1 2 3 0 1 2 3 0 1 2 3)
> > 
> > and produce:
> > 
> > ((0 1 2 3)(0 1 2 3)(0 1 2 3))
> > 
> > i.e. create sub-sequences beginning whenever the value decreases.
> > 
> > However, I am not having much luck (being pretty new to LISP). My
> > attempt was to use a loop with two collect statements, collecting
> > each number into one until its value decreases compared to the last
> > one, which then gets collected into another, then reset. Something
> > like this:
> > 
> > (loop
> > � for num in seq
> > � when (and (not (null subseq)) (<= num (car (last subseq)))
> > � � collect subseq into answer and
> > � � do (setf subseq nil)
> > � collect num into subseq
> > � finally (return answer))
...
> 
> (defun collect-sublists (list)
>   (flet ((collect-sublist ()
>            (loop for element = (pop list)
>                  while element collect element
>                  while (and list
>                             (<= element (first list))))))
>     (loop for sublist = (collect-sublist)
>           while sublist collect sublist)))

JavaScript (SpiderMonkey):

function clump(a){
  var c=[[a[0]]]
  a.reduce(function(p,x){x<p ? c.push([x]) : c.slice(-1)[0].push(x)
    return x})
  return c }
From: Rainer Joswig
Subject: Re: processing a sequence
Date: 
Message-ID: <joswig-ADFB5D.20111710122008@news-europe.giganews.com>
In article <············@aioe.org>,
 "William James" <·········@yahoo.com> wrote:

> ······@corporate-world.lisp.de wrote:
> 
> > On Dec 8, 1:08�am, Scott <·······@gmail.com> wrote:
> > > Hi All,
> > > 
> > > I am trying to process a sequence like:
> > > 
> > > (0 1 2 3 0 1 2 3 0 1 2 3)
> > > 
> > > and produce:
> > > 
> > > ((0 1 2 3)(0 1 2 3)(0 1 2 3))
> > > 
> > > i.e. create sub-sequences beginning whenever the value decreases.
> > > 
> > > However, I am not having much luck (being pretty new to LISP). My
> > > attempt was to use a loop with two collect statements, collecting
> > > each number into one until its value decreases compared to the last
> > > one, which then gets collected into another, then reset. Something
> > > like this:
> > > 
> > > (loop
> > > � for num in seq
> > > � when (and (not (null subseq)) (<= num (car (last subseq)))
> > > � � collect subseq into answer and
> > > � � do (setf subseq nil)
> > > � collect num into subseq
> > > � finally (return answer))
> ...
> > 
> > (defun collect-sublists (list)
> >   (flet ((collect-sublist ()
> >            (loop for element = (pop list)
> >                  while element collect element
> >                  while (and list
> >                             (<= element (first list))))))
> >     (loop for sublist = (collect-sublist)
> >           while sublist collect sublist)))
> 
> JavaScript (SpiderMonkey):
> 
> function clump(a){
>   var c=[[a[0]]]
>   a.reduce(function(p,x){x<p ? c.push([x]) : c.slice(-1)[0].push(x)
>     return x})
>   return c }

(define-modify-macro b! (&rest args) nconc) (defun clump (l &aux r) (reduce (lambda (a b) (if (> b a) (b! (car (last r)) (list b)) (b! r (list (list b)))) b) l :initial-value (car l)) r)

-- 
http://lispm.dyndns.org/