Discussion on: Using Recursion to Loop in Elm

[1hko]

Here's another way to write diff(n) that computes in linear space and time. Another important distinction is the result is computed in a single n-sized loop instead of multiple loops

sq : Int -> Int
sq n =
    n * n


diff : Int -> Int
diff n =
    let
        loop sum squares n =
            if n == 0 then
                sq sum - squares
            else
                loop (sum + n) (squares + sq n) (n - 1)
    in
        loop 0 0 n


diff 10 == 2640

You could also implement loop generically using a union type and then implement diff with loop

type Loop state result
    = Recur state
    | Done result


loop : state -> (state -> Loop state result) -> result
loop init f =
    case (f init) of
        Recur state ->
            loop state f

        Done value ->
            value


diff : Int -> Int
diff n =
    loop ( 0, 0, n ) <|
        \( sum, squares, n ) ->
            if n == 0 then
                Done (sq sum - squares)
            else
                Recur ( sum + n, squares + sq n, n - 1 )

diff 10 == 2640

Both implementations are tail recursive and do not grow the stack