F# implementation of the A* algorithm

This is my first attempt at writing something useful in F# and in a functional way in general. I would appreciate if you could point out any issue, even details, as I'd like to put all the bad habits aside as soon as possible. I tried to leave my OOP comfort zone when I wrote this but I feel like this is not enough. I would love to hear suggestions about how to make this code more functional.

Please consider that the code in Program.fs is for testing only and has a lot of ugly stuffs in it (magic numbers, poor logic). I've put it here so that you can see how the code in Pathfinding.fs is used. The code in main creates the following grid with 10 rows and 10 columns and sets which nodes are obstacles:

0  1  . . . 9
10          19
.           .
.           .
.           .
90 91 . . . 99

Pathfinding.fs

```
module Pathfinding

//Classic Vector2 type with distances calculation
type Vector2 =
{
mutable X : float;
mutable Y : float;
} with

member this.EuclideanDistance(otherVector:Vector2) =
let distanceX = otherVector.X - this.X
let distanceY = otherVector.Y - this.Y
sqrt (distanceX distanceX + distanceY distanceY)

member this.ManhattanDistance(otherVector:Vector2) =
let distanceX = abs (otherVector.X - this.X)
let distanceY = abs (otherVector.Y - this.Y)
distanceX + distanceY

// Open = Available to get chosen as the starting point for a new recursion
// Closed = Already used during one recursion, not available anymore
// NotUsed = Ready to be opened, never used before
// Obstacle = Can't be used and won't be reset
type NodeState = Open = 0 | Closed = 1 | NotUsed = 2 | Obstacle = 3

//A possible point on paths
type Node =
{
mutable g : float; //Sum of the distances between each nodes from the starting node to this one, following the parents
mutable h : float; //Sum of all the manhattan distance of the parents nodes and this node

Typically, F# is written in functional style, and there are several things you are not doing in functional style here.

type Vector2 =
    {
        mutable X : float;
        mutable Y : float;
    } with

    member this.EuclideanDistance(otherVector:Vector2) =
        let distanceX = otherVector.X - this.X
        let distanceY = otherVector.Y - this.Y
        sqrt (distanceX * distanceX + distanceY * distanceY)

    member this.ManhattanDistance(otherVector:Vector2) =
        let distanceX = abs (otherVector.X - this.X)
        let distanceY = abs (otherVector.Y - this.Y)
        distanceX + distanceY

X and Y should not be mutable here. You should write these as a record:

type Vector2 = { X :float; Y :float }

Then, instead of having class members, you would make the EuclideanDistance and ManhattanDistance pure functions:

let euclideanDistance (vector1 :Vector2) (vector2: Vector2) =
    let distanceX = vector2.X - vector1.X
    let distanceY = vector2.Y - vector1.Y
    sqrt (distanceX * distanceX + distanceY * distanceY)

let manhattanDistance (vector1 :Vector2) (vector2: Vector2) =
    let distanceX = abs (vector2.X - vector1.X)
    let distanceY = abs (vector2.Y - vector1.Y)
    distanceX + distanceY

You will probably be able to remove the type hints as well, and F# will still be able to figure out what types the parameters are.

In a few places you assign a variable, then immediately return the variable. Instead of this, you should return the result of the calculation. One such place is here:

member private this.generatePathList currentNode lastNode =
    let mutable result = [currentNode.Position]
    match currentNode.Id with 
    | x when x = lastNode.Id -> result
    | _ ->  result <- (this.generatePathList currentNode.ParentNode lastNode) @ result
            result

That should be rewritten as:

member private this.generatePathList currentNode lastNode =
    match currentNode.Id with 
    | x when x = lastNode.Id -> [currentNode.Position]
    | _ -> (this.generatePathList currentNode.ParentNode lastNode) @ [currentNode.Position]

This looks like a bug:

let assignNodesToPathfinder (nodeList:Node list) (pathfinder:Pathfinder) =
    let action n = pathfinder.addNode n
    let list = List.map action nodeList
    nodeList

You iterate the list and create a new list based on the action, but return the original list and do nothing with the new list. Unless pathfinder.addNode has side effects somehow, in which case you should ignore the result of the List.map. Given the name of the function, it looks as if you really just want a void result, so you can return a unit, which is essentially the same. The unit literal in F# is (), but you can also get it by returning a unit from another expression. Give these assumptions, I would write it as:

let assignNodesToPathfinder (nodeList:Node list) (pathfinder:Pathfinder) =
    ignore <| List.map pathfinder.addNode nodeList

Notice that if you have a function that takes a single parameter and returns a new result, you can just place it inline like the way I did above.

Another way to write it would be using tail recursion:

let rec assignNodesToPathfinder (nodeList:Node list) (pathfinder:Pathfinder) =
    let head::tail = nodeList
    pathfinder.addNode head

    if not tail.IsEmpty then
        assignNodesToPathfinder tail pathfinder

StackExchange Code Review Q#152064, answer score: 2