了解具有指定数据类型的尾递归

Question

所以我对递归的理解相对较好，但是在 F# 中能够创建自己的数据类型集，我不明白如何编写一个函数来引用该特定场景。谢谢你的帮助

type 'element mylist = PEANUT | BUTTER of 'element * 'element mylist

let exampleList = BUTTER (1, BUTTER (2, BUTTER (3, PEANUT)))

试图编写一个反转这个列表的尾递归函数？

这是我传统的写法

let rec helper a b =
      match a with
        | [] -> b
        | h::t -> helper t (h::b)

    let rev L = helper L []

现在这是我一直在尝试的：

let rec tailrevMylist a L =
      match a with
      | [] -> []
      | PEANUT::t -> tailrevMylist t (BUTTER::L)
 

    let revMylist L =
      tailrevMylist  L []

*** 开始更新/更改 ***

let rec tailrevMylist a b =
      match a with
      | PEANUT -> b
      | h::t -> tailrevMylist BUTTER (a, b)
 

    let revMylist L =
      tailrevMylist  L []

仍然得到不正确的类型——试图使用 CONS 而不是 h 但不能因为它期望联合。*** 结束更新 ***

但是，当我尝试运行时，revMylist exmapleList由于函数期望 a'a mylist list但int mylist在我的测试中输入了类型，因此出现错误。我需要让函数期待一个int mylist.

*** 解决方案 ***

let rec tailrevMyList a b  =
      match a with
        | PEANUT -> b
        | BUTTER (head, tail) -> (tailrevMyList tail (BUTTER (head, b)))
 

    let revMylist L = tailrevMyList L PEANUT

Answer 1

列表的定义本质上是：

type 'a list = [] | :: of 'a * 'a list

您可能会注意到它与您对mylist. 唯一的区别是使用[]in place ofPEANUT和::in place of BUTTER，同时::也是一个中缀运算符。

您可能还会注意到，这意味着您正在以毫无意义的方式混合list和mylist构造函数。因此，与其尝试修复您当前的实现，我只会告诉您如何通过应用一些非常简单的规则来机械地转换您的helper函数以供使用mylist：

1. 替换[]为PEANUT。
2. 替换a :: b为BUTTER (a, b)。

这就是它的全部内容。因此，我不会只给您答案，而是让您自己使用这些规则来推导出答案。祝你好运！