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));
