how to remove repeat element in a list

Here is one way to do it with a table while maintaining order:

procedure(myUniqueList(aList)
    let((uTable newList)
        uTable = makeTable("uTable" nil)
        foreach(element aList
            unless(uTable[element]
                newList = cons(element newList)
                uTable[element] = t
            )
        )
        reverse(newList)
    )
)

Derek

See this post.

I'd also like to point people to the very useful series of blogs "SKILL for the skilled" (more can be found by following the link for Team SKILL). Not sure this specific issue has been covered there, but it's worth looking at in general!

Regards,

Andrew.

Hi Derek:

thanks your help . it works.

but if I want to change the list as below to a sequest list , the format is OD, PO fisrt, then M1~M5, VIA1~VIA3,

ex:

aa = list( "VIA2" "VIA1" "VIA3" "M2" "M4" "M5" "M1" "OD" "PO")

       change to  ---->list("OD" "PO" "M1" "M2" "M3" "M4" "M5" "VIA1" "VIA2" "VIA3")

Your first post said you wanted to maintain the order and this one wants the result sorted. There are commands for sorting lists and you can create your own custom sort. I'm not quite sure what kind of order you described. It is not alphabetical and I don't know that OD and PO represent.

To sort alphabetically:
sortedList = sort(aa 'alphalessp)

To sort custom:
sortedList = sort(aa 'myCustomSort)

procedure(myCustomSort(a b)
  ;write custom code to determine if a should come before b
  ;return t if a comes before b
  ;return nil if b comes before a
)

Derek

Hi Derek, here is an interesting way to remove duplicates from a list maintaining order. It uses the function, mapcon, which was added to SKILL in SKILL version 33.  If you are using SKILL version 32 or earlier, you may not have this function.

(defun SkxUniquify (data)
  (foreach mapcon data data
    (unless (member (car data) (cdr data))
      (ncons (car data)))))

If the mapcon function is not defined in your SKILL version, you can define it yourself, but less efficently as follows.

;; This function iterates like map and maplist, but nconcs the return
;; values of the function like mapcan.
(unless (isCallable 'mapcon)
(defun mapcon (fn @rest args)
  (let ((buf (ncons nil)))
    (apply map (lambda (@rest args)
                 (lconc buf (apply fn args))) args)
    (car buf))))

If you define mapcon yourself, you unfortunately won't be able to use the shorthand version of foreach mapcon. You'll have to use mapcon directly as follows.

(defun SkxUniquify (data)
  (mapcon (lambda (data)
            (unless (member (car data) (cdr data))
              (ncons (car data))))
          data)) 

Kind Regards
Jim

Jim,

The downside of this implementation is that it is O(n^2) and whilst the list is in order, it's in the order of the last occurrence rather than first occurrence of a repeated value.

An ordered version which is a bit cleaner than Derek's and avoids a reverse is:

 procedure(CCFuniqueInOrder(lst)
  let(((uniq makeTable('uniq)))
    setof(elem lst
    !boundp(uniq[elem]) && (uniq[elem]=t)
    )
  )
)

This is making the assumption that 'unbound is not in the list (which is probably a reasonable assumption in most scenarios).

For a list with 1000000 random integers with values up to 10000,  this took 0.65s (on my laptop running on battery only), whereas I gave up with yours. Running with a list 10 times shorter took 29s, so I'd reasonably expect the original list to take 100 times longer than that, i.e. ~2900s. My example is roughly O(n).

Regards,

Andrew.

Hi Andrew, I agree that the fastest way to remove duplicates is using a hash table.  But a warning should sit above such a function as CCFuniqueInOrder.  One must be sure that the unbound symbol is not in the list being examined.  The unbound symbol is indeed likely to appear in the list if your application is operating on SKILL code.  E.g., if you are trying to find all the symbols in your SKILL code for the purpose of examining function prefixes etc.

Another limitation of hash tables is that not all SKILL data types are valid hash keys.  Three types come to mind quickly.  CDF objects (such as returned from cdfGetInstCDF), PCRE compiled expressions (such as returned from pcreCompile), and hash tables themselves.  If you attempt to use CCFuniqueInOrder to remove duplicates from a given list of hash tables, i.e., a list of hash tables which might contain the same hash table more than once, then uniq[elem] will trigger an error.

For example:

 (let ((x (makeTable 'x)) (y (makeTable 'y))) (CCFuniqueInOrder (list x x y y)))
*Error* assoc hash: given user type is not supported in assoc tables - table:x
<<< Stack Trace >>>
uniq[elem]
boundp(uniq[elem])
!boundp(uniq[elem])
(!boundp(uniq[elem]) && (uniq[elem] = t))
setof(elem lst (!boundp(&) && (uniq[elem] = t)))
let(((uniq makeTable(&))) setof(elem lst (!& && (uniq[elem] = t))))
CCFuniqueInOrder(list(x x y y))
let(((x makeTable(&)) (y makeTable(&))) CCFuniqueInOrder(list(x x y y)))

Admittedly this case is exremely rare. Most SKILL users will never need to worry about such extreme corner case.

Regards,

Jim. 

HI Derek, an interesting varient of removing duplciates from a list comes up when you slightly relax the meaning of duplicate.  For example, suppose you want to look at a list of strings, removing duplicates, but looking at the strings in a case independenty way. For exmaple, you might consider "AAA", "Aaa", and "aaa" to be duplicates.   Here is how you might do it.  First generalize SkxUniquify so that it can use a function other than equal to compare two elements.  Thereafter, use this generalized SkxUniquify to implement SkxRemoveDupStringsCi ...

(defun SkxUniquify (data @key (cmp equal))
  (mapcon (lambda (data)
            (unless (exists item (cdr data)
                      (cmp item (car data)))
              (ncons (car data))))
          data)) 

(defun SkxRemoveDupStringsCi (strings)
  (SkxUniquify strings
               ?cmp (lambda (a b)
                      (equal (lowerCase a)
                             (lowerCase b))))) 

(SkxRemoveDupStringsCi '("Aaa" "AAA" "AAA" "ABC" "abc" "aaa" "AAA")) 
=> ("abc" "AAA")

Hi Andrew,

I managed to cook up a faster implementation using tables, based on a solution elsewhere:

(defun rmDuplicates (lst "l")

  (let ((r (makeTable 'r)))

    (foreach e lst r[e]=t)

    r->?))

Sorting an array of symbols 10000000 times, I see that my function is about 1.4x faster.

Maybe tables are the way to go for efficient skill programs!

Dushyant