From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Panicz Maciej Godek Newsgroups: gmane.lisp.guile.user Subject: Re: Uniq list in Guile Date: Sat, 26 Oct 2013 10:03:44 +0200 Message-ID: References: <87d2mspkt3.fsf@gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=047d7bf15fc84c3e4904e9a04eae X-Trace: ger.gmane.org 1382774632 11671 80.91.229.3 (26 Oct 2013 08:03:52 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 26 Oct 2013 08:03:52 +0000 (UTC) Cc: guile-user To: Dmitry Bogatov Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Sat Oct 26 10:03:57 2013 Return-path: Envelope-to: guile-user@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1VZyqh-0000B0-Jn for guile-user@m.gmane.org; Sat, 26 Oct 2013 10:03:55 +0200 Original-Received: from localhost ([::1]:33790 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VZyqh-0000hK-6Z for guile-user@m.gmane.org; Sat, 26 Oct 2013 04:03:55 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:49013) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VZyqY-0000h9-CR for guile-user@gnu.org; Sat, 26 Oct 2013 04:03:47 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VZyqX-0003d9-BB for guile-user@gnu.org; Sat, 26 Oct 2013 04:03:46 -0400 Original-Received: from mail-ve0-x22d.google.com ([2607:f8b0:400c:c01::22d]:57114) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VZyqX-0003d1-6O; Sat, 26 Oct 2013 04:03:45 -0400 Original-Received: by mail-ve0-f173.google.com with SMTP id jw12so3548345veb.32 for ; Sat, 26 Oct 2013 01:03:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=NlSrypv6fCAksVavr0o9mY2+2AcZ/8K6YGCX1gsggSI=; b=NQzL13WtFrDf1BuSc7QaRat0bdq5s22iC0KcsyRQHr4g8Tp7pXRpC3ES/KPNk5Lrpy zHPV7VghXIBzQhkEvt7S+bJS7NQ8u2+X+NQsVPjgocaV8qtwC81fke4pYADGBtJMeaZc 7t0kQyy8Qq+VttJb7UqmLzyk6IKROJmKCRL4D7LZmUmutso8YdGexGiz0FAUJkKWQh01 4FZT+6TqkAcGV/nCnB8KjHEGOBVEA8FWVQIrOslfLb11xnNU5s9xMG6xLaPPhvQVttVM 5WNNQN/i89ra8SDmw03gDjnGYJJmtsCNrJ/jM/v9LlcWunvQGyN5eo2woXYzvCHT2ZgA Rk9g== X-Received: by 10.58.255.233 with SMTP id at9mr7081005ved.20.1382774624499; Sat, 26 Oct 2013 01:03:44 -0700 (PDT) Original-Received: by 10.220.113.142 with HTTP; Sat, 26 Oct 2013 01:03:44 -0700 (PDT) In-Reply-To: <87d2mspkt3.fsf@gnu.org> X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2607:f8b0:400c:c01::22d X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: General Guile related discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane.org@gnu.org Original-Sender: guile-user-bounces+guile-user=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.user:10857 Archived-At: --047d7bf15fc84c3e4904e9a04eae Content-Type: text/plain; charset=ISO-8859-1 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. --047d7bf15fc84c3e4904e9a04eae Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
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 i= s 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 simp= le way to decrease the complexity to linear time (+ sorting time, if one wi= shes to=A0
preserve the order) using a hash table, like that:

(define (unique elements)
=A0 (let ((res= ult (make-hash-table)))
=A0 =A0 (let loop ((i 0)(lst elements))
=A0 =A0 =A0 (if (pair? lst)
=A0 =A0 =A0 =A0 =A0 (begin
=A0 =A0 =A0 =A0 =A0 =A0 (hash-set! result (car lst) i)
=A0 =A0 =A0 =A0 =A0 =A0 (loop (1+ i) (cdr lst)))
=A0 =A0 =A0= =A0 =A0 (map car (sort-list (hash-map->list cons result)
=A0 = =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (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 com= mon to Scheme
programming, and in particular -- its mutable varia= nt, 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).<= /div>

Regards,
M.

--047d7bf15fc84c3e4904e9a04eae--