Phá vỡ hoặc shortcircuit một lần trong Scala

Question

Tôi đã viết một tìm kiếm theo chiều sâu đơn giản trong Scala với một hàm đệ quy như thế:

search(labyrinth, path, goal) 

nơi mê cung là một đặc điểm kỹ thuật của vấn đề (như biểu đồ hoặc bất cứ điều gì), đường dẫn là một danh sách giữ đường dẫn được thực hiện cho đến nay và mục tiêu là một đặc tả của trạng thái mục tiêu. Hàm trả về một đường dẫn tới mục tiêu dưới dạng một Danh sách và Nil nếu không tìm thấy đường dẫn nào.

Hàm mở rộng, ví dụ: tìm thấy tất cả các nút tiếp theo phù hợp (ứng cử viên) và sau đó phải gọi đệ quy gọi chính nó.

Tôi làm điều này bằng

candidates.foldLeft(Nil){ 
    (solution, next) => 
    if(solution == Nil) 
     search(labyrinth, next :: path, goal) 
    else 
     solution 
} 

Xin lưu ý rằng tôi đã bỏ qua một số chi tiết unescessary. Tất cả mọi thứ đang làm việc tốt cho đến nay. Nhưng khi một giải pháp được tìm thấy bên trong cuộc gọi foldLeft, giải pháp này sẽ được sao chép đơn giản bởi phần khác của câu lệnh if. Có cách nào để tránh điều này bằng cách phá vỡ foldLeft hoặc có thể bằng cách sử dụng một chức năng khác thay vì foldLeft? Trên thực tế tôi có thể có thể viết một phiên bản của foldLeft mà phá vỡ một lần "không Nil" được trả lại bản thân mình. Nhưng có một bên trong API?

Answer 1

Tôi không chắc tôi hiểu mong muốn rút ngắn vòng lặp. Có tốn kém để lặp lại thông qua các ứng viên không? Danh sách ứng viên có tiềm năng lớn không?

Có lẽ bạn có thể sử dụng "tìm" phương pháp:

candidates.find { c => 
    Nil != search(labyrinth, c :: path, goal) 
} match { 
    case Some(c) => c :: path 
    case None => Nil 
} 

Nếu độ sâu tiềm năng của không gian tìm kiếm lớn, bạn có thể tràn ngăn xếp của bạn (phù hợp, được đặt tên trang web này). Nhưng, đó là một chủ đề cho bài đăng khác.

Đối với tiếng cười khúc khích, dưới đây là triển khai thực thi có thể chạy được. Tôi đã phải giới thiệu một biến có thể thay đổi cục bộ (fullPath) phần lớn là do lười biếng, nhưng tôi chắc chắn bạn có thể loại bỏ chúng.

object App extends Application { 

    // This impl searches for a specific factor in a large int 
    type SolutionNode = Int 
    case class SearchDomain(number: Int) { 
     def childNodes(l: List[Int]): List[Int] = { 
      val num = if (l.isEmpty) number else l.head 
      if (num > 2) { 
       (2 to (num - 1)) find { 
        n => (num % n)==0 
       } match { 
        case Some(i) => List(i, num/i) 
        case None => List() 
       } 
      } 
      else List() 
     } 
    } 
    type DesiredResult = Int 


    def search (labyrinth: SearchDomain, path: List[SolutionNode], goal: DesiredResult): List[SolutionNode] = { 

     if (!path.isEmpty && path.head == goal) return path 
     if (path.isEmpty) return search(labyrinth, List(labyrinth.number), goal) 

     val candidates: List[SolutionNode] = labyrinth.childNodes(path) 
     var fullPath: List[SolutionNode] = List() 
     candidates.find { c => 
      fullPath = search(labyrinth, c :: path, goal) 
      !fullPath.isEmpty 
     } match { 
      case Some(c) => fullPath 
      case None => Nil 
     } 
    } 

    // Is 5 a factor of 800000000? 
    val res = search(SearchDomain(800000000), Nil, 5) 
    println(res) 

} 

Answer 2

Tôi thích giải pháp Mitch Blevins vì đây là giải pháp hoàn hảo cho thuật toán của bạn. Bạn có thể quan tâm đến my own solution đến một vấn đề khác về mê cung.