List of indexes

Q&A's, tips, howto's
Locked
cameyo
Posts: 183
Joined: Sun Mar 27, 2011 3:07 pm
Location: Italy
Contact:

List of indexes

Post by cameyo »

How to create a list of indexes of all the elements of a generic list?
Example:
Input: (setq lst '(1 (2 (3 4)) (5 6)))
(lst 0)
1
(lst 1)
(2 (3 4))
(lst 1 0)
2
(lst 1 1)
(3 4)
(lst 1 1 0)
3
(lst 1 1 1)
4
(lst 2)
(5 6)
(lst 2 0)
5
(lst 2 1)
6

Output: List of indexes of lst
((0) (1) (1 0) (1 1) (1 1 0) (1 1 1) (2) (2 0) (2 1))
or
(0 1 (1 0) (1 1) (1 1 0) (1 1 1) 2 (2 0) (2 1))

p.s. can't post formatted code on forum (Internal Server Error)

fdb
Posts: 66
Joined: Sat Nov 09, 2013 8:49 pm

Re: List of indexes

Post by fdb »

Something like below? (not very elegant, I know)

Code: Select all

(define (index-list lst)
  (setq mylist '())
  (define (h-index-list lst agg)
    (dolist (x lst)
      (setq mv (append agg (list $idx)))
      (push mv mylist -1)
      (if (list? x)
        (h-index-list x mv)))
    mylist)
  (h-index-list lst '()))

rickyboy
Posts: 607
Joined: Fri Apr 08, 2005 7:13 pm
Location: Front Royal, Virginia

Re: List of indexes

Post by rickyboy »

Here's a version that uses recursive calls in a classic way (think, SICP) where even the loop is handled by recursive call. (Nota bene: This is not a good newLISP implementation because newLISP doesn't turn tail calls into loops; fdb's implementation is the better one for newLISP.)

Code: Select all

(define (get-indices L (child 0) (parents '()) (result '()))
  (if (empty? L)
      result
      (list? (L 0))
      (get-indices (1 L) (+ 1 child) parents
                   (append (snoc result (snoc parents child))
                           (get-indices (L 0) 0 (snoc parents child))))
      (get-indices (1 L) (+ 1 child) parents
                   (snoc result (snoc parents child)))))
You will need this utility function, snoc, which acts like cons but does the reverse (it says it in the name lol :) : it takes the element argument and puts it at the end of the list. (Note also that the arguments are reversed as compared with cons.)

Code: Select all

(define (snoc xs x) (push x xs -1))
(λx. x x) (λx. x x)

rickyboy
Posts: 607
Joined: Fri Apr 08, 2005 7:13 pm
Location: Front Royal, Virginia

Re: List of indexes

Post by rickyboy »

You could also "factor out" the repeated code, but it may not make the code more readable.

Code: Select all

(define (get-indices L (child 0) (parents '()) (result '()))
  (if (empty? L)
      result
      (get-indices (1 L) (+ 1 child) parents
        (append
          (snoc result (snoc parents child))
          (if (list? (L 0))
              (get-indices (L 0) 0 (snoc parents child))
              '())))))
(λx. x x) (λx. x x)

cameyo
Posts: 183
Joined: Sun Mar 27, 2011 3:07 pm
Location: Italy
Contact:

Re: List of indexes

Post by cameyo »

Thank you guys
Very nice solutions
@rickyboy: "Nota bene" is Italian :-)

cameyo
Posts: 183
Joined: Sun Mar 27, 2011 3:07 pm
Location: Italy
Contact:

Re: List of indexes

Post by cameyo »

Faster solution:

Code: Select all

(setq a '(1 (2 (3 4)) (5 6)))
;Indexes
(ref-all nil a (fn (x) true))
((0) (1) (1 0) (1 1) (1 1 0) (1 1 1) (2) (2 0) (2 1))
;Elements
(ref-all nil a (fn (x) true) true)
(1 (2 (3 4)) 2 (3 4) 3 4 (5 6) 5 6)

Locked