转换lisp函数以使用map

Question

您好我期待转换我现有的功能:

(defun checkMember (L A)
  (cond
    ((NULL L) nil)
    ( (and (atom (car L)) (equal (car L) A))  T )
    (T  (checkMember (cdr L) A))))

要使用地图功能,但我老实说无法准确理解地图功能是如何工作的,你可以告诉我这个功能是如何工作的吗？

这是我的尝试:

(defun checkMem (L A)
  (cond
    ((NULL L) nil)
    ( (and (atom (car L)) (equal (car L)  (car A)))  T )
    (T  (mapcar #'checkMem  (cdr L) A))))

Answer 1

这里的映射函数不合适,因为该任务涉及搜索列表以确定它是否包含匹配项.这不是映射.

映射意味着将每个元素传递给某个函数(通常以某种方式收集返回值).当然,我们可以滥用映射以某种方式解决问题.

但是,我可以建议这是一个减少问题而不是映射问题吗？减少意味着处理列表的所有元素,以便生成一个汇总该列表的单个值.

热身:用于reduce将元素添加到一起:

(reduce #'+ '(1 2 3)) -> 6

在我们的例子中,我们要以不同方式降低清单:到这是一个值T或NIL基于该列表中是否包含了一些项目.

解:

(defun is-member (list item)
  (reduce (lambda (found next-one) (or found (eql next-one item)))
          list :initial-value nil))

;; tests:
(is-member nil nil) -> NIL
(is-member nil 42) -> NIL
(is-member '(1) 1) -> T
(is-member '(1) 2) -> NIL
(is-member '(t t) 1) -> NIL  ;; check for accumulator/item mixup
(is-member '(1 2) 2) -> T
(is-member '(1 2) 3) -> NIL
...

使用(左关联)reduce函数的一个常见模式是将每个约简中的左参数视为通过reduce"线程化"的累计值.当我们做一个简单的减少+以添加数字时,我们不考虑这个,但用于减少的函数的左参数总是部分和.部分和被初始化为零,因为reduce首先调用+没有参数的函数,这是可能的:(+)在Lisp中为零.

具体来说,会发生什么(reduce #'+ '(1 2 3)):

• 首先,回复的reduce电话.(+)0
• 然后,减少调用(+ 0 1),产生部分和1.
• 接下来,(+ 1 2)使用前一个部分和作为左参数减少调用,将下一个元素作为右参数.3当然,这会回来.
• 最后,减少通话(+ 3 3),导致6.

在我们的例子中,我们通过减少"线程化"的累积值不是部分和,而是布尔值.这个布尔值成为在reduce函数found内部调用的左参数.我们使用明确指定初始值:initial-value nil,因为我们的lambda函数不支持不带参数调用.在每次调用我们的lambda时,我们都会短路:如果found为true,则表示先前的减少已经确定列表包含该项,我们只返回true.否则,我们检查正确的参数:列表中的下一个项目.如果它等于item,那么我们返回T,否则NIL.然后这T或者NIL成为found下次通话的价值.一旦我们返回T,这个值将通过剩余的减少"多米诺骨牌",从而导致T退出reduce.

如果您坚持使用映射,则可以执行以下操作:将每个元素映射到列表,如果元素与项目不匹配,则列表为空,否则为非空.以这样的方式进行映射,即将列表连接在一起.如果结果列表为非空,则原始列表必须包含该项的一个或多个匹配项:

(defun is-member (list item)
  (if (mapcan (lambda (elem)
                (if (eq elem item) (list elem))) list)
     t))

如果列表包含多次出现的项目,则此方法会执行大量浪费的分配.

(这种reduce方法也很浪费,因为它很明显返回值后会继续处理列表T.)