LISP 中的函数式编程

Question

我刚刚开始学习函数式编程，这对我来说有点混乱，我现在有一个任务：从带有列表的行中删除所有重复项，所以：输入行：

(SETQ X (LIST  2 -3 (LIST 4 3 0 2) (LIST 4 -4) (LIST 2 (LIST 2 0 2))-3))

我希望输出是这样的：(2 -3 (4 3 0)(-4)()) 我想用递归来实现。我有一些概念性的问题：如何从列表中删除一个元素，或者我应该为输出创建一个新元素？在其他编程语言中，递归的每一步都有自己的变量范围，这里也一样吗？请问，你能描述一下方法吗，你会怎么做？

顺便说一句，我正在尝试运行此代码：

(SETQ X (LIST  2 -3 (LIST 4 3 0 2) (LIST 4 -4) (LIST 2 (LIST 2 0 2))-3))(DEFUN SEARCHDEEP (WHAT WHERE)
(COND
    ((NULL WHERE) NIL)
    (T (OR 
            (COND 
                ((ATOM (CAR WHERE)) (EQUAL WHAT (CAR WHERE)))
                (T (SEARCHDEEP WHAT  (CAR WHERE)))
            )
            (SEARCHDEEP WHAT (CDR WHERE))
        )
    )
))

(DEFUN REMDOUBLES (INPUT OUTPUT)(
(COND 
    ((NULL INPUT) NILL)
    (T 
        (REMDOUBLES (CDR INPUT) OUTPUT)
        (PRINT INPUT)
    )
)))


(REMDOUBLES X NIL)

但是我收到这个错误，这是什么意思？

SYSTEM::%EXPAND-FORM: (COND ((NULL INPUT) NILL) (T (REMDOUBLES (CDR INPUT) OUTPUT) (PRINT INPUT))) should be a lambda expression

Answer 1

我不懂 Common Lisp，但我想出了一个使用 racket 的解决方案。将它转换为 Lisp 应该是微不足道的，但我会把它留给你。由于无论如何这可能是一项家庭作业，因此通过代码工作并理解它对您有好处。

我认为我正在使用的唯一特定于球拍的东西是球拍的 mutable-set，它仅用于在我们将它们添加到输出时跟踪唯一值。过程计算完成后丢弃该集合。

#lang racket

(define input (list  2 -3 (list 4 3 0 2) (list 4 -4) (list 2 (list 2 0 2)) -3))

(define (procedure xs)
  (define (aux acc s xs)
    (cond [(empty? xs) (reverse acc)]
          [(list? (car xs)) (aux (cons (aux empty s (car xs)) acc) s (cdr xs))]
          [(set-member? s (car xs)) (aux acc s (cdr xs))]
          [else (begin (set-add! s (car xs))
                       (aux (cons (car xs) acc) s (cdr xs)))]))
  (aux empty (mutable-set) xs))

(define output (my-procedure input))

(display output)
; => (2 -3 (4 3 0) (-4) (()))

它有点复杂，因为它在一个过程中混合了树递归、折叠和唯一过滤。更好的解决方案是将这些过程分成通用过程，然后将它们组合成一个更具声明性的最终过程来完成您的预期任务。

Answer 2

在函数式编程中，您不会从参数中删除元素，因此您肯定会创建一个新列表，但是在许多情况下，您可以共享参数和结果中相同的结构（尾部）。

Common Lisp 是词法范围的。这意味着除了绑定变量之外，在创建函数时存在的自由变量加上全局范围也是已知的，就像您可能知道的其他语言一样，绑定变量在每次使用时都被绑定。

"something should be a lambda expression" 是 Common Lisp 错误，当您尝试在运算符位置使用表达式时。例如。 Scheme 代码 ((if (< x 10) + -) 5 10) 变为 15 或 -5 取决于操作数位置中表达式的计算结果。在 Common lisp 中，您可以有一个符号，例如。像 (+ 1 2) 中的 + 或 lambda，例如。 ((lambda (x) (* x x)) 10)。您尝试了 ((cond ...)) ，它可以在 Scheme 中使用，但不能在 Common Lisp 中使用。在 Common Lisp 中你需要做 (funcall (if (< x 10) #'+ #'-) 5 10)。由于括号在 C# 中几乎是花括号，我猜它们放错了地方，就好像有人会在语句 someFun(arg)() 的末尾添加一组 esxtra () 而 someFun 没有 return 一个函数。

我会像这样解决你的代码：

;; setq is for mutating, defparameter is a good option to make a global variable 
(defparameter *test* '(2 -3 (4 3 0 2) (4 -4) (2 (2 0 2)) -3))

(defun unique-elements (lst)
  (let ((h (make-hash-table :test 'equal)))
    (labels ((aux (lst)
               (cond ((null lst) '())
                     ((consp (car lst))
                      (let ((a (aux (car lst))))
                        (if (null a)
                            (aux (cdr lst)) ; don't include empty elements
                            (cons a (aux (cdr lst))))))
                     ((gethash (car lst) h)
                      (aux (cdr lst)))
                     (t (setf (gethash (car lst) h) t)
                        (cons (car lst) (aux (cdr lst)))))))
      (aux lst))))

(unique-elements *test*) ; ==> (2 -3 (4 3 0) (-4))

LISP 中的函数式编程

Functional programming in LISP

common-lisp

clisp