F# implicit typing choking on simple recursion

Question

When I define a recursive function in F# thus:

let rec recursiveSum inputs =
    let startState = 0.0m

    if List.length inputs = 1 then
        startState + inputs.Head
    else
        let t = List.tail inputs
        startState + inputs.Head + recursiveSum t

...all is good. When I attempt to avoid the "empty list" problem thus:

let rec recursiveSum inputs =
    let startState = 0.0m

    **if List.isEmpty inputs then startState**

    if List.length inputs = 1 then
        startState + inputs.Head
    else
        let t = List.tail inputs
        startState + inputs.Head + recursiveSum t

...I get yelled at:

recursion.fsx(5,9): error FS0001: This expression was expected to have type
    unit    
but here has type
    decimal

What am I missing here?

Answer 1

From the docs:

The types of the values produced in each branch must match. If there is no explicit else branch, its type is unit. Therefore, if the type of the then branch is any type other than unit, there must be an else branch with the same return type.

You're missing said else.

let rec recursiveSum inputs =
    let startState = 0.0m

    if List.isEmpty inputs then 0.0m
    elif List.length inputs = 1 then
        startState + inputs.Head
    else
        let t = List.tail inputs
        startState + inputs.Head + recursiveSum t

(N.b. I've used elif here rather than nesting another if expression; hopefully that's not too much of a distraction.)

That said, your logic involving startState is highly suspect; it's always zero, and really serves no purpose here. Your state should probably be a parameter rather than a local value so it can be used as an accumulator:

let recursiveSum inputs =
    let rec impl state inputs =
        if List.isEmpty inputs then state
        elif List.length inputs = 1 then
            state + inputs.Head
        else
            let t = List.tail inputs
            impl (state + inputs.Head) t
    impl 0.0m inputs

Lastly, let's make it idiomatic:

let recursiveSum inputs =
    let rec impl state inputs =
        match inputs with
          | []   -> state
          | [h]  -> state + h
          | h::t -> impl (state + h) t
    impl 0.0m inputs

which can be shortened to

let recursiveSum inputs =
    let rec impl state = function
      | []   -> state
      | h::t -> impl (state + h) t
    impl 0.0m inputs

Answer 2

With ildjarns answer, I think I would suggest that one could/should go all the way...

let rec fold f acc = function 
        | [] -> acc
        | [x] -> f x acc
        | h::t -> fold f (f h acc) t




let someDec = [0.1m; 0.2m]
let someStr = ["world"; "Hello "]

someDec
|> fold (+) 0.0m

someStr
|> fold (+) ""


let recursiveSum = fold (+) 0.0m    

someDec
|> recursiveSum


let recursiveStrAdd = fold (+) ""

someStr
|> recursiveStrAdd


someDec
|> recursiveSum

(And I never remember left or right here, so... ;-)