code.kerkeslager.com Git - sandbox/blob - elixir_primes/lib/primes.ex

   1 defmodule SieveFilter do
   2   def less_than?({a, _}, {b, _}) when a < b do true end
   3   def less_than?({a, b}, {a, c}) when b < c do true end
   4   def less_than?(_, _) do false end
   5
   6   def get_next({counter, prime}) do {counter + prime, prime} end
   7 end
   8
   9 defmodule Sieve do
  10   def run_item_through_sieve([{item, prime}|remaining_sieve], item) do
  11     {matched, unmatched} = run_item_through_sieve(remaining_sieve, item)
  12     {[{item, prime}|matched], unmatched}
  13   end
  14   def run_item_through_sieve(sieve, _) do {[], sieve} end
  15
  16   def merge(xs, []) do xs end
  17   def merge([], ys) do ys end
  18   def merge(xs, ys) do
  19     [x|remaining_xs] = xs
  20     [y|remaining_ys] = ys
  21
  22     if SieveFilter.less_than?(x, y) do
  23       [x|merge(remaining_xs, ys)]
  24     else
  25       [y|merge(xs, remaining_ys)]
  26     end
  27   end
  28
  29   def get_next(sieve) do
  30     Enum.map(sieve, &(SieveFilter.get_next(&1)))
  31   end
  32 end
  33
  34 defmodule Primes do
  35   def transform(sieve, previous_item) do
  36     item = previous_item + 1
  37     {matched, unmatched} = Sieve.run_item_through_sieve(sieve, item)
  38
  39     case matched do
  40       [] -> {Sieve.merge([{item * 2, item}], sieve), item}
  41       _ -> transform(Sieve.merge(Sieve.get_next(matched), unmatched), item)
  42     end
  43   end
  44
  45   def generate(initial_state, initial_item, get_next) do
  46     Stream.map(
  47       Stream.iterate(
  48         {initial_state, initial_item},
  49         fn({previous_state, previous_item}) -> get_next.(previous_state, previous_item) end
  50       ),
  51       fn({_, item}) -> item end
  52     )
  53   end
  54
  55   def primes() do
  56     Stream.drop(generate([], 1, &(transform(&1, &2))), 1)
  57   end
  58 end