एफपी

Question

के साथ स्कैला में चौड़ाई पहली खोज को कैसे कार्यान्वित करें मैं सोच रहा हूं कि कार्यात्मक प्रोग्रामिंग का उपयोग करके स्केल में Breadth-first search को कैसे कार्यान्वित किया जाए।

def bfs[S](init: S, f: S => Seq[S], finalS: S => Boolean): Option[S] = { 
    val queue = collection.mutable.Queue[S]() 

    queue += init 
    var found: Option[S] = None 

    while (!queue.isEmpty && found.isEmpty) { 
     val next = queue.dequeue() 
     if (finalS(next)) { 
     found = Some(next) 
     } else { 
     f(next).foreach { s => queue += s } 
     } 
    } 
    found 
    } 

हालांकि मैं केवल स्थानीय अस्थिरता (एक var और एक परिवर्तनशील Queue) का उपयोग करें, यह पूरी तरह कार्यात्मक नहीं है:

यहाँ मेरा पहला, अशुद्ध, कोड है।

मैं एक और संस्करण के साथ आते हैं:

case class State[S](q: Queue[S], cur: S) 

    def update[S](f: S => Seq[S])(s: State[S]) : State[S] = { 
    val (i, q2) = s.q.dequeue 
    val q3 = f(i).foldLeft(q2) { case (acc, i) => acc.enqueue(i)} 
    State(q3, i) 
    } 

    def bfs2[S](init: S, f: S => Seq[S], finalS: S => Boolean): Option[S] = { 
    val s = loop(State[S](Queue[S]().enqueue(init), init), update(f) _, (s: State[S]) => s.q.isEmpty || finalS(s.cur)) 
    Some(s.cur) 
    } 

    def loop[A](a: A, f: A => A, cond: A => Boolean) : A = 
    if (cond(a)) a else loop(f(a), f, cond) 

वहाँ दोनों के समाधान के लिए एक बेहतर तरीका है? क्या कुछ बॉयलरप्लेट को हटाने के लिए बिल्लियों/स्कालाज़ का उपयोग करना संभव है?

Answer 1

कार्यात्मक प्रोग्रामिंग के बारे में एक अच्छी बात यह है कि आप खोज डेटा से अपनी डेटा संरचना के ट्रैवर्सल को अलग करने के लिए आलस्य का लाभ उठा सकते हैं। यह बहुत ही पुन: प्रयोज्य, एकल जिम्मेदारी कोड के लिए बनाता है:

import scala.collection.immutable.Queue 

def breadth_first_traverse[Node](node: Node, f: Node => Queue[Node]): Stream[Node] = { 
    def recurse(q: Queue[Node]): Stream[Node] = { 
    if (q.isEmpty) { 
     Stream.Empty 
    } else { 
     val (node, tail) = q.dequeue 
     node #:: recurse(tail ++ f(node)) 
    } 
    } 

    node #:: recurse(Queue.empty ++ f(node)) 
} 

अब आप breadth_first_traverse(root, f) find (_ == 16) द्वारा एक BFS करते हैं या Stream कक्षा में किसी भी अन्य फ़ंक्शन का उपयोग एक आलसी पर उपयोगी तदर्थ "क्वेरी" ऐसा करने के लिए कर सकते हैं चौड़ाई-पहले Stream चपटा अपने पेड़ के

Answer 2

यह untested है, लेकिन मुझे लगता है कि काम करता है:

def bfs[S](init: S, f: S => Seq[S], finalS: S => Boolean): Option[S] = { 
    def bfshelper(q: Seq[S], f: S => Seq[S], finalS: S => Boolean): Option[S] = q match { 
     case Seq()    => None 
     case h +: t if finalS(h) => Some(h) 
     case h +: t    => bfshelper(t ++ f(h), f, finalS) 
    } 
    bfshelper(Seq(init), f, finalS) 
    } 

चाल क्या, जाँच की बात है, और अगर वर्तमान तत्व मिलान नहीं है की एक Seq रखने के लिए है, अपने आप को साथ फोन इस नोड के बच्चों के साथ हमें जांचना पड़ा कि

Answer 3

कार्ल बीलेफेल्ड द्वारा दिए गए उत्तर पर बिल्डिंग, यहां एक और समाधान है।

def bfs[T](s: Stream[T], f: T => Stream[T]): Stream[T] = { 
    if (s.isEmpty) s 
    else s.head #:: bfs(s.tail append f(s.head), f) 
}