I'm just getting my feet wet with F#, by implementing some simple algorithms. First up: Djikstras shortest path.
There is one piece I've written in this code which confuses me as to why it works: the
contains function. As I understand it,
List.isEmpty returns true when a list is empty; but in this case, I would want to see the opposite of that. However,
not(List.isEmpty) appeared to give the opposite of what I was expecting: it still returned true on a list being empty. Why is this the case? Or am I just missing something obvious?
As for the full code listing: have I done anything massively wrong?
open System; open System.Collections; open System.Collections.Generic; open System.IO; type Node(id: int, neighbours:list<(int*int)>) = let mutable _ID = id let mutable _neighbours:list<(int * int)> = neighbours member this.ID with get() = _ID and set(value) = _ID <- value member this.AddNeighbour(id:int, distance:int) = let t:(int*int) = (id, distance) _neighbours <- _neighbours @ [t] member this.Neighbours with get() = _neighbours and set(value) = _neighbours <- value; let nodes:list<Node> = [new Node(1, [(2, 3); (3, 3); (4, 1)]); new Node(2, [(3, 1)]); new Node(3, [(1, 3); (2, 1); (4, 10)]); new Node(4, [(1, 1); (3, 10)]) ]; let rec remove_first pred lst = match lst with | h::t when pred h -> t | h::t -> h::remove_first pred t | _ -> ; let contains (item:'a) (lst:list<'a>) : bool = let filtered = List.filter (fun I -> I = item) lst; List.isEmpty(filtered); let rec Traverse (data:list<Node>, start:int, visited:list<int>):list<int> = let startNode = List.find (fun (E:Node) -> E.ID = start) data //Get the starting node let newData = remove_first (fun (E:Node) -> E.ID = startNode.ID) data //Get the new data by removing the start node from the current data let newVisited = visited@[startNode.ID] let neighbourSet = List.filter (fun (i,_) -> contains i newVisited) startNode.Neighbours //Use only the neighbours that aren't visisted if(List.isEmpty neighbourSet) then newVisited; else neighbourSet |> List.minBy (fun (_,d:int) -> d) //Get neighbour with smallest distance |> fun (i, d) -> Traverse(newData, i, newVisited); //Recurse in to the traverse function, starting at the smallest neighbour let result = Traverse (nodes, 1, ); let writeList (lst:list<'a>):string = let mutable output = ""; for I in lst do output <- String.Concat(output, I); output; let path = "Output.txt"; File.WriteAllText(path , writeList(result));