Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #49147 > unrolled thread

Remove consecutive duplicates

Back to article view | Back to comp.lang.forth

Contents

  Remove consecutive duplicates "WJ" <w_a_x_man@yahoo.com> - 2016-07-14 06:59 +0000
    Re: Remove consecutive duplicates Richard Todd <richard.wesley.todd@gmail.com> - 2016-07-14 12:50 -0700
      Re: Remove consecutive duplicates Ron Aaron <rambamist@gmail.com> - 2016-07-15 13:43 +0300
        Re: Remove consecutive duplicates Ron Aaron <rambamist@gmail.com> - 2016-07-15 14:49 +0300
    Re: Remove consecutive duplicates Chris Curl <ccurl609@gmail.com> - 2016-07-14 17:14 -0700
      Re: Remove consecutive duplicates Julian Fondren <julian.fondren@gmail.com> - 2016-07-14 17:45 -0700
        Re: Remove consecutive duplicates missycurl@gmail.com - 2016-07-14 19:46 -0700
    Re: Remove consecutive duplicates "Ala'a" <amalawi@gmail.com> - 2016-07-15 14:25 -0700

#49147 — Remove consecutive duplicates

At the risk of blowing the stack (not tail-recursive):

let remove_consecutives ?(test=(=)) list =
  let rec loop = function
      [] -> []
    | a::b::rest when test a b -> loop (b::rest)
    | a::rest -> a :: loop rest
  in loop list ;;

remove_consecutives [2;2;3;4;4;4;5;2;6];;
 ===>
[2; 3; 4; 5; 2; 6]

remove_consecutives ~test:(<) [2;2;3;4;4;4;5;2;6;6];;
 ===>
[2; 4; 4; 5; 6; 6]

Since ANS Forth is the best language, show a better solution
in ANS Forth.


-- 
I would hesitate to describe America as a nation at all in 1997, because it is
something very different: a polyethnic federation administered by a single
ruling class....  [T]he accumulated rot in America has now reached a point
where the pillars of society itself are failing.  --- Ambrose Evans-Pritchard

[toc] | [next] | [standalone]

#49163

On Thursday, July 14, 2016 at 1:59:03 AM UTC-5, WJ wrote:
> At the risk of blowing the stack (not tail-recursive):
> 
> let remove_consecutives ?(test=(=)) list =
>   let rec loop = function
>       [] -> []
>     | a::b::rest when test a b -> loop (b::rest)
>     | a::rest -> a :: loop rest
>   in loop list ;;


Here's one way to do it, a destructive update version, no risk of 
blowing the stack, no allocation, fast:

: dedup ( test list  -- list )
   dup cell+   over @ 1 - cells over swap bounds 
   ?DO                             \ stack is: test list elem-to-write
      I dup @  swap  cell+ @       \ grab the next two elements  
      4 pick execute               \ execute the test
      0= IF I @ over ! cell+ THEN  \ write a list element if test failed
   cell +LOOP
   over dup @ cells + @ over !     \ write the last element 
   over - cell / over !  nip ;     \ update the list size and clean up

It expects a "list" which is a count + array.  Here's a way to print the list:

: .lst ( lst -- ) dup @ cells swap cell+ swap bounds 
     ?DO I @ .  cell +LOOP cr ;


> remove_consecutives [2;2;3;4;4;4;5;2;6];;
>  ===>
> [2; 3; 4; 5; 2; 6]

VARIABLE lst 9 lst ! 2 , 2 , 3 , 4 ,  4 , 4 , 5 , 2 , 6 ,
' = lst dedup .lst
2 3 4 5 2 6


> remove_consecutives ~test:(<) [2;2;3;4;4;4;5;2;6;6];;
>  ===>
> [2; 4; 4; 5; 6; 6]

VARIABLE lst 10 lst ! 2 , 2 , 3 , 4 ,  4 , 4 , 5 , 2 , 6 , 6 , 
' < lst dedup .lst
2 4 4 5 6 6

Though list processing isn't really forth's strong suit, the
implementation for specific problems isn't usually much longer
in terms of size, and will perform well.  If the problem is 
complex enough, a list library will be called for, which is also
what you wind up leaning on in other languages, anyway.

[toc] | [prev] | [next] | [standalone]

#49173

On 14/07/2016 22:50, Richard Todd wrote:

> Here's one way to do it, a destructive update version, no risk of 
> blowing the stack, no allocation, fast:

That's a good ANS version.  Here's a version in 8th:

: -dups \ a cmp -- a'
  >r
  -1 a:@ swap
  (
    tuck r@ w:exec not
  ) a:filter
  rdrop cr ;


Assuming a sorted array 'a', sorted based on the compare word 'cmp'
(which gives 'true' if the items are equal), the -dups word will remove
duplicate items.

This is generally useful, e.g. it will work on arrays of numbers or
strings (or other things), assuming the 'cmp' word provided works on
that data type.

So:

 [1,2,2,2,3,4,5,5] dup . cr
 ' n:= -dups . cr

Prints:
[1,2,2,2,3,4,5,5]

[1,2,3,4,5]

[toc] | [prev] | [next] | [standalone]

#49174

A cleanup of the previous one, which uses the same comparator as the sort:

: -dups \ a cmp -- a'
  >r
  -1 a:@ swap
  (
    tuck r@ w:exec
  ) a:filter
  rdrop nip ;

[toc] | [prev] | [next] | [standalone]

#49167

