Hi,
I was wondering whether there is something available which gives you
the position of an element not only in a sequence, but also in its
subsequences. For example:
[1]> (setf s '(x 1 1 (2 x (3 3 x) 2) 1))
(X 1 1 (2 X (3 3 X) 2) 1)
[2]> (where 'x s)
((0) (3 1) (3 2 2))
Which gives me a list of paths to each of the X's in the sequence.
The paths contain the successive indexes I'd have to give to NTH or
ELT together with the subsequence at that index. (Code at the end of
this post.)
It might also be handy to tell what I'm trying to accomplish here, in
case this is the wrong approach: I have a VRML file which is converted
to a Lisp object by read-from-string (see: <··············@xs4all.nl>).
The Lisp object of that file is a list with a lot of sublists. I'm
only interested in the content in some of those sublists and those are
preceded by a symbol, indicating their content. For example:
(VRML V2.0 UTF8 SHAPE
[...content deleted...]
(POINT (-80 0 -110 -80 ... etc. ...))
[...]
[3]> (where 'point vrml-object)
((4 2 7 0))
At which point I'd have to add one to the last item of the list to get
to the list with all the coordinates.
I frankensteined this together, which seems to be working well enough
for now. Fun to do, but I wanted to know whether something of
industrial strength already exists before I spend more time on it:
(defun where (item sequence)
(labels ((where-subseq (item subseq current-path)
(let ((length (length subseq))
(new-paths '()))
(dotimes (index length)
(if (typep (elt subseq index) 'sequence)
(let ((path-elt (where-subseq item (elt subseq index)
(append current-path
(list index)))))
(when (not (null path-elt))
(dolist (new-path path-elt)
(push new-path new-paths))))
(when (equal item (elt subseq index))
(push (append current-path (list index)) new-paths))))
new-paths)))
(let ((length (length sequence))
(paths '()))
(dotimes (index length)
(if (typep (elt sequence index) 'sequence)
(let ((path (where-subseq item (elt sequence index) (list index))))
(when (not (null path))
(dolist (new-path path)
(push new-path paths))))
(when (equal item (elt sequence index))
(push (list index) paths))))
paths)))
(Notes: It has only been tested on lists so far. Criticism on my Lisp
style very welcome!)
Regards,
Erik.
Erik Winkels wrote:
> I was wondering whether there is something available which gives you
> the position of an element not only in a sequence, but also in its
> subsequences. For example:
>
> [1]> (setf s '(x 1 1 (2 x (3 3 x) 2) 1))
> (X 1 1 (2 X (3 3 X) 2) 1)
>
> [2]> (where 'x s)
> ((0) (3 1) (3 2 2))
>
> Which gives me a list of paths to each of the X's in the sequence.
> The paths contain the successive indexes I'd have to give to NTH or
> ELT together with the subsequence at that index. (Code at the end of
> this post.)
>
> It might also be handy to tell what I'm trying to accomplish here, in
> case this is the wrong approach: I have a VRML file which is converted
> to a Lisp object by read-from-string (see: <··············@xs4all.nl>).
>
> The Lisp object of that file is a list with a lot of sublists. I'm
> only interested in the content in some of those sublists and those are
> preceded by a symbol, indicating their content. For example:
>
> (VRML V2.0 UTF8 SHAPE
> [...content deleted...]
> (POINT (-80 0 -110 -80 ... etc. ...))
> [...]
>
> [3]> (where 'point vrml-object)
> ((4 2 7 0))
> I frankensteined this together, which seems to be working well enough
> for now. Fun to do, but I wanted to know whether something of
> industrial strength already exists before I spend more time on it:
<snip>
I tried to do this to exercise my LOOP skills, but this felt so painful
that I think your architecture is unnecessarily complicated.
- First of all, if your interesting elements are always recognizable by
the first element, finding the position of any other element in that
sublist seems unnecessary.
- Is finding the paths (and presumably accessing those components later
by elt etc.) necessary? How about just recursing through the tree, and
either executing whatever operations you wish done "in-situ", or
returning the interesting sublists themselves? So instead of ((4 2 7
0)(6 7 8)...) you'd have something like ((POINT (-80 0 -110 -80
...))(POINT (-180 10 -10 -80 ...)) ...)
(In other words, instead of returning the indexes to reach the data just
return raw pointers to the data.)
--
Erik Winkels wrote:
> The Lisp object of that file is a list with a lot of sublists. I'm
> only interested in the content in some of those sublists and those are
> preceded by a symbol, indicating their content. For example:
>
> (VRML V2.0 UTF8 SHAPE
> [...content deleted...]
> (POINT (-80 0 -110 -80 ... etc. ...))
> [...]
>
> [3]> (where 'point vrml-object)
> ((4 2 7 0))
>
> At which point I'd have to add one to the last item of the list to get
> to the list with all the coordinates.
I don't understand why your function returns the positions of the
objects you're interested in. Wouldn't it be easier to just return the
objects directly?
> (let ((length (length subseq))
> (new-paths '()))
> (dotimes (index length)
> (if (typep (elt subseq index) 'sequence)
What you're doing here may be acceptable for code that works on vectors
or on very small lists. But for larger lists, you should be aware that
this way of stepping through the list takes O(n^2) time.
Instead of
(dotimes (index (length list))
... (elt list i) ...)
it's better to do something like
(dolist (elt list)
... elt ...)
or
(mapcar (lambda (elt) ... elt ...)
list)
or, if you really need the index,
(loop for elt in list
and index from 0
... elt ...
A shorter and faster way to write the function you gave would be:
(defun paths-to (item list)
(let ((paths '())
(index 0))
(dolist (elt list)
(cond ((listp elt)
(dolist (sub-path (paths-to item elt))
(push (cons index sub-path) paths)))
((equal elt item)
(push (list index) paths)))
(incf index))
paths))
Thanks to all who replied.
Arthur Lemmens <········@xs4all.nl> writes:
> I don't understand why your function returns the positions of the
> objects you're interested in. Wouldn't it be easier to just return
> the objects directly?
Yes it would be. I don't quite know what had gotten into me to solve
the problem way I did. I think I just wanted to write a function like
that :)
> What you're doing here may be acceptable for code that works on
> vectors or on very small lists. But for larger lists, you should be
> aware that this way of stepping through the list takes O(n^2) time.
Thanks for the reminder! I really ought to pay more attention to such
things.
From: Alexey Dejneka
Subject: Re: Branches to leafs on trees
Date:
Message-ID: <m3u1swwjcf.fsf@comail.ru>
Erik Winkels <·······@xs4all.nl> writes:
> Hi,
>
> I was wondering whether there is something available which gives you
> the position of an element not only in a sequence, but also in its
> subsequences. For example:
>
> [1]> (setf s '(x 1 1 (2 x (3 3 x) 2) 1))
> (X 1 1 (2 X (3 3 X) 2) 1)
>
> [2]> (where 'x s)
> ((0) (3 1) (3 2 2))
>
> Which gives me a list of paths to each of the X's in the sequence.
> The paths contain the successive indexes I'd have to give to NTH or
> ELT together with the subsequence at that index. (Code at the end of
> this post.)
(defun tree-find (item tree)
"Return NIL if ITEM is not in TREE, T if (EQL ITEM TREE), path as a list
of indexes in sublists otherwise."
(if (atom tree)
(eql item tree)
(loop for sublist in tree
and index from 0
for position = (tree-find item sublist)
when position do (return (if (eq position t)
(list index)
(cons index position))))))
--
Regards,
Alexey Dejneka