ソフトウェア技法 No.4の演習問題の補足

• 普通に漸化式で考えると、「リストlst の2番目に大きな値」を 「リストlst のtail部分 (List.tl lst) の2番目に大きな値」をつかって 表すことになるが、これはできそうもない。 「リストlst のtail部分 (List.tl lst) の1番目に大きな値」も知らないとい けない。
• そこで、方針としては2つ考えられる。
• 1つは、既につくったmax_listを駆使するものである。つまり、

  let rec second_largest lst =
    match lst with
     | [] -> ...
     | h::t -> 
        let num1 = max_list t in
        let num2 = second_largest t in
           あとは、num1,num2,h の「2番目」を返せばよい。
  

  これはあまり効率がよくない実装だが、この段階ではこれでもよい。

• もう1つは、 「リストlst の1番目と2番目に大きな値」を 計算する補助関数を定義することである。これは、2つの値を同時に返すので あり、関数としては表現できないように思えるかもしれないが、 リストにくるめばよい。つまり、 「リストlst の1番目と2番目に大きな値をリストにしたもの」を 返す補助関数を作るとよい。

  let rec take_top2 lst =
    match lst with
     | [] -> [-10000; -10000]
     | h::t -> 
        let top2 = take_top2 t in
            あとは、List.hd top2 と List.hd (List.tl top2) と
            h の中で「1番目」と「2番目」を取り，
            それらのリストを返せばよい。
  
  let second_largest lst =
     let top2 = take_top2 lst in 
       List.hd (List.tl top2)
  

• もう1つの方法は，リストの先頭から「大きい方から2つ」を とっていく方法である． これは，引数を増やして対応することになるので，補助関数がいる．

  let rec second_largest2 largest second lst =
    match lst with
     | [] -> second
     | h::t -> 
        h, largest, second のうち，上位1，2の
        ものがどれかを求めたあと
          second_largest2 最大値 2番目 t
        を呼ぶ
  
  let second_largest lst =
    match lst with
     | [] -> failwith "too short list"
     | [h] -> failwith "too short list"
     | h1 :: h2 :: t ->
        if h1 > h2 then 
          second_largest2 h1 h2 t
        else 
          second_largest2 h2 h1 t