Arc Forum | Can't see the bug in my short routine

Arc Forum

Can't see the bug in my short routine

2 points by map 6063 days ago | 6 comments

  (def collect-dups (lst)
    (rev (rem [< len._ 2]
      (reduce
        (fn (accum e)
          (if (or (is accum '(())) (is caar.accum e))
            (push e car.accum)
            (push list.e accum))
          accum)
        (cons '(()) lst))))) 

  (def collect-dups- (lst)
    (rev (rem [< len._ 2]
      (reduce
        (fn (accum e)
          (if (in caar.accum  e nil)
            (push e car.accum)
            (push list.e accum))
          accum)
        (cons '(()) lst))))) 


  (prn (collect-dups '(2 3 3 4 4 4 4 5 6 6 6 7)))
  (prn (collect-dups '(2 3 3 4 4 4 4 5 6 6 6 7)))
  (prn (collect-dups- '(2 3 3 4 4 4 4 5 6 6 6 7)))
  (prn (collect-dups- '(2 3 3 4 4 4 4 5 6 6 6 7)))

Output:

  ((3 3) (4 4 4 4) (6 6 6))
  ((3 3) (4 4 4 4) (6 6 6))
  ((3 3) (4 4 4 4) (6 6 6))
  ((2 2) (3 3) (4 4 4 4) (6 6 6))

The (2 2) in the last line is wrong.

1 point by sacado 6063 days ago | link

  (prn (collect-dups- '(2 3 3 4 4 4 4 5 6 6 6 7)))
  (prn (collect-dups- '(2 3 3 4 4 4 4 5 6 6 6 7)))

The two lines are equivalent, how can they produce different outputs ? I guess you made a mistake there ?

-----

5 points by almkglor 6063 days ago | link

You're passing in a list using ' - this is the problem

  (cons '(()) lst)

Try doing something like this:

  (def foo ()
   (let acc '(())
     (push 1 (car acc))))
  arc> (foo) (foo)

Generally, don't use '(...), unless you really really really have to. Use the longer 'list instead:

  (cons (list ()) lst)

-----

3 points by map 6063 days ago | link

As you hinted, the output of your example surprised me:

  (1)(1 1)

And your suggestion fixed my routine. But I don't understand why.

-----

5 points by eds 6063 days ago | link

It's because 'quote doesn't necessarily create a new list every time (at least not in function definitions). If you do

  (def foo ()
    '(a b c))

(foo) will return the same list every time, so if you modify the list in or before your next call, you'll get the modified instead of the original value.

-----

2 points by map 6063 days ago | link

That helps. Thanks.

-----

1 point by map 6063 days ago | link

For the record, here's an improved version translated from someone else's CL code:

  (def collect-dups (lst)
    (let accum nil
      (each e lst
        (if (is caar.accum e)
          (push e car.accum)
          (push list.e accum)))
      (rev (keep cdr accum))))

-----