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

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 []

*** 开始 UPDATES/CHANGES ***

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 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 的定义非常相似。唯一的区别是使用 [] 代替 PEANUT 和 :: 代替 BUTTER，:: 也是中缀运算符。

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

将[]替换为PEANUT。
将a :: b替换为BUTTER (a, b)。

仅此而已。因此，我不会只给你答案，而是让你自己使用这些规则推导出答案。祝你好运！

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

Understanding tail recursion with stated data types

recursion

f#

algebraic-data-types