Как сделать мою функцию сортировки хвостовой рекурсивной? - PullRequest
Новая
       64

Как сделать мою функцию сортировки хвостовой рекурсивной?

4 голосов
/ 26 сентября 2019

Все эти годы я занимался программированием в императивном стиле, но сейчас начал изучать функциональный стиль и столкнулся с некоторыми препятствиями, переводя функцию в хвостовую рекурсию.

Попытка изменить и добавить распечатки, чтобы понять код, но ничего полезного 

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], и приведенный выше код работаетно не знаю, как сделать это как хвост-рекурсивный.

Любое руководство будет полезным.

@ Найджел - я попробовал ваше решение для моей текущей версии сортировки, и оно сработало: 

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)
  }

Спасибо за разъяснение.

1 Ответ

1 голос
/ 27 сентября 2019

В вашей реализации вы перемещаетесь по ->, а затем работаете <-, что похоже на 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's 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))
}
...