英文:

lambda function to omit value on a list

问题

我在想是否有一种方法可以编写一个lambda函数（递归？），可以省略给定列表中的某个值（它的每次出现）？

我尝试想出一个想法，但整个事情都崩溃了 - 因为我们总是需要指定lambda的主体，因为它在代码中的出现位置进行计算。

我曾认为可以通过另一个lambda来指定lambda主体来完成，但我不知道如何做。

英文:

I am wondering if there is any way to write a lambda function(recursively?), that omits certain value(it's every occurence) on a given list?

I tried come up with an idea, but the whole thing breaks down - because we need to always specify a body of our lambda, because it is calculated at occurence place in code.

I thought it could be done by specifying lambda body with another lambda, but I have no clue on how to do it.

答案1

得分: 3

我有一个 lambda -

(lambda (x)
  ...)

但在 ... 表达式中，我想要递归调用它。我知道如果给 lambda 一个名字，我可以通过名字调用它，但我想要在没有名字的情况下递归。让我们想象另一个 lambda，它将其参数应用于自身 -

(lambda (f) (f f))

现在让我们将它应用于我们原始的 lambda -

((lambda (f) (f f))
 (lambda (x) ...))

现在 x 是对自身的引用！好的，那么这如何实现递归呢？x 是我们的 lambda，当应用于自身时提供了递归的机制 -

((lambda (f) (f f))
 (lambda (x) ;; x *is* this lambda
   (println "infinite recursion happening now...")
   (x x))) ;; apply x to itself to recur

"infinite recursion happening now..."
"infinite recursion happening now..."
"infinite recursion happening now..."
"infinite recursion happening now..."
...
(无限循环)

所以这很好，但我们怎样停止无限递归呢？更重要的是，我们如何在途中传递参数？

正如我们所看到的 (x x) 推动了递归。如果我们只在一个 条件 下递归，我们可以控制过程何时退出。让我们让我们的 (lambda (x) ...) 返回另一个过程，而不是 (lambda (n) ...) -

((lambda (f) (f f))
 (lambda (x)
   (lambda (n)
     (if (zero? n)  ; 条件
         ...        ; 完成
         (x x)))))  ; 否则继续递归

然而，现在 (x x) 不会立即递归，而是返回一个过程 (lambda (n) ...)，因此我们可以将其应用于一个参数，以传递一个新的 n 值 -

((lambda (f) (f f))
 (lambda (x)
   (lambda (n)
     (if (zero? n)
         "done"
         (begin
           (printf "~a ...\n" n)
           ((x x)                 ; (x x) 返回 λn 
            (sub1 n)))))))        ; 更新的 n

因此，概括地说，外部的 λf 将 λx 应用于自身，现在返回 λn。现在我们将 that 应用于一个参数，并见证了无名的、匿名的过程递归 -

(((lambda (f) (f f))
  (lambda (x)
    (lambda (n)
      (if (zero? n)
          "done"
          (begin
            (printf "~a ...\n" n)
            ((x x)
             (sub1 n)))))))
 5) ; 将该过程应用于 5

5 ...
4 ...
3 ...
2 ...
1 ...
done

u combinator

我们上面写的组合器被称为 u combinator

(define u
  (lambda (f) (f f)))

我们可以使用 u 重写我们的程序 -

((u (lambda (x)            ; (u (lambda (x) ...))
      (lambda (n)
        (if (zero? n)
            "done"
            (begin
              (printf "~a ...\n" n)
              ((u x)                 ; (u x) 递归
               (sub1 n)))))))
 5)

y combinator

然而，(x x) 和 (u x) 的递归机制有点奇怪。如果我们能传递一个更合适的递归机制到我们的 lambda，并直接使用该参数递归，那将更好。这是 y combinator 的基础 -

(define y
  (lambda (f)
    (f (lambda (x)     ; 而不是将 f 应用于自身
         ((y f) x))))) ; 提供一个 lambda，当应用时，递归

下面我们将参数命名为 recur，但你可以随意命名它 -

((y (lambda (recur)            ; (y (lambda (recur) ...))
      (lambda (n)
        (if (zero? n)
            "done"
            (begin
              (printf "~a ...\n" n)
              (recur (sub1 n))))))) ; 将 recur 应用于... 递归!
 5)

5 ...
4 ...
3 ...
2 ...
1 ...
done

在实践中

让我们看一个稍微复杂一点的例子。我们可以将我们的 (y ...) 表达式分配给一个名称 factorial，并使用不同的初始值对 n 调用它。请注意，我们不是用过程的 name 来递归。y-combinator 提供了直接递归的参数 -

(define factorial
  (y (lambda (recur)    ; y 提供 recur
       (lambda (n)
         (if (zero? n)
             1
             (* n (recur (sub1 n))))))))  ; recur!

(factorial 10) ; 初始 n = 10
(factorial 20) ; 初始 n = 20

3628800
2432902008176640000

为了展示计算阶乘的另一种方法，我们可以使用 另一个 柯里化参数来跟踪计算过程中的累加器 -

(define factorial
  ((y (lambda (recur)
        (lambda (acc)     ; 累加器参数
          (lambda (n)
            (if (zero? n)
                acc
                ((recur (* acc n)) (sub1 n))))))) ; recur with two arguments
   1)) ; 初始 acc = 1

(factorial 10) ; 初始 n

<details>
<summary>英文:</summary>

I have a lambda -

```rkt
(lambda (x)
  ...)

But inside the ... expression I would like to call it recursively. I know if I give the lambda a name, I can call it by name, but I want to recur without a name. Let's imagine another lambda that applies its argument to itself -

(lambda (f) (f f))

Now let's apply it to our original lambda -

((lambda (f) (f f))
 (lambda (x) ...))

Now x is a reference to itself! Ok, so how does that enable recursion? x is our lambda, and when applied to itself provides a mechanism for recursion -

((lambda (f) (f f))
 (lambda (x) ;; x *is* this lambda
   (println "infinite recursion happening now...")
   (x x))) ;; apply x to itself to recur

"infinite recursion happening now..."
"infinite recursion happening now..."
"infinite recursion happening now..."
"infinite recursion happening now..."
...
(ad infinitum)

So that's great and all, but how would we stop the infinite recursion? And more importantly, how can we pass arguments along the way?

As we saw (x x) drives the recursion. If we only recur under a condition, we can control when our procedure exits. Let's have our (lambda (x) ...) return another procedure, (lambda (n) ...) instead -

((lambda (f) (f f))
 (lambda (x)
   (lambda (n)
     (if (zero? n)  ; condition
         ...        ; done
         (x x)))))  ; otherwise recur

However instead of immediately recurring (x x) will now return a procedure, (lambda (n) ...), so we can apply it to an argument to pass along a new n value -

((lambda (f) (f f))
 (lambda (x)
   (lambda (n)
     (if (zero? n)
         "done"
         (begin
           (printf "~a ...\n" n)
           ((x x)                 ; (x x) returns λn 
            (sub1 n)))))))        ; updated n

So to recap outer λf applies λx to itself, which now returns λn. Now we apply that to an argument and witness nameless, anonymous procedure recursion -

(((lambda (f) (f f))
  (lambda (x)
    (lambda (n)
      (if (zero? n)
          "done"
          (begin
            (printf "~a ...\n" n)
            ((x x)
             (sub1 n)))))))
 5) ; apply the procedure to 5

5 ...
4 ...
3 ...
2 ...
1 ...
done

u combinator

The combinator we wrote above is known as the u combinator

(define u
  (lambda (f) (f f)))

We can rewrite our program using u below -

((u (lambda (x)            ; (u (lambda (x) ...))
      (lambda (n)
        (if (zero? n)
            "done"
            (begin
              (printf "~a ...\n" n)
              ((u x)                 ; (u x) to recur
               (sub1 n)))))))
 5)

y combinator

The (x x) and (u x) recursion mechanisms are a little weird though. It would be nice if we could pass a more suitable recursion mechanism to our lambda and recur directly using that parameter. This is the basis of the y combinator -

(define y
  (lambda (f)
    (f (lambda (x)     ; rather than applying f to itself
         ((y f) x))))) ; provide a lambda, when applied, recurs

Below we name the parameter recur, but you can call it whatever you want -

((y (lambda (recur)            ; (y (lambda (recur) ...))
      (lambda (n)
        (if (zero? n)
            "done"
            (begin
              (printf "~a ...\n" n)
              (recur (sub1 n))))))) ; apply recur to.. recur!
 5)

5 ...
4 ...
3 ...
2 ...
1 ...
done

in practice

Let's see a slightly more sophisticated example. We can assign our (y ...) expression to a name, factorial, and call it repeatedly with different initial values for n. Note we are not recurring with the procedures name. The y-combinator provides the parameter for direct recursion -

(define factorial
  (y (lambda (recur)    ; y provides recur
       (lambda (n)
         (if (zero? n)
             1
             (* n (recur (sub1 n))))))))  ; recur!

(factorial 10) ; initial n = 10
(factorial 20) ; initial n = 20

3628800
2432902008176640000

To demonstrate another way to compute a factorial, we could use another curried parameter to track an accumulator over the course of the computation -

(define factorial
  ((y (lambda (recur)
        (lambda (acc)     ; accumulator parameter
          (lambda (n)
            (if (zero? n)
                acc
                ((recur (* acc n)) (sub1 n))))))) ; recur with two arguments
   1)) ; initial acc = 1

(factorial 10) ; initial n = 10
(factorial 20) ; initial n = 20

3628800
2432902008176640000

That λrecur.λacc.λn. ... is getting a bit hard to read. We can use curry to convert a multi-parameter procedure to its curried form -

(define factorial
  ((y (curry (lambda (recur acc n) ; simplified
               (if (zero? n)
                   acc
                   ((recur (* acc n)) (sub1 n))))))
   1))

(factorial 10)
(factorial 20)

3628800
2432902008176640000

Similarly, we can improve y to provide a more ergonomic recursion mechanism that accepts multiple arguments -

(define y
  (lambda (f)
    (f (lambda args   ; multiple args
         (apply (y f) args)))))   ; apply (y f) to args

Effortless recursion with multiple arguments -

(define factorial
  ((y (curry (lambda (recur acc n)
               (if (zero? n)
                   acc
                   (recur (* acc n) (sub1 n)))))) ; simplified
   1))

(factorial 10)
(factorial 20)

3628800
2432902008176640000

remove

With these fundamentals in place, we can get to the meat of your question. We will write a remove procedure which accepts an element to remove e, and an input list xs -

(define remove
  (y (curry (lambda (recur e xs)
              (cond ((null? xs)
                     null)
                    ((eq? e (car xs))
                     (recur e (cdr xs)))
                    (else
                     (cons (car xs)
                           (recur e (cdr xs)))))))))

(remove 'q '(a b q c d q e q f q g q q h i q))

'(a b c d e f g h i)

more parameters

There's no limit to the number of parameters your recursive lambda can use. Let's see fibonacci which uses two initial parameters, a = 0 and b = 1 and a third parameter n, to compute the nth term in the famous sequence -

(define fibonacci
  ((y (curry (lambda (recur a b n) ; as number of parameters
               (if (zero? n)
                   a
                   (recur b (+ a b) (sub1 n)))))) ; ergonomic recursion
   0   ; initial a = 0
   1)) ; initial b = 1

The n argument is supplied at the call site -

(fibonacci 10) ; initial n = 10
(fibonacci 100) ; initial n = 100

55
354224848179261915075

going deeper

Did you notice the Y-combinator above uses its own name y in its definition? We can rewrite it using the U-combinator, such that no definition refers to itself by name -

(define u
  (lambda (f) (f f)))

(define y
  (u (lambda (h)   ; now defined in terms of U
       (lambda (f)
         (f (lambda args
              (apply ((u h) f) args))))))) ; no reference to Y

This y works the same as above, but no longer refers to itself by its name. Let's see some more sophisticated functions now. Here's a range function that builds a list from min to max -

(define range
  (y (curry (lambda (recur min max)
              (if (> min max)
                  null
                  (cons min (recur (add1 min) max)))))))

(range 5 10)

'(5 6 7 8 9 10)

Here's a foldr procedure to fold a list from right to left with a user-supplied function f, an initial accumulator init, and an input list, xs -

(define foldr
  (y (curry (lambda (recur f init xs)
              (if (null? xs)
                  init
                  (f (car xs)
                     (recur f init (cdr xs))))))))

(foldr + 0 (range 5 10))

45

We could partially apply foldr with + and 0 to define sum -

(define sum
  (foldr + 0))

(sum (range 5 10))

45

We could define a higher-order map that maps an input list with a user-supplied function f, using foldr behind the scenes -

(define map
  (curry (lambda (f xs)
           (foldr (lambda (x acc) (cons (f x) acc))
                  null
                  xs))))

(map (lambda (x) (* 100 x))
     (range 5 10))

'(500 600 700 800 900 1000)

Finally we can see all of these expressions can be combined. Everything accomplished using nameless recursion!

(sum (map (lambda (x) (* 100 x))
          (range 5 10)))

4500

remarks

It can be challenging to reduce programming concepts to simple forms. To develop the capacity for thinking about programs like this, I strongly suggest the study of lambda calculus. In this tiny model of computation, there are only three expressions to learn -

1. Variables, such as x or y
2. Abstraction, with a single parameter (lambda (z) ...) where ... is a single expression
3. Application, (f w) where f is any lambda and w is any expression

These 3 components make up a universal model of computation that can simulate any Turing machine. Introduced by Alonzo Church in the 1930's, it serves as the theoretical foundation for functional programming style. Languages like Scheme and Racket were heavily influenced and embrace functional disciplines with a passion.

Learning to build things from the smallest, most primitive components can help you establish an insight and appreciation for higher level language features and give you the understanding and confidence necessary to design whatever you can imagine.