diff options
Diffstat (limited to 'samples/rosetta/hamming_numbers.bruijn')
| -rw-r--r-- | samples/rosetta/hamming_numbers.bruijn | 28 |
1 files changed, 28 insertions, 0 deletions
diff --git a/samples/rosetta/hamming_numbers.bruijn b/samples/rosetta/hamming_numbers.bruijn new file mode 100644 index 0000000..426223d --- /dev/null +++ b/samples/rosetta/hamming_numbers.bruijn @@ -0,0 +1,28 @@ +: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) |