--- /dev/null
+# The directory Mix will write compiled artifacts to.
+/_build
+
+# If you run "mix test --cover", coverage assets end up here.
+/cover
+
+# The directory Mix downloads your dependencies sources to.
+/deps
+
+# Where 3rd-party dependencies like ExDoc output generated docs.
+/doc
+
+# If the VM crashes, it generates a dump, let's ignore it too.
+erl_crash.dump
+
+# Also ignore archive artifacts (built via "mix archive.build").
+*.ez
--- /dev/null
+# Primes
+
+**TODO: Add description**
+
+## Installation
+
+If [available in Hex](https://hex.pm/docs/publish), the package can be installed as:
+
+ 1. Add `primes` to your list of dependencies in `mix.exs`:
+
+ ```elixir
+ def deps do
+ [{:primes, "~> 0.1.0"}]
+ end
+ ```
+
+ 2. Ensure `primes` is started before your application:
+
+ ```elixir
+ def application do
+ [applications: [:primes]]
+ end
+ ```
--- /dev/null
+# This file is responsible for configuring your application
+# and its dependencies with the aid of the Mix.Config module.
+use Mix.Config
+
+# This configuration is loaded before any dependency and is restricted
+# to this project. If another project depends on this project, this
+# file won't be loaded nor affect the parent project. For this reason,
+# if you want to provide default values for your application for
+# 3rd-party users, it should be done in your "mix.exs" file.
+
+# You can configure for your application as:
+#
+# config :primes, key: :value
+#
+# And access this configuration in your application as:
+#
+# Application.get_env(:primes, :key)
+#
+# Or configure a 3rd-party app:
+#
+# config :logger, level: :info
+#
+
+# It is also possible to import configuration files, relative to this
+# directory. For example, you can emulate configuration per environment
+# by uncommenting the line below and defining dev.exs, test.exs and such.
+# Configuration from the imported file will override the ones defined
+# here (which is why it is important to import them last).
+#
+# import_config "#{Mix.env}.exs"
--- /dev/null
+defmodule SieveFilter do
+ def less_than?({a, _}, {b, _}) when a < b do true end
+ def less_than?({a, b}, {a, c}) when b < c do true end
+ def less_than?(_, _) do false end
+
+ def get_next({counter, prime}) do {counter + prime, prime} end
+end
+
+defmodule Sieve do
+ def run_item_through_sieve([{item, prime}|remaining_sieve], item) do
+ {matched, unmatched} = run_item_through_sieve(remaining_sieve, item)
+ {[{item, prime}|matched], unmatched}
+ end
+ def run_item_through_sieve(sieve, _) do {[], sieve} end
+
+ def merge(xs, []) do xs end
+ def merge([], ys) do ys end
+ def merge(xs, ys) do
+ [x|remaining_xs] = xs
+ [y|remaining_ys] = ys
+
+ if SieveFilter.less_than?(x, y) do
+ [x|merge(remaining_xs, ys)]
+ else
+ [y|merge(xs, remaining_ys)]
+ end
+ end
+
+ def get_next(sieve) do
+ Enum.map(sieve, &(SieveFilter.get_next(&1)))
+ end
+end
+
+defmodule Primes do
+ def transform(sieve, previous_item) do
+ item = previous_item + 1
+ {matched, unmatched} = Sieve.run_item_through_sieve(sieve, item)
+
+ case matched do
+ [] -> {Sieve.merge([{item * 2, item}], sieve), item}
+ _ -> transform(Sieve.merge(Sieve.get_next(matched), unmatched), item)
+ end
+ end
+
+ def generate(initial_state, initial_item, get_next) do
+ Stream.map(
+ Stream.iterate(
+ {initial_state, initial_item},
+ fn({previous_state, previous_item}) -> get_next.(previous_state, previous_item) end
+ ),
+ fn({_, item}) -> item end
+ )
+ end
+
+ def primes() do
+ Stream.drop(generate([], 1, &(transform(&1, &2))), 1)
+ end
+end
--- /dev/null
+defmodule Primes.Mixfile do
+ use Mix.Project
+
+ def project do
+ [app: :primes,
+ version: "0.1.0",
+ elixir: "~> 1.3",
+ build_embedded: Mix.env == :prod,
+ start_permanent: Mix.env == :prod,
+ deps: deps()]
+ end
+
+ # Configuration for the OTP application
+ #
+ # Type "mix help compile.app" for more information
+ def application do
+ [applications: [:logger]]
+ end
+
+ # Dependencies can be Hex packages:
+ #
+ # {:mydep, "~> 0.3.0"}
+ #
+ # Or git/path repositories:
+ #
+ # {:mydep, git: "https://github.com/elixir-lang/mydep.git", tag: "0.1.0"}
+ #
+ # Type "mix help deps" for more examples and options
+ defp deps do
+ []
+ end
+end
--- /dev/null
+defmodule SieveFilterTest do
+ use ExUnit.Case
+ doctest SieveFilter
+
+ test "less_than? compares the counter first" do
+ assert SieveFilter.less_than?({10, 5}, {12, 3})
+ assert not SieveFilter.less_than?({12, 3}, {10, 5})
+ end
+
+ test "less_than? compares the prime second" do
+ assert SieveFilter.less_than?({10, 2}, {10, 5})
+ assert not SieveFilter.less_than?({10, 5}, {10, 2})
+ end
+
+ test "get_next adds the prime to the counter" do
+ assert SieveFilter.get_next({21, 7}) == {28, 7}
+ end
+end
+
+defmodule SieveTest do
+ use ExUnit.Case
+ doctest SieveFilter
+
+ test "run_item_through_sieve returns empty list and all filters for prime" do
+ sieve = [{8, 2}, {9, 3}, {10, 5}]
+ {matched, unmatched} = Sieve.run_item_through_sieve(sieve, 7)
+
+ assert matched == []
+ assert unmatched == sieve
+ end
+
+ test "run_item_through_sieve returns matched and unmatched filters for composite" do
+ sieve = [{10, 2}, {10, 5}, {12, 3}, {14, 7}]
+ {matched, unmatched} = Sieve.run_item_through_sieve(sieve, 10)
+
+ assert matched == [{10, 2}, {10, 5}]
+ assert unmatched == [{12, 3}, {14, 7}]
+ end
+
+ test "merge merges sieves" do
+ sieve_a = [{12, 2}, {15, 5}]
+ sieve_b = [{12, 3}, {14, 7}]
+ merged = Sieve.merge(sieve_a, sieve_b)
+
+ assert merged == [{12, 2}, {12, 3}, {14, 7}, {15, 5}]
+ end
+
+ test "get_next updates filters" do
+ sieve = [{42, 2}, {42, 3}, {42, 7}]
+
+ assert Sieve.get_next(sieve) == [{44, 2}, {45, 3}, {49, 7}]
+ end
+end
+
+defmodule PrimesTest do
+ use ExUnit.Case
+ doctest Primes
+
+ test "transform updates sieve and next item" do
+ sieve = [{8, 2}, {9, 3}, {10, 5}, {14, 7}]
+ item = 7
+
+ {next_sieve, next_item} = Primes.transform(sieve, item)
+
+ assert next_sieve == [{12, 2}, {12, 3}, {14, 7}, {15, 5}, {22, 11}]
+ assert next_item == 11
+ end
+
+ test "generate iterates updating state and yielding items" do
+ fibonacci = Primes.generate(0, 1, fn(prev, curr) -> {curr, prev + curr} end)
+
+ assert Enum.take(fibonacci, 10) == [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
+ end
+
+ test "primes generates primes" do
+ assert Enum.take(Primes.primes(), 10) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
+ end
+
+ test "primes is fast" do
+ assert 1 == Enum.sum(Stream.take_while(Primes.primes(), &(&1 < 2_000_000)))
+ end
+end
--- /dev/null
+ExUnit.start()
projects / sandbox / commitdiff