Skip to content

Collections § Lists' sumEachItem is incorrect #41

@00-kat

Description

@00-kat
// Tail-recursion with a list, using cons pattern
let sumEachItem (myList:int list) =
    match myList with
    | [] -> 0
    | head :: tail -> head + sumEachItem tail

Firstly, this won't actually compile:

Program.fs:4:30: error: The value or constructor 'sumEachItem' is not defined. [FS0039]
    4 |     | head :: tail -> head + sumEachItem tail
      |                              ^~~~~~~~~~~

The binding needs to be made recursive;

-let sumEachItem (myList:int list) =
+let rec sumEachItem (myList:int list) =

Secondly, there is no TCO there because the stack frame needs to be kept around for head + ⟨value⟩ to be computed after the recursive call; if [<TailCall>] (as described in an earlier section) is added, a warning ensues:

Program.fs:5:30: warning: The member or function 'sumEachItem' has the 'TailCallAttribute' attribute, but is not being used in a tail recursive way. [FS3569]
    5 |     | head :: tail -> head + sumEachItem tail
      |                              ^~~~~~~~~~~

I'm not sure if the comment should be updated from “Tail-recursion” to “Recursion” or if an accumulator should be added though.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions