时间戳

首页 > 解决方案 > 在 f# 中反转链表数据类型的顺序

f# - 在 f# 中反转链表数据类型的顺序

问题描述

我必须颠倒使用以下数据类型的链表的顺序：

type IntList =
  | Nil
  | Cons of int * IntList

我曾尝试使用单独的“附加”方法，但我想知道一种使用单个函数的方法

let rec append num lst =
  match lst with
  | Nil -> Con (num,Nil)
  | Cons (hd,tl) -> L (hd ,append num tl)

let rec reverse lst = 
  match lst with 
  | Nil -> Nil
  | Cons (hd,tl) -> append hd (reverse tl)

标签： f#

解决方案

通过使用累加器变量，您可以在一个函数中使用它。当您递归到列表的末尾时，您什么都不做，而是保留一个变量，当您从递归返回到列表的开头时，该变量将存储结果。

当您到达列表末尾时，您只需返回最初是一个空列表的 acuumulator，然后将所有元素添加到其中，同时返回。

由于您将累加器作为递归函数参数，因此最好将其包装在一个除了提供累加器初始值之外什么都不做的函数中。

type IntList =
  | Nil
  | Cons of int * IntList 


let reverse lst = 
  let rec reverseHelper lst acc =
      match lst with 
      | Nil -> acc
      | Cons (hd,tl) -> reverseHelper tl (Cons (hd, acc))
  reverseHelper lst Nil

推荐阅读