F# Recursion to Summarize a Path given by List of Points

user_17167251 0
Viewed 83

I am new to F# and have stumbled on a problem that I am interested in. I am trying to recreate similar functionality to List.reduce with recursion instead. The function uses sumTwoPoints to calculate the sum of two elements in a list of coordinates and returns one element.

let sumTwoPoints(x1, y1) (x2, y2) : float * float = (x1 + x2, y1 + y2)

What I have done so far:

let rec pathSum list = 
    match list with
    | [] -> failwith "Empty List"
    | head::next::rest -> sumTwoPoints head next :: rest

My thought process is this

// e0() e1() e2() e3() e4()...
// sumTwoPoints (e0 e1) = r1
// sumTwoPoints (r1 e2) = r2
// sumTwoPoints (r2 e3) = r3 
// sumTwoPoints (r3 e4) = r4
// pathSum = r4

The e0 represents the element in the list. If we go by this system, head = e0 and tail = e1 and the rest list has leftover elements. I am not sure about adding the new r1 to the rest list, but that is what I came up with. The next step, if my logic is correct, is to pass this new list to pathSum, but get again, I don't know how to achieve that in the code.

My proposed solution might be completely wrong, and any advice or help would be appreciated.

recursion list f#
2 Answers

You'd need to modify your function to add a parameter for the current point.

The logic would be that it adds the 'head' of the list to that point, then recursively calls itself with the result of that addition and the rest of the list. When it's finally called with an empty list, it simply returns the point value.

let rec pathSum (current:float * float) list =
    match list with
    | [] -> current
    | head::rest ->
        let next = sumTwoPoints head current
        pathSum next rest

The initial call would have to pass an initial value of (0, 0):

pathSum (0, 0) list
user_13208450

A follow up to what Charles Mager as answered you need to look at list. It can either be empty []or have the value of another list x::y. If you take a closer look at your functions

sumTwoPoints : (float * float) -> (float * float) -> (float * float)
pathSum : (float * float) list -> (float * float)

This way you have rest as the type of (float * float) list which when called with pathSum gives the type (float * float). This way you can utilize the function sumTwoPoints without the need of next

 let rec pathSum list =
    match list with
    | [] -> (0.0, 0.0)
    | head::rest ->
        sumTwoPoints head (pathSum(rest))

And lastly you will need to change failwith to give zero as otherwise it will fail the recursion.

user_121445020
Related