recursion - 在 Lisp 中组合列表，只使用 first 和 cons

Question

我正在做一项作业，我需要合并两个列表，但我们只允许使用以下函数:

cons(e,L)
first(L)
rest(L)

几个小时以来，我一直在尝试弄清楚如何仅使用这些函数递归地执行此操作，但我一无所知。我们应该使用类似于这样的符号:

find(L, k) is
    NULL    if L = NULL
or first(L) if first(L) = k
or find(rest(L), k)

有什么建议吗？谢谢!!

Answer 1

如果 combine 意味着附加两个列表，那么尝试下面的伪代码:

append(a,b) =
  if nil(a) then b
  else cons(first(a),append(rest(a),b))