Re: Uniq list in Guile

[Panicz Maciej Godek <godek.maciek@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1227 bytes --]

There's also a "delete-duplicates" function available that comes with
SRFI-1.
It has a different behaviour, because it uniques the whole list, not just
the groups of adjacent elements, and is a pure function, but usually can be
used to achieve the desired effect.
The manual claims that it has an O(n^2) complexity. There's a simple way to
decrease the complexity to linear time (+ sorting time, if one wishes to
preserve the order) using a hash table, like that:

(define (unique elements)
  (let ((result (make-hash-table)))
    (let loop ((i 0)(lst elements))
      (if (pair? lst)
          (begin
            (hash-set! result (car lst) i)
            (loop (1+ i) (cdr lst)))
          (map car (sort-list (hash-map->list cons result)
                              (lambda (a b) (< (cdr a) (cdr b)))))))))

Perhaps someone else's opinion would be useful here, but I don't
think that UNIX-style "uniq" procedure should be common to Scheme
programming, and in particular -- its mutable variant, which makes it
completely uncomposable (the UNIX variant is immutable, so it can be
used with pipes). Note that uniq has to be used with sort in order to
express the above concept (i.e. removing duplicate entries).

Regards,
M.

[-- Attachment #2: Type: text/html, Size: 1572 bytes --]