Remove even appearance of elements from list with Lisp or PROLOG

I have to delete even appearance of element from list using LISP or PROLOG.

Here is some example.

input: '(5 2 (3 5 (3) 5 (4 2 (2 4))) 5 2)

output: '(5 2 (3 () 5 (4 (2))))

Structure of the output list remains t开发者_开发问答he same.

Thanks for advice,

Since this appears to be a homework, I am going to provide only a pointer to the solution:

• Review the REMOVE-IF predicate in Common Lisp. (It may not do everything you need...)
• Build a recursive walker.
• Consider how you will pass the state back and forth.

As an aside, I highly recommend posting a snippet of your work to date and asking a specific question. A generalized question such as the above seems to suggest you want a solution dropped in your lap.

Okay, it's not homework. And I got intellectually intrigued. I solved it.

It's a recursive walker. If your Lisp does TCO, it should be transformable into a TCO.

You can do it in a loop, but that would require maintaining a stack list to handle the "go into list" case.

I make no claims to an idiomatic solution.

(defparameter input '(5 2 (3 5 (3) 5 (4 2 (2 4))) 5 2))

(defparameter output '(5 2 (3 () 5 (4 (2)))))

(defun remove-every-other-appearence (list &optional (hash-table nil))
  (when list                             ; termination condition
    ;(format t "~%~a~&" list)
    (unless hash-table                     ; if it's the first time
      ;(format t "creating hash table~&")
      (setf hash-table (make-hash-table))) ; create a hash table
    (let ((eut (car list)))                ; element under test
      ;(format t "eut: ~a~&" eut)
      (cond
        ((consp eut)                      ;Recursion time, it's a list.
         ;(format t "Recursing~&")
         (cons
          (remove-every-other-appearence eut hash-table)
          (remove-every-other-appearence (cdr list) hash-table)))
        (t                                ;Otherwise...
                                        ; Increment seen counter by 1
         (setf (gethash eut hash-table 0) 
               (1+ (gethash eut hash-table 0)))
         (cond
           ((evenp (gethash eut hash-table))
             (remove-every-other-appearence (cdr list) hash-table))
                                        ;ignore the element
           ((oddp (gethash eut hash-table))
                                        ; if this is the odd occurance
                                        ;cons the element back onto the rest of the list
            (cons eut (remove-every-other-appearence (cdr list) hash-table)))           
           (t
            (error "This integer is neither even nor odd. We're in trouble"))))))))

* input

(5 2 (3 5 (3) 5 (4 2 (2 4))) 5 2)
* (remove-every-other-appearence input)

(5 2 (3 NIL 5 (4 (2))))
* output

(5 2 (3 NIL 5 (4 (2))))

FWIW, your problem statement is rather unclear.

As I understand the question, the problem is that you have an arbitrary "tree", the non-leaf nodes of which are lists and the leaf nodes of which are something else. A "list of lists" as it were. You would like to view that as a logical flat sequence of leaf nodes, iterate over that and remove every other leaf node without altering the overall shape of the "tree", such that the only thing that changes is the number of leaves hanging from any given node.

From that, given the following inputs, you'd realize the corresponding outputs:

input:  []
output: []

input:  [a,b,c,d]
output: [a,c]

input:  [a,[],b,c,d]
output: [a,[],c]

input:  [a,[b],c,d]
output: [a,[],c]

input:  [a,[b,c,d,e],f,g]
output: [a,[c,e],g]

input:  [a,[b,[],[c,d,[e,f,g],h],i],j]
output: [a,[[],[c,[e,g]],i]]

Here's an [untested] prolog solution. In it, I just maintaining two states, keep and remove and toggle between them as needed. You get odd/even for free: it just depends on the state in which you start the machine.

It should be noted that if the data structure passed in contains any unbound/non-unified variables, you're unlike to get correct results. Unwanted unification causes problems. Guard clauses would need to be added to properly handle with them.

% ====================
% The public interface
% ====================
remove_even( Xs , Ys ) :- remove_every_other_node( keep   , _ , Xs , [] , Ys ).
remove_odd(  Xs , Ys ) :- remove_every_other_node( remove , _ , Xs , [] , Ys ).

%------------------
% The core iterator
%------------------
remove_every_other_node( S , S , [] , T , List ) :-
  reverse(T,List)
  .
remove_every_other_node( S , N , [X|Xs] , T , List ) :-
  process_node( S, S1 , X , T , T1 ) ,
  remove_every_other_node( S1 , N , Xs , T1 , List )
  .

%----------------------
% The list node handler
%----------------------
process_node( S , S , []     , T , [[]|T] ).
process_node( S , N , [X|Xs] , T , [L1|T] ) :-
  remove_every_other_node( S , N , [X|Xs] , [] , L1)
  .
process_node( keep   , remove , X , T , [X|T] ).
process_node( remove , keep   , X , T , T     ).

(defun rea (tree)
  (let ((table (make-hash-table)))
    (labels ((fn (x)
               (unless (and x (atom x) (evenp (incf (gethash x table 0))))
                 (list (if (atom x) x (mapcan #'fn x))))))
      (car (fn tree)))))