extra/rosetta-code/hamming-lazy/hamming-lazy.factor

   1 ! Copyright (c) 2012 Anonymous
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: combinators fry kernel lists lists.lazy locals math ;
   4 IN: rosetta-code.hamming-lazy
   5
   6 ! http://rosettacode.org/wiki/Hamming_numbers#Factor
   7
   8 ! Hamming numbers are numbers of the form
   9 !    H = 2^i * 3^j * 5^k        where i, j, k >= 0
  10
  11 ! Hamming numbers are also known as ugly numbers and also
  12 ! 5-smooth numbers (numbers whose prime divisors are less or equal
  13 ! to 5).
  14
  15 ! Generate the sequence of Hamming numbers, in increasing order.
  16 ! In particular:
  17
  18 ! 1. Show the first twenty Hamming numbers.
  19 ! 2. Show the 1691st Hamming number (the last one below 231).
  20 ! 3. Show the one millionth Hamming number (if the language – or
  21 !    a convenient library – supports arbitrary-precision integers).
  22
  23 :: sort-merge ( xs ys -- result )
  24     xs car :> x
  25     ys car :> y
  26     {
  27         { [ x y < ] [ [ x ] [ xs cdr ys sort-merge ] lazy-cons ] }
  28         { [ x y > ] [ [ y ] [ ys cdr xs sort-merge ] lazy-cons ] }
  29         [ [ x ] [ xs cdr ys cdr sort-merge ] lazy-cons ]
  30     } cond ;
  31
  32 :: hamming ( -- hamming )
  33     f :> h!
  34     [ 1 ] [
  35         h 2 3 5 [ '[ _ * ] lazy-map ] tri-curry@ tri
  36         sort-merge sort-merge
  37     ] lazy-cons h! h ;
  38