Namaran

Code daily. Without assist.

2026-09-06

FirstFree.hs

import Data.Maybe (listToMaybe)

firstFree :: [(Int, Int)] -> Maybe (Int, Int)
firstFree taken =
  listToMaybe [(day, hour) | hour <- [9 .. 17], day <- [1 ..], (day, hour) `notElem` taken]

main :: IO ()
main = print (firstFree [(1, 9)])

予約で埋まっている枠の一覧 taken を避けて、最も早い空き枠 (日, 時) を返す firstFree です。日は 1 から始まって終わりがなく、各日の枠は 9 時から 17 時までです。早さはまず日で比べ、同じ日なら時で比べます。firstFree [(1, 9)] に対して、いまは Just (2,9) を出力します。本来の出力は Just (1,10) です。どこを直せばよいでしょうか?

Answer

2つの生成器の順番を入れ替えて、day <- [1 ..], hour <- [9 .. 17] にします。

内包表記の生成器は、左が外側、右が内側のループになります。いまのコードでは外側が hour、内側が day なので、枠は (1,9)、(2,9)、(3,9) の順に、日をまたいで同じ時刻から並びます。(1,9) は埋まっているので、最初に条件を満たすのは (2,9) です。結果の組を (day, hour) の順に書いていても、並び順を決めるのは生成器の順番で、組の形ではありません。

内側の day <- [1 ..] には終わりがないので、hour が 10 に進むことはありません。それでもプログラムが止まらずに答えを返すのは、listToMaybe が先頭の1要素しか求めず、内包表記もその1要素が決まるところまでしか評価されないからです。無限の生成器を内側に置いた誤りはハングとして現れず、9 時の枠しか探さないという、出力だけ見ればもっともらしい結果になります。

入れ替えると、外側の day には終わりがなくても、内側の hour は9個で一巡するので、1日目の 9 時から 17 時までを調べてから2日目に進みます。最初に条件を満たすのは (1,10) です。taken は有限なので、空き枠はどこかの日で必ず見つかります。並び順を気にせずに全体から minimum で最小の組を選ぶ直し方では、終わりのないリストを最後まで読もうとして、今度は本当に止まらなくなります。