From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: kwright@free-comp-shop.com Newsgroups: gmane.lisp.guile.user Subject: Re: Question about data structures Date: Sun, 22 Nov 2020 15:58:08 -0500 Message-ID: <87r1olw1lr.fsf@fcs22.keithdiane.us> References: <3b07669d7286df2542796e309db101423bb3e147.camel@divoplade.fr> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="7646"; mail-complaints-to="usenet@ciao.gmane.io" Cc: guile-user@gnu.org To: divoplade Original-X-From: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Sun Nov 22 21:58:54 2020 Return-path: Envelope-to: guile-user@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1kgwRi-0001sS-7e for guile-user@m.gmane-mx.org; Sun, 22 Nov 2020 21:58:54 +0100 Original-Received: from localhost ([::1]:40670 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kgwRh-0000Bg-8D for guile-user@m.gmane-mx.org; Sun, 22 Nov 2020 15:58:53 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:49772) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kgwRW-0000BY-GX for guile-user@gnu.org; Sun, 22 Nov 2020 15:58:42 -0500 Original-Received: from dsl.keithdiane.us ([66.92.74.188]:50647) by eggs.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kgwRU-00070T-Mb for guile-user@gnu.org; Sun, 22 Nov 2020 15:58:42 -0500 Original-Received: from fcs22.keithdiane.us (fcs22.keithdiane.us [192.168.1.121]) by fcs19.keithdiane.us (Postfix) with ESMTP id 5363E218375; Sun, 22 Nov 2020 15:58:09 -0500 (EST) Original-From: Keith Wright In-Reply-To: <3b07669d7286df2542796e309db101423bb3e147.camel@divoplade.fr> (message from divoplade on Sun, 22 Nov 2020 20:45:05 +0100) Received-SPF: pass client-ip=66.92.74.188; envelope-from=kwright@free-comp-shop.com; helo=dsl.keithdiane.us X-Spam_score_int: -16 X-Spam_score: -1.7 X-Spam_bar: - X-Spam_report: (-1.7 / 5.0 requ) BAYES_00=-1.9, HEADER_FROM_DIFFERENT_DOMAINS=0.249, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=no autolearn_force=no X-Spam_action: no action X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.23 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-mx.org@gnu.org Original-Sender: "guile-user" Xref: news.gmane.io gmane.lisp.guile.user:17038 Archived-At: divoplade writes: > Hello Zelphir! > > Le dimanche 22 novembre 2020 =C3=A0 19:48 +0100, Zelphir Kaltstahl a =C3= =A9crit : >> However, when I use the list in reverse and ever need >> to output the lines in the list in their original >> order, I would first need to `reverse` the list again. > There is a "reverse" function; you could implement it yourself as a > tail-recursive function if you wanted (it's currently implemented in C, > so my guess is it's even more efficient). You don't need vectors for > that. > > (define (my-reverse-aux accumulation list) > (if (null? list) > accumulation > (my-reverse-aux (cons (car list) accumulation) (cdr list)))) > > (define (my-reverse list) > (my-reverse-aux '() list)) > > (my-reverse '(a b c d e f g h)) There is also a reverse! procedure. (reverse! '(a b c))=20 $1 =3D (c b a) I have not actually looked at the code, but I assume from the "!" in the name and a decent respect for competence of the programmers, that it uses the well-known algorithm to reverse a list by destructive update. This algorithm is still O(n), but who cares? It is at least O(n) to read n lines, no matter how how you read them. The cost is amortised and is only O(1) per line. The thing to avoid is "cons". The my-reverse procedure above still does O(n) times cons, which uses storage, and may call garbage collection. The destructive update algorithm does O(n) times update one storage location and a couple of registers, which is trivial compared to reading a line. Just remember not to save pointers into the original non-reversed list, because it gets smashed. (You can still save pointers to the _members_ of the list.) -- Keith, Programmer in Chief, Free Computer Shop, http://www.free-comp-shop.com/ Food, Shelter, Source code =20=20=20