rosetta/hamming_numbers.bruijn

:import std/Combinator .
:import std/Number .
:import std/List .

merge y [[[∅?1 0 (1 [[2 [[go]]]])]]]
	go 3 <? 1 (3 : (6 2 4)) (1 : (6 5 0))

# classic version while avoiding duplicate generation
hammings-classic (+1) : (foldr u empty ((+2) : ((+3) : {}(+5))))
	u [[y [merge 1 ((mul 2) <$> ((+1) : 0))]]]

:test ((hammings-classic !! (+42)) =? (+162)) ([[1]])

# enumeration by a chain of folded merges (faster)
hammings-folded ([(0 ∘ a) ∘ (0 ∘ b)] (foldr merge1 empty)) $ c
	merge1 [[1 [[1 : (merge 0 2)]]]]
	a iterate (map (mul (+5)))
	b iterate (map (mul (+3)))
	c iterate (mul (+2)) (+1)

:test ((hammings-folded !! (+42)) =? (+162)) ([[1]])

# --- output ---

main [first-twenty : (n1691 : {}n1000000)]
	first-twenty take (+20) hammings-folded
	n1691 hammings-folded !! (+1690)
	n1000000 hammings-folded !! (+999999)