2026-11-06
Select.hs
select :: Int -> [Int] -> Int
select _ [] = error "out of range"
select k (p : xs)
| k < n = select k smaller
| k == n = p
| otherwise = select (k - n - 1) [x | x <- xs, x > p]
where
smaller = [x | x <- xs, x < p]
n = length smaller
main :: IO ()
main = print (select 3 [2, 4, 2, 1, 3])
これは何を出力するでしょうか?
Answer
Output
4
select k は、先頭の p より小さい要素を smaller に集め、その個数 n と k を比べて、0始まりで k 番目に小さい要素がどこにあるかを決めます。k < n なら smaller の中、k == n なら p 自身、それより大きければ右側で、右側では smaller と p の分の n + 1 個を k から引きます。この引き算が正しいのは、p より前に並ぶ要素が smaller と p だけのときです。
右側を作る内包表記の条件は x > p なので、p と等しい要素は smaller にも右側にも入りません。最初の呼び出しでは p = 2 で、smaller は [1]、n は1です。k = 3 は1より大きいので、select 1 [4, 3] に進み、2番目の 2 はここで消えます。[4, 3] では p = 4 で smaller が [3]、n = 1 が k と等しいので 4 が返ります。
並べ替えると [1, 2, 2, 3, 4] なので、3番目(0始まり)は 3 だと読むのが自然です。消えた 2 は本来 3 と 4 より前に並ぶ要素で、それが抜けた右側では順位がすべて1つ繰り上がり、3 のあった位置に 4 が来ます。重複が無いリストなら、この内包表記の分け方でも正しい値が返ります。