Namaran

Code daily. Without assist.

2026-11-04

Gaps.hs

gaps :: [Int] -> [Int]

Int のリストの各要素を、リスト全体の最大値からその要素を引いた値に置き換えたリストを返す gaps を書いてください。リストは先頭から末尾まで1回だけたどり、最大値を求めるために maximum などで別にたどってはいけません。空リストには空リストを返します。

入力例 1

gaps [3, 7, 5]

出力例 1

[4,0,2]

入力例 2

gaps [2]

出力例 2

[0]

入力例 3

gaps []

出力例 3

[]
Reference
gaps :: [Int] -> [Int]
gaps xs = ys
 where
  (top, ys) = go xs
  go [] = (minBound, [])
  go (x : rest) =
    let (m, zs) = go rest
     in (max x m, top - x : zs)

1回たどるだけでは、先頭の要素を見ている時点で最大値はまだ分かりません。手続き型の考え方では、最大値を先に求めるか、差をあとで書き直すことになります。Haskell では、where に書いた (top, ys) = go xs は、上から順に実行される手順ではなく、top と ys が何であるかを述べる等式です。そのため、go の中で、go 自身が最後に返す最大値 top を使えます。

go は1回の再帰で2つのものを同時に作ります。組の1つ目は残りの最大値と自分を比べた最大値で、ここに top は出てきません。2つ目は各要素の差 top - x のリストです。遅延評価なので、top - x は再帰の最中には計算されず、「あとで top から x を引く」という未評価の式のままリストに入ります。print が要素を表示しようとして初めて top が求められ、そのときには最大値の計算はたどり終えた結果から決まります。最大値の計算が差を必要としないので、定義が循環していても答えは決まります。1

空リストでは go [] が (minBound, []) を返し、ys は空なので top が使われることはありません。minBound は max でどの要素より大きくならない初期値です。掲載したのは参考実装で、唯一の正解ではありません。foldr で組を畳み込んでも、同じように書けます。

  1. 計算の結果を、その計算自身の中で使うこの書き方は、tying the knot(結び目を作る)と呼ばれます。Richard Bird が1984年の論文で、木の葉をすべて最小値に置き換える repmin という問題を、1回の走査で解いてみせたのがよく知られた例です。