꼬리 재귀 구현 내가, 기능 방식으로 그들을 <code>partition</code> 인 중 하나를 스칼라의 목록 방법의 몇 가지를 구현하기 위해 노력했습니다 운동 목적

Question

. 다음 서명을 가정합니다

def partition[T](l: List[T], f: T => Boolean): (List[T], List[T]) 

그것은 두리스트로 구성된 튜플을 반환 - 첫 번째는 통과 조건 f 및 다른 모든 요소를 ​​포함하는 다른 하나를 충족 l의 모든 요소가 포함되어 있습니다. 이 스택 오버플로 질문 (Can all recursive functions be re-written as tail-recursions?)에서

def partition[T](l: List[T], f: T => Boolean): (List[T], List[T]) = { 
    l match { 
     case Nil => (Nil, Nil) 
     case head :: rest => { 
     val (left, right) = partition(rest, f) 
     if (f(head)) 
      (head :: left, right) 
     else 
      (left, head :: right) 
     } 
    } 
    } 

그것이 누적 어떤 경우에 사용될 수 있음을 분명히한다 :

나는 불행하게도 꼬리 재귀되지 않습니다 재귀 솔루션을 함께했다. 주어진 목록에서 나는 역순으로 최종 목록을 반환 할 것이므로 이것이 불가능하다고 주장 할 것입니다.

당신은 나에게 꼬리 재귀 솔루션을 전해 주 시겠어요? 어쩌면 연속 통과 (나는 그것이 어떻게 작동하고 어떻게 적용될 수 있는지 이해하지 못했다)일까요?

Answer 1

당신은 유지할 수 있습니다 누적 계산기로 튜플을 반환하고 반환하기 전에 목록을 반대로해야합니다.

def partition[T](l: List[T])(f: T => Boolean): (List[T], List[T]) = { 
    @tailrec 
    def partitionInternal(l: List[T])(acc: (List[T], List[T])): (List[T], List[T]) = { 
    l match { 
     case Nil => acc 
     case head :: tail => 
     if (f(head)) partitionInternal(tail)(head :: acc._1, acc._2) 
     else partitionInternal(tail)(acc._1, head :: acc._2) 
    } 
    } 

    val (lf, r) = partitionInternal(l)((List.empty[T], List.empty[T])) 
    (lf.reverse, r.reverse) 
} 

대신 (::) 앞에 추가의 (:+)을 추가 할 수 있지만, 당신은 모든 항목에 대해 O (N)의 가격을 지불합니다.

또 다른 아이디어는 List[T] 대신 ListBuffer[T]을 사용하여 일정 시간 추가가있는 내부 재귀 구현에 사용하는 것입니다. Additionaly

def partition[T](l: List[T])(f: T => Boolean): (List[T], List[T]) = { 
    @tailrec 
    def partitionInternal(l: List[T])(acc: (ListBuffer[T], ListBuffer[T])): (ListBuffer[T], ListBuffer[T]) = { 
    l match { 
     case Nil => acc 
     case head :: tail => 
     val (leftAcc, rightAcc) = acc 
     if (f(head)) partitionInternal(tail)((leftAcc += head, rightAcc)) 
     else partitionInternal(tail)((leftAcc, rightAcc += head)) 
    } 
    } 

    val (lf, r) = partitionInternal(l)((ListBuffer.empty[T], ListBuffer.empty[T])) 
    (lf.toList, r.toList) 
} 

통지 나는 List[T]에 대한 별도의 인수 목록 및 T => Boolean에서 함수를 만들 : 당신이 할 필요가 마지막에 호출 .toList입니다. 이는 형식 추론이 매개 변수 목록간에 흐르기 때문에 컴파일러가 메서드를 적용 할 때 올바른 형식 인수를 유추하는 데 도움이됩니다.

Answer 2

는 두 축전지, left에 대한 하나 right 하나를 유지해야합니다. 그것을 사용

def partition[T](l: List[T], f: T => Boolean): (List[T], List[T]) = { 
    @annotation.tailrec 
    def aux(tl: List[T], left: List[T], right: List[T]): (List[T], List[T]) = tl match { 
    case Nil => (left.reverse, right.reverse) 
    case head :: rest => { 
     if (f(head)) 
     aux(rest, head :: left, right) 
     else 
     aux(rest, left, head :: right) 
    } 
    } 

    aux(l, List(), List()) 
} 

---

: 당신이 입력 목록을 겪고을 완료하면, 단순히 두 축 압기 (원래 순서로 돌아 가야을 반전)을 반환

scala> def partition[T](l: List[T], f: T => Boolean): (List[T], List[T]) = { 
    | @annotation.tailrec 
    | def aux(tl: List[T], left: List[T], right: List[T]): (List[T], List[T]) = tl match { 
    |  case Nil => (left.reverse, right.reverse) 
    |  case head :: rest => { 
    |  if (f(head)) 
    |   aux(rest, head :: left, right) 
    |  else 
    |   aux(rest, left, head :: right) 
    |  } 
    | } 
    | 
    | aux(l, List(), List()) 
    | } 
partition: [T](l: List[T], f: T => Boolean)(List[T], List[T]) 

scala> partition(List(1, 2, 3, 4, 5), (i: Int) => i%2 == 0) 
res1: (List[Int], List[Int]) = (List(2, 4),List(1, 3, 5))