functional-programming - 末尾再帰を使用して最大値を見つける

Question

末尾再帰を使用してリストの最大値を見つけようとしています。ただし、補助関数は使用できません...したがって、再帰を使用して行う必要があります。頭から始めて最大値を見つける関数を書きましたが、尾から始めてそれを実装する方法がわかりません!

lmax []  = error "empty list"
lmax [x] = x
lmax (x::y::xs) = 
  if x > y then lmax (x::xs)
  else          lmax (y::xs)

Answer 1

fun lmax l = let
  fun lmaxh [] a = a
    | lmaxh (x::xs) a = lmax xs Int.max(x,a)
  in
    lmaxh l 0
  end

これは、値が非負の整数であると仮定して機能します。

Answer 2

末尾再帰を実装すると、再帰呼び出しを作成した後にスタックを評価して「ポップオフ」する必要がないため、効率が最適化されます。

一般に、末尾再帰を使用するには、以前の計算からの「メモリ」を保存して現在の計算と比較し、将来の計算のために更新して、基本ケースで関数をすぐに終了する必要があります。

そのため、関数は既に末尾再帰的です。

ただし、これは末尾再帰maxList関数であり、より SML の精神に基づいています。

fun maxList l =
   let 
      fun maxListHelper l acc = 
         case l of 
             [] => acc
           | x :: xs' => if x > acc 
                         then (maxListHelper xs' x) 
                         else (maxListHelper xs' acc)
   in
     case l of
         [] => error "Empty List!"
       | x :: xs' => maxListHelper xs' x
   end

関数は非常にHaskell に似た構文で記述されており、関数定義内でネストされたケースとして明示的に宣言されることなく、異なるケースが異なる行で処理されます。これはまったく問題ありませんが、通常 SML では行われません。