Report functions that are not tail-call-optimized

[jfmengels]

What the rule should do:

Report when functions that are tagged to or supposed to be TCO are not.

What problems does it solve:

TCO functions are faster than their non-TCO counterparts (usually)

Example of things the rule would report:

Doing an operation on the result of a recursive call

reverse : List a -> Maybe a
reverse list =
  case list of
    [] -> Nothing
    x :: xs -> reverse xs ++ [ x ]

Using pipelines in the recursive call

tailCallWithPipeline : Int -> String -> String
tailCallWithPipeline count acc =
    if count <= 0 then
        acc

    else
        acc
            |> tailCallWithPipeline (count - 1)

Having the recursive call inside a boolean expression

isPrefixOf : List a -> List a -> Bool
isPrefixOf prefix list =
    case ( prefix, list ) of
        ( [], _ ) ->
            True
        ( _ :: _, [] ) ->
            False

        ( p :: ps, x :: xs ) ->
            -- Defeats TCO
            p == x && isPrefixOf ps xs
            -- The following would work
            -- if p == x then
            --     isPrefixOf ps xs
            -- else
            --     False

Example of things the rule would not report:

Properly TCO function that was somehow tagged

last : List a -> Maybe a
last list =
  case list of
    [] -> Nothing
    x :: [] -> Just x
    _ :: xs -> last xs

Also, non-TCO functions that were not tagged, and non-recursive functions.

Configuration example:

This depends on how we wish to tag functions.

config =
  [ -- If we explicit them all in the configuration, then
    NoFailingTailCallOptimization.rule [ ( "List.Extra", "last" ) ]
    -- if we tag them through comments, then
  ,  NoFailingTailCallOptimization.rule
  ]

If we explicit them in the configuration, then we should report functions that could not be found in the project.

For tagging through comments, I imagine we can look for comments like TCO or whatever at the beginning of a function

last : List a -> Maybe a
last list =
  -- TCO
  case list of
    [] -> Nothing
    x :: [] -> Just x
    _ :: xs -> last xs

which is more fragile though. The exact string could be configurable.

When (not) to enable this rule:

If you do not care about performance and stack-safety, and/or have no knowledge about TCO.

I am looking for:

• Expert knowledge on TCO
• A good explanation on TCO, to put in and/or link to in the error message
• Feedback on how to tag a function as TCO
• A good rule name. I was thinking of but am not entirely convinced by NoFailingTailCallOptimization
• To know in which package(s) this would fit best. I thought about elm-review-performance, but I don't know what else could go in there.
• A discussion on whether we should report mutually recursive functions, which are not TCO

[jfmengels]

I added this case where a function is not TCO apparently.

[jfmengels]

Published as https://package.elm-lang.org/packages/jfmengels/elm-review-performance/latest/NoUnoptimizedRecursion!