On Thursday, July 14, 2016 at 2:59:03 AM UTC-4, WJ wrote:
> At the risk of blowing the stack (not tail-recursive):
> 
> let remove_consecutives ?(test=(=)) list =
>   let rec loop = function
>       [] -> []
>     | a::b::rest when test a b -> loop (b::rest)
>     | a::rest -> a :: loop rest
>   in loop list ;;
> 
> remove_consecutives [2;2;3;4;4;4;5;2;6];;
>  ===>
> [2; 3; 4; 5; 2; 6]
> 
> remove_consecutives ~test:(<) [2;2;3;4;4;4;5;2;6;6];;
>  ===>
> [2; 4; 4; 5; 6; 6]
> 
> Since ANS Forth is the best language, show a better solution
> in ANS Forth.
> 
> 
> -- 
> I would hesitate to describe America as a nation at all in 1997, because it is
> something very different: a polyethnic federation administered by a single
> ruling class....  [T]he accumulated rot in America has now reached a point
> where the pillars of society itself are failing.  --- Ambrose Evans-Pritchard

Better? Please define "better". "Better" is subjective.

[toc] | [prev] | [next] | [standalone]

#49168

On Thursday, July 14, 2016 at 7:14:24 PM UTC-5, Chris Curl wrote:
> Better? Please define "better". "Better" is subjective.

Or you could do that.  Don't you have your own values?

Generally WJ's solutions can be made to take forever or to use
infinite RAM or to crash outright (as in this case) just by
supplying a non-trivial amount of input.  Take 'rosetta code compare
list of strings':

On Friday, January 22, 2016 at 9:42:29 PM UTC-6, WJ wrote: 
> Albert van der Horst wrote: 
> 
> > A much more practical (as in actually occuring) problem would be 
> > "given a text file, build a data structure in memory that allows 
> > lines to be accessed by their line number. Demonstrate it by 
> > having a function to type line N" 
> 
> That's so simple that it's not a problem [...] 
>
> IO.readlines("test.csv")[2].display 
>  ===> 
> Bill,22,M 

Look at that amazing one-liner.  Stylish.  Terse.  Readable.  Easy
to write.  All the real work is done by other people.  These are
WJ's values.

And applied to a 2GB file, that one-liner chews up a minute of time
and 4.6GB of RAM.  These are WJ's values: code that works on trivial
data sets, but which must be thrown away and completely re-written
once anyone actually tries to use it.  Imagine if someone asked you
for a tool to grab the nth line from a file, to use in some bash
scripts, and then pushed that Ruby oneliner to a server farm, and
then wrote some cronjobs that grabbed multiple lines from large log
files.  "Oh gosh, we had three hundred servers panic and reboot
themselves last night!  What the hell happened?"  Man I'd love to be
the supercoder explaining why I thought this was too simple to even
be a problem.


-- Julian

[toc] | [prev] | [next] | [standalone]

#49170

On Thursday, July 14, 2016 at 8:45:55 PM UTC-4, Julian Fondren wrote:
> On Thursday, July 14, 2016 at 7:14:24 PM UTC-5, Chris Curl wrote:
> > Better? Please define "better". "Better" is subjective.
> 
> Or you could do that.  Don't you have your own values?
> 
> Generally WJ's solutions can be made to take forever or to use
> infinite RAM or to crash outright (as in this case) just by
> supplying a non-trivial amount of input.  Take 'rosetta code compare
> list of strings':
> 
> On Friday, January 22, 2016 at 9:42:29 PM UTC-6, WJ wrote: 
> > Albert van der Horst wrote: 
> > 
> > > A much more practical (as in actually occuring) problem would be 
> > > "given a text file, build a data structure in memory that allows 
> > > lines to be accessed by their line number. Demonstrate it by 
> > > having a function to type line N" 
> > 
> > That's so simple that it's not a problem [...] 
> >
> > IO.readlines("test.csv")[2].display 
> >  ===> 
> > Bill,22,M 
> 
> Look at that amazing one-liner.  Stylish.  Terse.  Readable.  Easy
> to write.  All the real work is done by other people.  These are
> WJ's values.
> 
> And applied to a 2GB file, that one-liner chews up a minute of time
> and 4.6GB of RAM.  These are WJ's values: code that works on trivial
> data sets, but which must be thrown away and completely re-written
> once anyone actually tries to use it.  Imagine if someone asked you
> for a tool to grab the nth line from a file, to use in some bash
> scripts, and then pushed that Ruby oneliner to a server farm, and
> then wrote some cronjobs that grabbed multiple lines from large log
> files.  "Oh gosh, we had three hundred servers panic and reboot
> themselves last night!  What the hell happened?"  Man I'd love to be
> the supercoder explaining why I thought this was too simple to even
> be a problem.
> 
> 
> -- Julian

Yes, I have my own values, and I apply them constantly when I am working 
on programs that address real problems in the real world. 

WJ's stupid little "programming 101" challenges are ridiculous, and when 
he asks for something "better" I don't know what the fuck he means.

In the real world, with programs that lots of people depend on, "better" means
reliable, maintainable, and understandable. Some one line voodoo is worse.

[toc] | [prev] | [next] | [standalone]

#49182

for the = case (using spf4)

: range CELLS OVER + OVER ;
: ovwrt @ SWAP CELL+ TUCK ! ;
: xdup range DO DUP @ I @ <> IF I ovwrt THEN CELL +LOOP ;

CREATE list 2 , 2 , 3 , 4 , 4 , 4 , 5 , 2 , 6 ,
list 9 CELLS DUMP
CR
list 9 xdup
list 9 CELLS DUMP

xdup leaves the address of the last number on the stack. It can be removed or used for calculating final result length as needed by the application!

Ala'a

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web