重構具有多個出口的Scala函數的建議

Question

我已經寫了一個應用程序，並且有一段我不喜歡的代碼，雖然它工作正常。如何重新實現我的search(...)以實現功能或根據Scala習慣用法？而且，在這種情況下，我如何最好地重構我的代碼以便用不可變列表替換Buffer？

順便說一句，我沒有包含函數eliminate(...)的實現。不過，它返回Map[Int, List[Int]]

謝謝。

def search(estimates : Map[Int, List[Int]]) : Map[Int, List[Int]] = { 
    if (estimates.forall{e => e._2.size == 1}) { 
     return estimates 
    } else if (estimates.exists(e => e._2.isEmpty)) { 
     Map.empty 
    } else { 
     val sortedEstimates = estimates.toList.sortBy{_._2.size} 
     val (pos, numbers) = sortedEstimates.find(_._2.size > 1).get 
     val numbersBuffer = numbers.toBuffer // find a way to use immutable collection 
     while (!numbersBuffer.isEmpty) { 
     val head = numbersBuffer.remove(0) 
     val result = search(eliminate(estimates.updated(pos, List(head)), pos, head)) 
     if (result != Map.empty) return result 
     } 
     Map.empty 
    } 
    } 

def eliminate(estimates : Map[Int, List[Int]], position : Int, num : Int) : Map[Int, List[Int]] = {...} 

Answer 1

首先，讓我們的名字表示類型爲清楚：

type Estimates = Map[Int, List[Int]] 
type Entry = (Int, List[Int]) 

因爲我們需要通過列表大小來比較條目，所以有一個明確命名的比較器很有用：

val byNumsSize: Ordering[Entry] = Ordering.by(_._2.size); 

稍後，如果列表爲空，我們需要根據byNumsSize或None找到最少的列表條目。這可以使用reduceOption(byNumsSize.min)完成，參見this answer。

讓我們專注於內部循環。這個想法是找到eliminate內部調用成功的第一個元素。這可以通過lazy views，映射整個集合和第一個可接受的結果來完成。它總是有用的一段代碼分成幾個小功能，讓我們將它表示爲

def eliminate(estimates : Estimates, entry: Entry) : Option[Estimates] = { 
    val pos = entry._1; 
    entry._2 
    .view // process the sequence lazily to run each step only when needed 
    .map(n => search(eliminate(estimates.updated(pos, List(n)), pos, n))) 
    .collectFirst({ case es if !es.isEmpty => es }) // better/safer than != Map.empty 
} 

現在我們已經爲search功能構建塊。我們可以通過遍歷它來找到至少一個，而不是整理列表並選擇最小值（即O（n log n））。首先，我們篩選列表大小爲1的所有條目，然後按大小查看最小值。如果最小值有一個非空列表，我們嘗試使用前一個函數處理它。如果最低有一個空的列表，我們失敗了。在這種情況下，我們返回空地圖。

編輯：比較尺寸時我犯了一個錯誤（_._2.size與_._2）。爲了避免這樣的錯誤，我會更好地定義一個單獨的功能吧：

def entrySize(e: Entry): Int = e._2.size 

如果所有條目具有尺寸1的列表，我們跳過處理並立即返回原來的地圖：

def search(estimates : Estimates) : Estimates = 
    estimates 
    .toSeq 
    .filter(entrySize(_) != 1) 
    // Find the minimum by size not equal to 1, if there is one: 
    // see https://stackoverflow.com/a/10922659/1333025 
    .reduceOption[Entry](byNumsSize.min) 
    .map(entry => { 
     if (entrySize(entry) > 1) 
      eliminate(estimates, entry) 
     else 
      None 
     }.getOrElse(Map.empty)) 
    .getOrElse(estimates); // all sizes are equal to 1 

我不確定這個解決方案是否會爲您更容易理解。但它既不使用任何可變狀態，也不使用方法，它只對集合和Option s進行操作。

（請注意，我沒有檢查我的代碼工作完全是你的，我只嘗試進行編譯。）

Answer 2

這似乎好一點，但我還是不喜歡所有的if的：

def search(estimates: Map[Int, List[Int]]): Map[Int, List[Int]] = { 
    if (estimates.values.forall(_.size == 1)) { 
     estimates 
    } else if (estimates.values.exists(_.isEmpty)) { 
     Map.empty 
    } else { 
     estimates 
     .toList 
     .sortBy(_._2.size) 
     .find(_._2.size > 1) 
     .map({ 
     case (pos, numbers) => { 
      numbers.foldLeft(Map.empty[Int, List[Int]])((acc, i) => { 
      if (acc.isEmpty) { 
       search(eliminate(estimates.updated(pos, List(i)), pos, i)) 
      } else { 
       acc 
      } 
      }) 
     } 
     }).getOrElse(Map.empty) 
    } 
    }