S2S

[ quoted from ] 情報演習 課題S-B-2（※）一部抜粋・改変

(1)

任意の長さnのリスト (a₁ a₂ … a_n) を入力とし、長さn+1のリストのリスト

    ((a1 a2 … an) (a2  … an) … (an) ())

を返す再帰関数tailsを定義せよ。

       例： 

    > (tails '(1 2 3 4 5)) 

    ((1 2 3 4 5) (2 3 4 5) (3 4 5) (4 5) (5) ()) 

(2)

任意の長さnのリスト (a₁ a₂ … a_n) を入力とし、長さn+1のリストのリスト

     (() (a1) (a1 a2) … (a1 a2 … an))

を返す再帰関数headsを定義せよ。

       例： 

    > (heads '(1 2 3 4 5)) 

    (() (1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5)) 

(3)

整数のリスト (a₁ a₂ … a_n) を受け取り、その連続する部分列

    ai, ai+1, …, ai+k-1 (k≧0, 1≦i≦n, i+k≦n)

の総和 a_i+ … +a_i+k-1 のうち最大の総和を返す関数mssを定義せよ。

       例： 

    > (mss '(1 2 3 -4 1)) 

    6 

    > (mss '(-5 2 8 -19 9 6 8 -1 2 -1)) 

    24 

tailsはtailの集まり

与えられたリストの後ろ側（尾っぽ）の部分集合を求める関数を作れという問題ですが、その名の通りtailsはtailの集まりなので、tailsという関数はtails自身で再帰的に定義されます。

図は、tailsの入れ子構造、すなわちtails関数の再帰構造を示しています。この図がほぼそのまま答えになっているので、眺めながらアルゴリズムを考えてみてください。

基本関数

tailsを実装するには、cdr,consの２つの基本関数を使います。簡単に説明をすると、cdrはリストの後ろ側を返す関数、consリストの頭に何か要素をくっつけたリストを作る関数です。しかし、この課題をこなすには、リスト構造とこれら基本関数の正確な定義を知っておく必要があります。

厳密には、基本３関数car,cdr,consはどれもリストではなくてペアに関する関数です。つまり、(cons a b) はペア(a . b)を生成する関数で、car,cdrはそれぞれペア(a . b)からa,bを得る関数なのです。なぜペアを扱う関数でリストも扱えるかというと、実はリスト(a b c … z)が、(a . (b . (c . … (z . '() ))))という風にpair of pair構造をしているからです。

注意点

問題に与えられている出力例では、空リスト()が最後についていることに注意してください。リストの構造と上記の基本関数の挙動を理解していないと、思い通りの結果が得られず、空リストがつかない結果を得るかもしれません。

もっとも、実は問題（３）でtails,headsの結果につく空リストが邪魔になってくるので、実際の所は空リストがない方が嬉しいわけですが。問題の出力例ではついているので、忠実に空リストもつけた方が無難でしょう。

まずはheadを作る

基本的にtailsと同じ考え方で実装できそうです。ですが、tailsの場合にtailを求めるために使った関数cdrにあたる基本関数がありません。そこで、まずは入力されたリストの頭（head）側を返す関数を自前で作ってしまうのがいいでしょう。

単にheadだとか、carの集まりなのでcarsだとか、一番後ろを削って得られるリストという意味でdel-tailだとか、自分が分かりやすい名前をつけるようにしましょう。自分さえ分かれば何でもいいのです。

(define (head ls)
  (if ;入力lsのcdrが空の場合、lsには「イラナイcar」しか残っていないので…
      ;終了条件が満たされた場合は空リストを返す
      ;lsのcarと、lsのcdrのheadを繋げたものがlsのhead
  )

headsはheadの集まり

あとはtailsと同じように実装するだけです。同じことですが、一応大枠を示しておきます。

(define (heads ls)
  (if ;入力が空かどうか
      ;空の入力に対してheadsはどんなリストを返せばいいのか
      ;lsのheadのheadsと、lsをくっつけて返す
  )

注意点

ところが、今度もやはりリストの構造を理解していないと失敗します。headsとtailsでは、リストの入れ子構造が文字通り頭と尾が逆になってしまうため、consは使えません。

そこで今度はappend関数を使うのが楽です。(append ls1 ls2)はリストls1,ls2を繋げたリストを作ります。(append '(0 1) '(2 3))など色々試してみるといいでしょう。空リストを繋げたときの扱いや、list of listを繋げたときの扱いに気をつけてください。今回headsで得たいものがlist of listであることを忘れずに。

ちなみにheadやappendはなくてもできます。つまり、少し工夫して違うアルゴリズムにすれば、headもappendも持ち出さずにheadsを再帰的に定義できます。余裕のある人は考えてみてもいいでしょう。ただし計算量は、appendを使わない分少し減る程度で、どちらのアルゴリズムでも大体同じです。

まずはsublistsを作る

入力リストに対して、連続する部分列の和の最大値が欲しいので、まずは部分列を求める関数sublistsを作りましょう。それ自体は難しくなく、tailsにheadsをかけ合わせればsublistsができあがります。さっき作ったtailsとheadsが早速活躍です。

(define (sublists ls) (map heads (tails ls)))

sublistsの問題点

ところがこれにはいくつか問題があります。まず、結果がlist of list of listになっています。tailsやheadsは、listからlist of listを作って返す関数だったので、それらをかけ合わせれば当然階層が増えてしまいます。次に、tailsやheadsが空リストも含めて返すので、結果に空リストが大量に含まれてしまいます。特に後者の問題はmssを実装するのにはとても邪魔です。

ただどちらも無理に直さなければならないというものでもないので、必要に応じて対応するプログラムを書いてください。例えば、sublistsの定義自体を少し書き換えて、list of listで空以外の部分列を返すようにするとか、mssを計算するときに空リストは無視するなどです。

sumとmax

入力されたリストの和や最大値を求める関数は、ありそうでありません。ただし、複数の入力の和や最大値ならば簡単に求められます。

(+ 1 2 3 4 5) ; -> 15
(max -1 -2 3) ; ->  3

一つの方法は、この形にリストを展開してこれらの関数を利用することです。もう一つの方法は、リストを入力として和や最大値を求める関数を自前で作ってしまうことです。そう難しくはないので、後者をオススメしておきます。

mss = max * sum * sublists

ここまで来れば何も考えることはありません。max,sum,sublistsの３種類を組み合わせるだけでmssは完成です。

見ての通り３種類の関数を組み合わせているだけなので、この実装方法は計算量的にあまり良いとは呼べないものです。しかし、mssはさらに効率よく計算できるアルゴリズムが存在しており、sublistsを一切使わずに最大の部分列和を求められるのです。まぁこの課題では、(1),(2)のtails,headsがsublistsを作るための誘導問題になっているので、多少計算量が多くても、sublistsを活用する方法で十分です。