From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: "Basil L. Contovounesios" Newsgroups: gmane.emacs.bugs Subject: bug#33309: Add flatten-list? Date: Mon, 10 Dec 2018 22:42:14 +0000 Message-ID: <87tvjl80mx.fsf@tcd.ie> References: <87r2fw7jsa.fsf@gmail.com> <058f4a0f-7ce4-49c4-ae54-0bc259bd82d1@default> <87pnvg7fgg.fsf@gmail.com> <8736r5ojnc.fsf@gmx.de> <87sgz5m98k.fsf@gmail.com> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Trace: blaine.gmane.org 1544481668 14398 195.159.176.226 (10 Dec 2018 22:41:08 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 10 Dec 2018 22:41:08 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.0.50 (gnu/linux) Cc: 33309@debbugs.gnu.org, Michael Albinus , Stefan Monnier To: Alex Branham Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Mon Dec 10 23:41:03 2018 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1gWUEY-0003Zx-24 for geb-bug-gnu-emacs@m.gmane.org; Mon, 10 Dec 2018 23:41:02 +0100 Original-Received: from localhost ([::1]:35039 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gWUGe-0001Zf-Fl for geb-bug-gnu-emacs@m.gmane.org; Mon, 10 Dec 2018 17:43:12 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:35188) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gWUGX-0001ZP-Mg for bug-gnu-emacs@gnu.org; Mon, 10 Dec 2018 17:43:06 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1gWUGU-0004Mo-7L for bug-gnu-emacs@gnu.org; Mon, 10 Dec 2018 17:43:05 -0500 Original-Received: from debbugs.gnu.org ([208.118.235.43]:37970) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1gWUGT-0004MR-Sl for bug-gnu-emacs@gnu.org; Mon, 10 Dec 2018 17:43:02 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1gWUGT-0001pC-Md for bug-gnu-emacs@gnu.org; Mon, 10 Dec 2018 17:43:01 -0500 X-Loop: help-debbugs@gnu.org Resent-From: "Basil L. Contovounesios" Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Mon, 10 Dec 2018 22:43:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 33309 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: Original-Received: via spool by 33309-submit@debbugs.gnu.org id=B33309.15444817436971 (code B ref 33309); Mon, 10 Dec 2018 22:43:01 +0000 Original-Received: (at 33309) by debbugs.gnu.org; 10 Dec 2018 22:42:23 +0000 Original-Received: from localhost ([127.0.0.1]:42228 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1gWUFr-0001oN-Ce for submit@debbugs.gnu.org; Mon, 10 Dec 2018 17:42:23 -0500 Original-Received: from mail-ed1-f66.google.com ([209.85.208.66]:33034) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1gWUFp-0001o8-Tr for 33309@debbugs.gnu.org; Mon, 10 Dec 2018 17:42:22 -0500 Original-Received: by mail-ed1-f66.google.com with SMTP id p6so10942143eds.0 for <33309@debbugs.gnu.org>; Mon, 10 Dec 2018 14:42:21 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=tcd-ie.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version; bh=2NoJgeY+dQUoSqzk/XFSaIcvk9zVJNmv1uwRKZM1LCQ=; b=0Wi80nU5feEkEsnuRiMw1P1hJBDcrFZ5YiXq32LlDZy7nhwWVcRfOoVbe1miV7Zrr2 iLbSKvm3Jlx1hCWpAq7HYp3CMQZSLWi3ho1j+iS1n0mSZBzmAXaRqmPdkW+AlDaRLpwn igVRc6JUTth9tEKEcW5s4OJuI6WqisEGnhX5S2M7t6Ih9pIEFFDqKAVha79VpUw7ZkFr xDOw15/qdCX6HfCyK6ZAwVX3CrZxNsWSLkTCi9H6tydGpuca+4JTWKXrUi5Ka/xxlRVm 07rbEEvPPXGlUlVj1SeC1vGMRJEW8wInWvOVW6Q84KPMfNF3RDpuV5s+lxVIsqwlL+B3 ntvw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:references:date:in-reply-to :message-id:user-agent:mime-version; bh=2NoJgeY+dQUoSqzk/XFSaIcvk9zVJNmv1uwRKZM1LCQ=; b=iYHcyQSL8ek64gMhilsJ89P+scIxxpXOp8rxGYnR2ZId9n1r7yiUGorFblZ0gzEp0s nd28JnB86Dkjzr/bQU6aPi31HYCNBnzbF4kDa90jCeIId6RHTjTe73jYeSUSZ0cu0AnO k6h27FLDPh7EiISxvAmdBbwskeyY45/DWj7ddSKEKfzOoRj9/7XZw/jGwou3DoI4CJqC 5EaEpX1Ey0SKOA1r6s6uVJWW/l0wDDDNOOVkQfoHJkJ8yJOGIidVL2eNUmt+b7+H9P3G KZmj73u9aRitSUjFGn/VDc+ri5Gr8icTRE4ly7TJm5tCE3sipIUw9DFrruqN6BkehEuu flEw== X-Gm-Message-State: AA+aEWbBxNzQ6mayZslMwY4FgfdcwWImv3q4nNfYV5+mkHnqVYxS8yFI QskVajlpysQQVxe2ha0egTZb3g== X-Google-Smtp-Source: AFSGD/W5+QoW3Ul5ZYHiAM8OO3yyCC01mnGoO/Yc41EG+MV6JH7OeVMA7R2VuXp5DwOhbI/IdVOgOA== X-Received: by 2002:a17:906:881:: with SMTP id n1-v6mr10743803eje.7.1544481736046; Mon, 10 Dec 2018 14:42:16 -0800 (PST) Original-Received: from localhost ([2a02:8084:20e2:c380:f786:805d:f4ab:1006]) by smtp.gmail.com with ESMTPSA id t22-v6sm1986881ejl.58.2018.12.10.14.42.14 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Mon, 10 Dec 2018 14:42:15 -0800 (PST) In-Reply-To: <87sgz5m98k.fsf@gmail.com> (Alex Branham's message of "Mon, 10 Dec 2018 14:12:43 -0600") X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 208.118.235.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.org gmane.emacs.bugs:153314 Archived-At: --=-=-= Content-Type: text/plain [Sorry, Alex, for sending this to you twice - I accidentally made my last message a narrow, rather than wide, reply.] Alex Branham writes: > Thanks for the feedback, everyone. Thanks for working on this. > Here's a patch that implements `flatten-tree' which always returns a > list and recurses into conses. Given Emacs' recursive limitations, wouldn't an iterative implementation be better? For instance, the following currently blows max-specpdl-size: (length (flatten-tree (make-list 800 nil))) How about something like the following? --=-=-= Content-Type: text/x-diff Content-Disposition: inline; filename=flatten-tree.diff diff --git a/lisp/subr.el b/lisp/subr.el index f7eac75305..3fed3bc436 100644 --- a/lisp/subr.el +++ b/lisp/subr.el @@ -5453,10 +5453,15 @@ flatten-tree This always returns a list containing all the elements of TREE. \(flatten-tree \\='(1 (2 3 (4 5 (6))) 7)) => (1 2 3 4 5 6 7)" - (cond ((null tree) nil) - ((consp tree) (append (flatten-tree (car tree)) - (flatten-tree (cdr tree)))) - (t (list tree)))) + (let (elems) + (setq tree (list tree)) + (while (let ((elem (pop tree))) + (cond ((consp elem) + (setq tree (cons (car elem) (cons (cdr elem) tree)))) + (elem + (push elem elems))) + tree)) + (nreverse elems))) ;; Technically, `flatten-list' is a misnomer, but we provide it here ;; for discoverability: --=-=-= Content-Type: text/plain -- Basil --=-=-=--