CODEWITHSUNDEEP
algorithmf#breadth-first-search
Yabert Yanuar
Yabert Yanuar

Reputation: 1027

Breadth-first Search in F# (BFS)

I want to implement search using BFS. The Algorithm say that i must use a queue to get FIFO effect. I read Chris Okasaki's Purely Functional Data Structures book and found how to make a queue (i wrote using F#) :

type 'a queue = 'a list * 'a list
let emtpy = [],[]
let isEmpty = function
    | [],_ -> true
    | _ -> false

let checkf = function
    | [],r -> List.rev r,[]
    | q -> q

let snoc (f,r) x = checkf (f,x :: r)

let head = function
    | ([],_) -> failwith "EMPTY"
    | (x::f,r) -> x

let tail = function
    | ([],_) -> failwith "EMPTY"
    | (x::f,r) -> checkf (f,r)

anyone know how to implement this to BFS?

and i have this code to make a tree from a list:

let data = [4;3;8;7;10;1;9;6;5;0;2]

type Tree<'a> = 
    | Node of Tree<'a> * 'a * Tree<'a>
    | Leaf

let rec insert tree element = 
    match element,tree with
    | x,Leaf        -> Node(Leaf,x,Leaf)
    | x,Node(l,y,r) when x <= y -> Node((insert l x),y,r)
    | x,Node(l,y,r) when x > y -> Node(l,y,(insert r x))
    | _ -> Leaf

let makeTree = List.fold insert Leaf data

(want to combine these two codes)

Upvotes: 3

Views: 3079

Answers (2)

Baine Wedlock
Baine Wedlock

Reputation: 71

Might still be useful 11 years later?

BFS in F# is not hard: Instead of a while loop you can use recursion to keep it mutable-free.

I enqueue each node with its trace so we can calculate the solution path.

let data = [4;3;8;7;10;1;9;6;5;0;2]

type Tree<'a> = 
    | Node of Tree<'a> * 'a * Tree<'a>
    | Leaf

let rec insert tree element = 
    match element,tree with
    | x,Leaf        -> Node(Leaf,x,Leaf)
    | x,Node(l,y,r) when x <= y -> Node((insert l x),y,r)
    | x,Node(l,y,r) when x > y -> Node(l,y,(insert r x))
    | _ -> Leaf

let tree = List.fold insert Leaf data

// BFS
let rec find goal queue =
  match queue with
  | []                          -> None
  | (Leaf, _)::tail             -> find goal tail
  | (Node (l,y,r), trace)::tail ->
    if y = goal then Some (List.rev (y::trace)) else
    find goal (tail @ [ l, y::trace; r, y::trace ])

// for example, to find the 5 in your tree
find 5 [tree, []]
|> printfn "%A"

// it will return: Some [4; 8; 7; 6; 5]
// because your tree looks like this:
//         4
//      /     \
//     3       8
//    /       / \
//   1       7   10
//  / \     /   /
// 0   2   6   9
//        /
//       5

Upvotes: 1

Rafe
Rafe

Reputation: 5295

the BFS algorithm is this:

Initialise the search by placing the starting vertex in the queue.
While the queue is not empty.
  Remove the front vertex from the queue.
  If this is a solution then we're finished -- report success.
  Otherwise, compute the immediate children of this vertex and enqueue them.
Otherwise we have exhausted the queue and found no solution -- report failure.

My F# syntax is a bit wobbly, but here's how I'd sketch out the solution:

bfs start = bfsLoop ([start], [])

bfsLoop q0 =
  if   isEmpty q0
  then failWith "No solution"
  else v = head q0
       if   isSolution v
       then v
       else q1 = tail q0
            vs = childrenOf v
            q = foldl snoc vs q1
            bfsLoop q

Hope this helps.

Upvotes: 4

Related Questions