Namaran

Code daily. Without assist.

2026-08-30

Codes.hs

import Data.Bits (shiftR, xor)

grays :: [Int]
grays = [i `xor` (i `shiftR` 1) | i <- [0 ..]]

codes :: Int -> [Int]
codes n = filter (< 2 ^ n) grays

main :: IO ()
main = print (codes 3)

grays は、i = 0, 1, 2, ... を順に i `xor` (i `shiftR` 1) に変えた値の無限リストです。codes n は、そのうち n ビットに収まる値を、grays に現れる順にすべて並べたリストを返すつもりの関数です。main は本来 [0,1,3,2,6,7,5,4] を表示して終わるはずが、いまは何も表示されないまま、いつまでも終わりません。

Answer

Wrong

codes n = filter (< 2 ^ n) grays

filter は遅延評価なので、無限リストにかけても条件を満たす要素を先頭から1つずつ返せます。print は [0,1,3,2,6,7,5,4 までの文字を作りますが、閉じ括弧 ] を出すには、この先に 8 未満の値がもう無いことを確かめる必要があります。filter にはそれが分からないので、i = 8 以降の値を1つずつ調べ続け、リストの終わりに着くことはありません。表示しかけた文字は出力のバッファにたまり、改行も来ずバッファもいっぱいにならないので、画面には何も出ません。

filter を選んだのは、grays の値が 0, 1, 3, 2, 6, 7, 5, 4 と大きくなったり小さくなったりするので、「最初に条件を外れた値で止める takeWhile では、途中で切れてしまう」と考えたからでしょう。けれども i `shiftR` 1 は i の最上位ビットより上にビットを持たないので、i と符号の最上位ビットは同じ位置にあります。i が n ビットに収まるときに限って符号も収まるので、n ビットの符号は grays の先頭の 2 ^ n 個にすべて並び、その後ろには1つも現れません。

Right

codes n = take (2 ^ n) grays

take (2 ^ n) は、先頭から 2 ^ n 個を取ったところでリストを閉じ、grays の残りを調べません。上で見たとおり、先頭の 2 ^ n 個が n ビットに収まる符号のすべてなので、codes 3 は i = 0 から 7 の8個だけを計算し、[0,1,3,2,6,7,5,4] を表示して終わります。1

  1. 同じ理由で、takeWhile (< 2 ^ n) grays と書いても止まります。最初に 2 ^ n 以上になるのは i = 2 ^ n の符号で、それより前の値はすべて 2 ^ n 未満だからです。