;;; Can we write the classic MEMBER function, which returns the cons
;;;   cell of a matching element, as a REDUCE? Yes, we can---but don't
;;;   ask AIs to do it!

;;; The obstacle is simple: the basic form of REDUCE applies the
;;;   two-argument function to values in the list, i.e., the CARs of
;;;   the list's cons cells. However, we need the cons cells
;;;   themselves, so that we can return the one with the matching 
;;;   element, as MEMBER does.

;;; The answer is also simple: we'll need to use the fold style, and
;;;   have our two-argument function take a pair of a cons cell
;;;   pointer and a CAR value and return a cons cell pointer. We'll use
;;;   a left fold with the :initial-value of the list itself, and make REDUCE
;;;   iterate over the list's cons cells. The solution is at the end of
;;;   this file.

;;;;;;;; I thought, why not ask an AI to write a MEMBER implementation via REDUCE? 
;;;;;;;;   The results were not great.

;;; The following was AI-generated. It claims to be a fold-style implementation,
;;;   but it's not. It's just a recursive function with an accumulator that doesn't
;;;   actually accumulate anything. It's just unnecessarily complex.

(defun fold-member-cons-ai (x lst)
  (labels ((fold (lst acc)
             (if (or acc (null lst))  ; return if 
                 acc
                 (fold (cdr lst)
                       (if (equal (car lst) x)
                           lst  ; return sublist starting at matched element
                           nil)))))
    (fold lst nil)))
fold-member-cons-ai

;; At least it matches MEMBER's behavior.

(fold-member-cons-ai 'b '(a b c d))  ; returns (b c d)
(b c d)

(fold-member-cons-ai 'z '(a b c d))  ; returns nil
nil

(fold-member-cons-ai nil '(a nil c d))  ; correct
(nil c d)


;; This function, also suggested by AI, returns the matching element, not
;;   its cons cell. The structure of this function is also suspect.
(defun fold-member-ai (x lst)
  (fold-left (lambda (found elem)
               (if found
                   found
                   (if (equal elem x) elem nil)))
             nil
             lst))
fold-member-ai

;; Here fold-left is a pretty standard tail-recursive left fold, no issues there:

(defun fold-left (fn init lst)
  (if (null lst)
      init
      (fold-left fn (funcall fn init (car lst)) (cdr lst))))
fold-left

;; Except, this doesn't work the same way as LISP's MEMBER:

(fold-member-ai nil '(nil nil nil))
nil                              ; indistinguishable from false

(fold-member-ai nil '(A nil nil))
nil                              ; indistinguishable from false

;;   whereas MEMBER handles these differently:

(member nil '(nil nil nil))
(nil nil nil)                    ; true

(member nil '(A nil nil))
(nil nil)                        ; true

;;; Another AI variant, more unnecessary complications. But at least
;;;   it uses REDUCE as asked.

(cl-defun member-cons-via-reduce-ai (item list &key (test #'eql))
  (reduce (lambda (found tail)
            (or found
                (and (funcall test item (car tail))
                     tail)))
          (loop for cell on list collect cell)  ;; why this?
          :initial-value nil))
member-cons-via-reduce-ai

;; and matches MEMBER's behavior.

(member-cons-via-reduce-ai nil '(nil nil nil))
(nil nil nil)

(member-cons-via-reduce-ai nil '(A nil B C D))
(nil B C D)

(member-cons-via-reduce-ai nil '(A B C D))
nil

(member-cons-via-reduce-ai nil nil)
nil

;;;;;;;;;;;;;;;;;;;; OK, enough AIs for now ;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Actually, the solution is really simple (although not quite optimal):

(defun actual-member-via-left-fold (x lst)
    (reduce (lambda (l c)                ; c is a dummy argument, unused
	      (if (equal (car l) x) l
		(cdr l)))
	    lst              
	    :initial-value lst))         ; start with the list itself. The lambda
                                         ;  maps a (list, element) -> list
actual-member-via-left-fold


(actual-member-via-left-fold 'x '(x y z))
(x y z)

(actual-member-via-left-fold 'z '(x y z))
(z)

(actual-member-via-left-fold 'u '(x y z))
nil

(actual-member-via-left-fold nil '(x nil z))
(nil z)

(actual-member-via-left-fold 'x nil)
nil