Написание факториальной функции со списками

Хотя я считаю, что нашел надежный алгоритм для своей функции (факториал), я очень смущен тем, почему он зацикливается бесконечно. Вот мой код:

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}}

tail-recursion invariants oz mozart
person user3078046    schedule 16.10.2014    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Вы никогда не увеличиваете M => {Fact (M+1) (M|Acc}} всегда {Fact 2 1|Acc}

и чтобы сделать ваш код более читабельным, вы не обязаны писать

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

ты можешь просто написать

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

код

Принимая во внимание эти вещи, самая простая факториальная функция

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
person yakoudbz    schedule 16.10.2014
comment
Спасибо за ваше предложение (о удобочитаемости), я попробую это в будущем. Я собираюсь попытаться переписать алгоритм с другой идеей. - person user3078046; 16.10.2014

arrow_upward
0
arrow_downward

Я впервые вижу программу, написанную на этом языке, но, кажется, нашел проблему. Функция FactT рекурсивная, верно? Первый аргумент FactT — «верхний предел», верно? я думаю проблема здесь

{FactT (M+1) (M|Acc)}end

Вы сравниваете M (которое всегда равно 1) с M+1 (которое передается в качестве первого аргумента (N)). Это сравнение всегда «ложно». Например, на первой итерации это 1==N (ложь), на второй итерации это не 2==N, а 1==2 (ложь) и так далее.

Извините за плохое объяснение. Надеюсь, вы поняли, что я хотел сказать.

Вероятно, это должно выглядеть так:

{FactT N ((M+1)|Acc)}end

или что-то.

person Rei    schedule 16.10.2014
comment
Большое спасибо за это объяснение. Я думаю, вы точно указали, где была ошибка. Но предложение, которое вы сделали, не может быть применено, потому что часть (M + 1) | Acc расширяет 2 до nil в виде списка, затем 2 до 2 и продолжает работать. Таким образом, аргументы не развиваются, что противоречит принципу рекурсии. - person user3078046; 16.10.2014
comment
@user3078046 user3078046, как я уже сказал, я никогда раньше не видел этот язык, поэтому я действительно не знал, что означает (M+1)|Acc (и не хотел гуглить :)). Добро пожаловать в любом случае. - person Rei; 16.10.2014