Хвостовая рекурсия в SML не дает никакого результата

Следуя моему предыдущему сообщению здесь, я попытался сделать то, что было предложено, и преобразовать код в метод хвостовой рекурсии с let .

Исходный код - который не работает (из-за использования val внутри условия if):

fun func() = 

val decimal = 0 (* the final result *)
val multiple = 0 (* keeps track of multiples, eg. In XXV, X would be a multiple *)
val current = 0 (* the digit currently being processed *)
val top = 0   (* value of the last element in the list *)
val last_add = 0 (* the last digit that wasn't a multiple, or subtraction operation *)
val last_sub = 0
val problem = 0 (* if value is 1 then there is a problem with the input *)
val myList = [1,2,3,4,5] (* the list has more values *)

while (myList <> [])    (* run while the list is not empty *)

    val current = tl(myList) (* grab the last element from the list *)
    val myList = tl(myList) (* remove the last element from the list *)
    val top = tl(myList) (* grab the value at the end of the list *)
    if ( myList <> []) andalso (current > top))
       then      

                val decimal = decimal + current - top
                val last_sub = top;
                val myList = tl(myList)
       else     
           if ( (myList = []) andalso (current = top))
              then val decimal = decimal + current
                   val multiple = multiple + 1
              else
                  if (last_sub = current)
                     then val problem = 1

                     else
                          val decimal = decimal + current
                          val multiple = 0
                          val last_add = current

И код как метод хвостовой рекурсии:

fun calc [] = 0
    |calc [x] = x
    |calc (head::tail) = 
       let 
          val decimal = 0
          val multiple = 0
          val current = 0
          val top = 0  
          val last_add = 0
          val last_sub = 0
          val problem = 0  
          val doNothing = 0
       in      

          let
              val current = hd(rev(head::tail))  (* grab the last element *) 
              val head::tail = rev(tl(rev(head::tail)))  (* POP action - remove the last element from the list *)
              val top = hd(rev(head::tail))      (* grab the new last element after removing *)
              in 
                if (current > top) then 
                    let 
                          val decimal = decimal + current - top
                          val last_sub = top 
                          val head::tail = rev(tl(rev(head::tail)))  (* POP action - remove the last element from the list *)
                    in
                    calc(head::tail)
                    end
                else
                 if ( (head::tail = []) andalso (current = top))
                   then let 
                          val decimal = decimal + current
                          val multiple = multiple + 1
                        in 
                          calc(head::tail)
                        end
                 else 
                     if (last_sub <> current)
                       then let 
                               val decimal = decimal + current
                               val multiple = 0
                               val last_add = current
                            in 
                               calc(head::tail)
                            end
                     else
                        (* do nothing *)    
                        val doNothing = 0
               end      

       end; 

Однако, когда я пытаюсь войти:

calc([0,100,20,30,4,50]);

Я получил :

uncaught exception Bind [nonexhaustive binding failure]
  raised at: stdIn:216.13-216.50

Я знаю, что этот код очень труден для чтения и довольно длинный, но я был бы очень признателен, если бы кто-нибудь объяснил мне, как его исправить, или помог найти причину этого вывода.

Спасибо


person JAN    schedule 29.12.2012    source источник


Ответы (1)


У вас есть несколько проблем с вашим кодом.

Прежде всего, вы можете использовать last для захвата последнего элемента списка. Дополнительную информацию см. в документации списка. Но если у вас нет действительно веских причин для этого, проще и гораздо эффективнее просто начать с начала списка и удалять элементы из начала по мере рекурсии. У вас уже есть первый элемент, связанный с head в вашем коде с помощью сопоставления с образцом.

Во-вторых, если вы не используете refs (что вы, вероятно, не хотите делать), в Standard ML нет переменных, только значения. Это означает, что если вы хотите переносить состояние между вызовами, любые аккумуляторы должны быть параметрами вашей функции. Использование вспомогательной функции для инициализации аккумуляторов является распространенным шаблоном.

В-третьих, вместо того, чтобы сравнивать список с [], чтобы проверить, пуст ли он, используйте функцию null. Поверь мне в этом. Вы получите предупреждения, используя =, из-за проблем с тонким выводом типов. Еще лучше использовать сопоставление с образцом для параметров вашей функции или использовать оператор case. Сопоставление с образцом позволяет компилятору сообщить вам, обработали ли вы все возможные случаи.

В-четвертых, SML обычно использует для имен переменных camelCase, а не змеиный регистр. Это более стилистически, но по мере того, как вы будете писать больше кода и сотрудничать, вам захочется соответствовать соглашениям.

В-пятых, когда вы выполняете рекурсию по списку, не пытайтесь просмотреть несколько значений в списке. Это все усложняет. Относитесь к нему как к головному элементу и хвостовому списку, и все станет намного проще. В моем коде, вместо того, чтобы сохранять актуальность в списке, я сделал это, выделив его в отдельный параметр. У вас есть базовый случай, когда вы просто возвращаете ответ из одного из ваших аккумуляторов, и рекурсивный случай, когда вы выполняете рекурсию с обновленными значениями аккумулятора, и одно значение выталкивается из вашего списка. Это исключает проблемный сценарий.

Я не уверен, что эта логика верна, так как я не знаю, что вы пытаетесь вычислить, но посмотрите на этот код, который иллюстрирует некоторые вещи, о которых я говорил.

(* This is the helper function which takes accumulators as
   parameters. You shouldn't call this directly. *)
fun calc' decimal _ _ _ _ [] =
    (* We processed everything in the list.  Just return the accumulator. *)
    decimal
  | calc' decimal multiple lastAdd lastSub current (top::tail) =
    (* This case is for when there are 1 or more elements in the list. *)
    if current > top then
        calc' (decimal + current - top) multiple lastAdd top top tail
    else if current = top then
        calc' (decimal + current) (multiple + 1) lastAdd lastSub top tail
    else
        calc' (decimal + current) 0 current lastSub top tail

(* This is the function you should call. *)
fun calc [] = 0
  | calc [_] = 0 (* Given a single-element list. *)
  | calc (x::xs) =
    (* Apply the helper with correct initial values. *)
    calc' 0 0 0 0 x xs

В функциональном языке вместо присваивания значения переменной, когда вы хотите ее изменить, просто выполните рекурсию и укажите новое значение для правильного параметра. Вот как вы пишете «цикл» на функциональном языке, используя рекурсию. Пока вы используете только хвостовую рекурсию, она будет так же эффективна, как цикл while в вашем любимом императивном языке.

person Jonathan Tran    schedule 29.12.2012