Namaran

Code daily. Without assist.

2026-11-06

Median.hs

import Data.List (partition)

select :: Int -> [Int] -> Int
select _ [] = error "empty"
select _ [x] = x
select k xs@(p : _)
  | k < n = select k ls
  | otherwise = select (k - n) rs
 where
  (ls, rs) = partition (< p) xs
  n = length ls

main :: IO ()
main = print (select 1 [3, 1, 2])

select k xs は、xs の要素を小さい方から数えて k 番目(0始まり)の要素を返すつもりの関数です。main の select 1 [3, 1, 2] は 2 を表示するはずが、いまは何も表示されず、プログラムが終わりません。

Answer

Wrong

select _ [x] = x
select k xs@(p : _)
  | k < n = select k ls
  | otherwise = select (k - n) rs
 where
  (ls, rs) = partition (< p) xs
  n = length ls

xs@(p : _) は先頭の p に名前を付けるだけで、partition (< p) xs は p を含む xs 全体を分けます。p < p は偽なので、p 自身は必ず rs に入ります。最初の呼び出しでは p = 3 で ls = [1, 2]、k = 1 は n = 2 より小さいので select 1 [1, 2] に進みます。今度は p = 1 がリストの最小値なので、ls は空、rs は [1, 2] 全体で、n = 0 の分岐から呼ばれるのはまた select 1 [1, 2] です。引数がまったく同じなので、この呼び出しは永遠に繰り返されます。

select _ [x] = x の節は要素が1つになれば止まりますが、リストが縮まない限りそこには着きません。p を左に入れようと partition (<= p) xs に変えても直りません。今度は p がリストの最大値のときに ls が xs 全体になり、select 0 [3, 1, 2] のように k < n の分岐で同じ呼び出しを繰り返します。p を残したまま分けると、どちらの側に入れても、片側が元のリストと同じになる入力があります。

Right

select _ [] = error "empty"
select k (p : xs)
  | k < n = select k ls
  | k == n = p
  | otherwise = select (k - n - 1) rs
 where
  (ls, rs) = partition (< p) xs
  n = length ls

(p : xs) で先頭を取り出し、残りの xs だけを分けます。ls と rs はどちらも p を含まないので、元のリストより必ず1つ以上短く、再帰するたびに長さが減っていずれ答えに着きます。p はどちらの側にも入らなくなったので、k == n のときに p を返す節を足し、右へ進むときは ls の n 個と p の1個を引いた k - n - 1 を渡します。[x] の節は、ls が空で k == 0 のときに p を返す節が受け持つので要りません。p と等しい要素は rs に残るので、重複があっても数え落としません。