Search code examples
tail-recursioninvariantsozmozart

Writing a Factorial function with Lists


While I believe I have found a sound algorithm for my function (Factorial) I'm very confused as to why it loops infinitely. Here's my code :

declare
fun{Fact N}
   local M=1 in             %I suppose it loops from here??
      local FactT in        %But the function call starts from here
     fun{FactT N Acc}       % which doesn't include the local declaration of M
        if M==N then
           {Browse M}
           Acc
        else
           %{Browse M}     %displays infinite lines of 1s
           %{Browse N}
           %{Browse Acc}   %They form a continuously growing list of 1s
           {FactT (M+1) (M|Acc)}end
     end
     {FactT N nil}
      end
   end
end

{Browse {Fact 3}}

Solution

  • You never increment M => {Fact (M+1) (M|Acc}} is always {Fact 2 1|Acc}

    and to make your code more readable, you're not obilged to write

    fun...
       local ...
       in ...
       end
    end
    

    you can just write

    fun...
       ...
    in
       ...
    end
    

    code

    Taking those things into account, the most simple factorial function is

    declare
    fun {Fact N}
       fun{Aux N Acc}
          if N=<0 then Acc
          else {Aux N-1 N*Acc}
          end
       end
    in
       {Aux N 1}
    end