scala - 如何使我的排序函数尾递归?
问题描述
这些年来,我一直在使用命令式编码,但现在开始学习函数式风格,并面临将函数转换为尾递归的一些障碍。
尝试修改和添加打印以理解代码但没有任何成果
def sort(compare: (A, A) => Int): MyList[A] = {
def sortHelper(x: A, xs: MyList[A]): MyList[A] = {
if (xs.isEmpty) {
new Cons(x, Empty)
}
else if(compare(x, xs.head) < 0)
{
new Cons(x, xs)
}
else
{
new Cons(xs.head, sortHelper(x, xs.tail))
}
}
sortHelper(h, t.sort(compare))
}
}
val listOfInts = new Cons(1, new Cons(2, new Cons(3, new Cons(4, Empty)
println(listOfInts.sort((x, y) => y - x))
该列表被排序为 [4,3,2,1] 并且上面的代码正在运行,但不知道如何使其成为尾递归。
任何指导都会有所帮助。
@Nigel - 我尝试了你对我当前版本的排序的解决方案并且它有效:
def anotherSort(isLess: (A, A) => Boolean): MyList[A] = {
@tailrec
def sortHelper(workList: MyList[A], sortedList: MyList[A] = Empty): MyList[A] =
if(workList.isEmpty) sortedList
else {
if(sortedList.isEmpty) sortHelper(workList.tail, new Cons(workList.head, Empty))
else if(isLess(workList.head, sortedList.head)) sortHelper(new Cons(workList.head, new Cons(sortedList.head, workList.tail)), sortedList.tail)
else sortHelper(workList.tail, new Cons(workList.head, sortedList))
}
sortHelper(this)
}
谢谢你说清楚。
解决方案
在您的实现中,您导航->
然后<-
进行类似于Right Fold
.
如果您将 List 视为调用堆栈,则您有 f(f(f(f(...)))) ,您首先在其中执行最里面的 f 。这与尾递归相反。
您要做的是展开一层,创建结果并使用列表的其余部分进行递归。
从左到右执行此操作,您的 sortHelper 函数可能应该采用列表的当前工作版本,加上排序版本作为另一个参数。然后,您可以递归地从工作列表中提取一个元素并将其放在排序列表中。如果您遇到当前元素小于排序列表头部的情况,您应该退后推销并将已排序的头部放回工作列表中,然后将头部放回列表中(因为您不不知道递归的时候会不会再遇到这种情况)。
这是答案的冗长版本,让您有机会自己尝试代码。
我已经包含了下面的代码,如果您想自己尝试,请不要看:
import scala.annotation.tailrec
sealed trait MyList[+A] extends Product with Serializable {
val isEmpty: Boolean
def head: A
def tail: MyList[A]
def sort(isLess: (A, A) => Boolean): MyList[A] = {
@tailrec
def inner(working: MyList[A], sorted: MyList[A] = Empty): MyList[A] = working match {
case Empty => sorted
case Cons(h, t) =>
if (sorted.isEmpty) inner(t, Cons(h, Empty))
else if (isLess(h, sorted.head)) inner(Cons(h, Cons(sorted.head, t)), sorted.tail)
else inner(t, Cons(h, sorted))
}
inner(this)
}
}
case object Empty extends MyList[Nothing] {
val isEmpty = true
def head = throw new NotImplementedError("No head on Empty list")
def tail = throw new NotImplementedError("No tail on Empty list")
}
case class Cons[+A](head: A, tail: MyList[A]) extends MyList[A] {
val isEmpty = false
}
object SortTest extends App {
val listOfInts: MyList[Int] = Cons(1, Cons(2, Cons(3, Cons(4, Empty))))
val isLess: (Int, Int) => Boolean = (x, y) => x < y
println(listOfInts.sort(isLess))
}
只是为了好玩,在这里它被调整为使用 Scala 的 List 和 Ordering 类型类:
import scala.annotation.tailrec
import scala.Ordering.Implicits._
object SortTest extends App {
def sort[A: Ordering](lst: List[A]): List[A] = {
@tailrec
def inner(working: List[A], sorted: List[A] = Nil): List[A] = working match {
case Nil => sorted
case h :: t =>
val (w, s) = sorted.headOption.fold((t, h :: Nil)){ sh =>
if (h < sh) (h :: sh :: t, sorted.tail)
else (t, h :: sorted)
}
inner(w, s)
}
inner(lst)
}
val listOfInts: List[Int] = 1 :: 2 :: 3 :: 4 :: Nil
println(sort(listOfInts))
}
推荐阅读
- javascript - 如果一个实体有数组数据,我如何在两个实体中建立关系
- python - 更改 tkinter 菜单的字体
- python - 使用数据框列输入数据的 matplotlib 3D 曲面图
- java - Spring Scoped Prototype bean 实例是相等的
- jquery - 按下子按钮(具有不同功能)时,卡片会翻转。如何停止传播到父级?
- sql - Oracle中的多行插入查询(从一张表中选择多行并插入到另一张表中
- mysql - 如果用户具有普通/超级用户权限,MySQL 将捕获用户登录信息
- html - 使用 flex 的输入顶部的标签
- discord.js - 如果允许某个变量,有没有办法覆盖“列入黑名单”的单词?
- google-bigquery - 我应该将类型 2 历史记录应用于具有重复键的表吗?