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