Powtarzające się wywołanie funkcji, dopóki nie zwróci żadnej Brak

Question

Często napotykam wzorzec, więc zastanawiałem się, czy w bibliotece Scala jest jakaś wygodna metoda.

Niech to będzie funkcja f: A => Option[B]. Chciałbym wykonać powtarzające się wywołanie do f zaczynając od x, f(f(f(x).get).get...), aż f zwraca None i zachować ostatnią wartość inną niż None.

pisałem implementację dla tego:

@tailrec 
def recurrentCallUntilNone[B](f: B => Option[B], x: B): B = f(x) match { 
    case Some(y) => recurrentCallUntilNone(f, y) 
    case None => x 
} 

Czy to już wdrożony w bibliotece standardowej?

Przykład użycia może dotyczyć listy (Zipper), która zachowuje aktualną pozycję. Wywołanie: next, None jest zwracana, jeśli nie ma elementów po bieżącej pozycji lub Option dla tej samej listy, ale z aktualną pozycją zwiększaną. Za pomocą powyższej metody można skonstruować metodę, która szuka listy do końca.

Answer 1

Co robisz wygląda bardzo specyficznego rodzaju trampoline. Bardziej ogólny przypadek używa funkcji owiniętych klasami przypadków zamiast Option i obsługuje różne typy argumentów i zwracanych.

Jak zauważa Calin-Andrei, trampoliny są dostępne w standardowej bibliotece przy użyciu TailCalls object.

Od pierwszego linku:

def even2(n: Int): Bounce[Boolean] = { 
    if (n == 0) Done(true) 
    else Call(() => odd2(n - 1)) 
} 
def odd2(n: Int): Bounce[Boolean] = { 
    if (n == 0) Done(false) 
    else Call(() => even2(n - 1)) 
} 
trampoline(even2(9999)) 

sealed trait Bounce[A] 
case class Done[A](result: A) extends Bounce[A] 
case class Call[A](thunk:() => Bounce[A]) extends Bounce[A] 

def trampoline[A](bounce: Bounce[A]): A = bounce match { 
    case Call(thunk) => trampoline(thunk()) 
    case Done(x) => x 
} 

teraz z biblioteki standardowej

import scala.util.control.TailCalls._ 

def even2(n: Int): TailRec[Boolean] = { 
    if (n == 0) done(true) 
    else tailcall(odd2(n - 1)) 
} 
def odd2(n: Int): TailRec[Boolean] = { 
    if (n == 0) done(false) 
    else tailcall(even2(n - 1)) 
} 
even2(9999).result 

Answer 2

W przypadku konkursu piękności można zbudować funkcję, która przekształca istniejącą w potwora, o którym mówiliście za pomocą curry.

def composeUntilTheEnd[B](f: Option[B] => Option[B])(x: Option[B]): Option[B] = 
     if (f(x) != None) composeUntilTheEnd(f)(f(x)) 
     else x 

def ff = composeUntilTheEnd((x:Option[Int]) => x)_ 

Teraz nazywając ff uzyskać zamierzone zachowanie.

Answer 3

Jeśli chcesz, możesz utworzyć parę z opcjami, a następnie użyć funkcji strumienia, aby uzyskać ostatni zdefiniowany element. (Czy raczej ostatnio zdefiniowany elementu przed elementem nieokreślonej)

def options[B](f: B => Option[B], initialValue: Option[B]): Stream[Option[B]] = { 
    initialValue #:: options(f, initialValue.map(f(_)).flatten) 
} 

options.takeWhile(_.isDefined).last 

Answer 4

Jak o:

Stream.iterate(Some(x)) { x => x.flatMap(f _) }.takeWhile { _.isDefined }.last 

UPDATE

Albo nawet neater IMHO (tylko pojedynczy przechodzenie):

val result = { 
    val xs = Stream.iterate(Some(x)) { x => x.flatMap(f _) } 
    (xs zip xs.tail) collectFirst { 
    case (Some(x), None) => x 
    } get 
} 

Należy pamiętać, że jest to bezpieczne, aby zadzwonić collectFirst ponieważ nie możemy zacząć None (inaczej pętla nieskończona byłoby to możliwe).