Come posso approssimare Python o l'operatore per il confronto dei set in Scala?

Question

Dopo aver ascoltato l'ultimo podcast di Stack Overflow, il compattore Python di Peter Norvig mi ha incuriosito, così ho deciso di implementarlo in Scala se potessi esprimerlo bene nell'idioma Scala funzionale, e anche di vedere quante righe di codice Prenderei.

Ecco l'intero problema. (Non confrontiamo ancora le righe di codice.)

(Due note: puoi eseguirlo nell'interprete di Scala, se lo desideri.Se hai bisogno di una copia di big.txt, o dell'intero progetto, è on GitHub.)

import scala.io.Source 

val alphabet = "abcdefghijklmnopqrstuvwxyz" 

def train(text:String) = { 
    "[a-z]+".r.findAllIn(text).foldLeft(Map[String, Int]() withDefaultValue 1) 
    {(a, b) => a(b) = a(b) + 1} 
} 

val NWORDS = train(Source.fromFile("big.txt").getLines.mkString.toLowerCase) 

def known(words:Set[String]) = 
    {Set.empty ++ (for(w <- words if NWORDS contains w) yield w)} 

def edits1(word:String) = { 
    Set.empty ++ 
    (for (i <- 0 until word.length) // Deletes 
    yield (word take i) + (word drop (i + 1))) ++ 
    (for (i <- 0 until word.length - 1) // Transposes 
    yield (word take i) + word(i + 1) + word(i) + (word drop (i + 2))) ++ 
    (for (i <- 0 until word.length; j <- alphabet) // Replaces 
    yield (word take i) + j + (word drop (i+1))) ++ 
    (for (i <- 0 until word.length; j <- alphabet) // Inserts 
    yield (word take i) + j + (word drop i)) 
} 

def known_edits2(word:String) = {Set.empty ++ (for (e1 <- edits1(word); 
    e2 <- edits1(e1) if NWORDS contains e2) yield e2)} 

def correct(word:String) = { 
    val options = Seq(() => known(Set(word)),() => known(edits1(word)), 
    () => known_edits2(word),() => Set(word)) 
    val candidates = options.foldLeft(Set[String]()) 
    {(a, b) => if (a.isEmpty) b() else a} 
    candidates.foldLeft("") {(a, b) => if (NWORDS(a) > NWORDS(b)) a else b} 
} 

In particolare, mi chiedo se c'è qualcosa più pulito che posso fare con la funzione correct. Nel Python originale, l'implementazione è un po 'più pulito:

def correct(word): 
    candidates = known([word]) or known(edits1(word)) or 
     known_edits2(word) or [word] 
    return max(candidates, key=NWORDS.get) 

A quanto pare in Python, un insieme vuoto valuterà a Boolean False, in modo che solo il primo dei candidati per restituire un insieme non vuoto sarà valutata, salvataggio di chiamate potenzialmente costose su edits1 e known_edits2.

L'unica soluzione che otterrei è la versione che vedete qui, dove vengono chiamate le funzioni anonime Seq fino a quando non viene restituito uno Set non vuoto, che è garantito l'ultimo.

Testate Scala così esperte, c'è un modo più sintatticamente conciso o migliore per farlo? Grazie in anticipo!

Answer 1

Gli iteratori sono anche pigri (anche se non molto funzionali poiché si può solo scorrere su di loro una volta sola.) Quindi, si potrebbe fare in questo modo:

def correct(word: String) = { 
    val sets = List[String => Set[String]](
     x => known(Set(x)), x => known(edits1(x)), known_edits2 
    ).elements.map(_(word)) 

    sets find { !_.isEmpty } match { 
     case Some(candidates: Set[String]) => candidates.reduceLeft { (res, n) => if (NWORDS(res) > NWORDS(n)) res else n } 
     case None => word 
    } 
    } 

Come bonus, metodo find di Iterator() non forza la valutazione dell'elemento successivo.

Answer 2

