如何使我的排序函数成为尾递归？

Question

这些年来，我一直以命令式进行编码，但现在开始学习函数式，并面临一些将函数转换为尾递归的障碍。

试图修改和添​​加打印以理解代码，但没有任何成果

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]并且上面的代码正在工作，但不知道如何使其成为尾递归。

任何指导都将有所帮助。

Answer 1

在您的实现中，您导航->，然后工作类似于<-的Right Fold。

如果您将List视为调用堆栈，则有f（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))
}