Questo lavoro dovrebbe funzionare? La sintassi _ è una funzione parzialmente applicata e utilizzando un (pigro) Stream, mi assicuro che le valutazioni nello reduceLeft (che ritengo sia più appropriato di foldLeft qui) avvengano solo come richiesto!

def correct(word:String) = { 
    Stream(known(Set(word)) _, 
     known(edits1(word)) _, 
     known_edits2(word) _, 
     Set(word) _ 
     ).find(!_().isEmpty) match { 
    case Some(candidates) => 
     candidates.reduceLeft {(res, n) => if (NWORDS(res) > NWORDS(n)) res else n} 
    case _ => "" //or some other value 

}

Probabilmente ho fatto alcuni errori di sintassi qui, ma penso che l'approccio Stream è uno valido

Answer 3

Io non so perché si sta tentando di utilizzare la valutazione pigra per known anziché utilizzare semplicemente un flusso come illustrato in oxbow_lakes. Un modo migliore di fare quello che ha fatto:

def correct(word: String) = { 
    import Stream._ 

    val str = cons(known(Set(word)), 
      cons(known(edits1(word)), 
      cons(known_edits2(word), 
      cons(Set(word), empty)))) 

    str find { !_.isEmpty } match { 
    case Some(candidates) => 
     candidates.foldLeft(Set[String]()) { (res, n) => 
     if (NWORDS(res) > NWORDS(n)) res else n 
     } 

    case None => Set() 
    } 
} 

Il sfrutta il fatto che Stream.cons è pigro già e quindi non abbiamo bisogno di avvolgere tutto in un thunk.

Se siete veramente in vena di sintassi bello però, siamo in grado di aggiungere un po 'di zucchero sintattico per tutte quelle conses:

implicit def streamSyntax[A](tail: =>Stream[A]) = new { 
    def #::(hd: A) = Stream.cons(hd, tail) 
} 

Ora il nostro precedentemente brutta str definizione rientra nella seguente:

def correct(word: String) = { 
    val str = known(Set(word)) #:: known(edits1(word)) #:: 
      known_edits2(word) #:: Set(word) #:: Stream.empty 

    ... 
} 

Answer 4

Scala 2.7-ready (inclusa la performance implicita work-around):

class Or[A](one: Set[A]) { 
    def or(other: => Set[A]): Set[A] = if (one.isEmpty) other else one 
} 

implicit def toOr[A](one: Set[A]) = new Or(one) 

def correct(word: String) = { 
    candidates = known(Set(word)) or known(edits1(word)) or known_edits2(word) or Set(word) 
    candidates.foldLeft("") {(a, b) => if (NWORDS(a) > NWORDS(b)) a else b} 
} 

Scala 2.8-bontà:

implicit def toOr[A](one: Set[A]) = new AnyRef { 
    def or(other: => Set[A]): Set[A] = if (one.isEmpty) other else one 
} 

def correct(word: String) = { 
    candidates = known(Set(word)) or known(edits1(word)) or known_edits2(word) or Set(word) 
    candidates.max(Ordering.fromLessThan[String](NWORDS(_) < NWORDS(_))) 
} 

Detto questo, ho praticamente upvoted tutti gli altri. Non ho considerato un Stream.

EDIT

Sembra Ordering.fromLessThan può portare a due volte i necessari confronti. Ecco una versione alternativa a quella linea:

candidates.max(new Ordering[String] { def compare(x: String, y: String) = NWORDS(x) - NWORDS(y) }) 

Answer 5

Ho cercato di attuare un short Scala implementation of the spelling corrector. Sono 15 linee senza importazioni. La sostituzione più breve per Python di o è semplice chiamata dal parametro nome:

def or[T](candidates : Seq[T], other : => Seq[T]) = if(candidates.isEmpty) other else candidates 
def candidates(word: String) = or(known(List(word)), or(known(edits1(word)), known(edits2(word)))) 

In uno scenario del mondo reale userei la conversione implicita Daniel proposto.