import TypeClass

defclass Witchcraft.Foldable do
  @moduledoc """
  Data that can be folded over to change its structure by altering or combining elements

  ## Examples

      iex> right_fold([1, 2, 3], 0, &+/2) # sum
      6

  ## Properties

  People are working on Foldable properties. This is one of the exceptions to
  there needing to conform to properties. In the meantime, we are testing that
  naturality is preserved, which is be a free theorm.

  If that fails, something is very wrong with the instance.

  ## Type Class

  An instance of `Witchcraft.Foldable` define `Witchcraft.Foldable.right_fold/3`.

      Foldable   [right_fold/3]
  """

  alias __MODULE__
  alias Witchcraft.{Ord, Monad, Monoid, Semigroup, Unit}

  import Kernel, except: [length: 1, max: 2, min: 2]
  import Exceptional.Safe, only: [safe: 1]

  require Foldable.EmptyError

  use Witchcraft.Applicative
  use Quark

  @type t :: any()

  defmacro __using__(opts \\ []) do
    {:ok, new_opts} =
      Keyword.get_and_update(opts, :except, fn except ->
        {:ok, [length: 1, max: 2, min: 2] ++ (except || [])}
      end)

    if Access.get(opts, :override_kernel, true) do
      quote do
        import Kernel,               unquote(new_opts)
        import Witchcraft.Semigroup, unquote(opts)
        import Witchcraft.Ord,       unquote(opts)
        import unquote(__MODULE__),  unquote(opts)
      end
    else
      quote do
        import Witchcraft.Semigroup, unquote(opts)
        import Witchcraft.Ord,       unquote(opts)
        import unquote(__MODULE__),  unquote(new_opts)
      end
    end
  end

  where do
    @doc ~S"""
    Right-associative fold over a structure to alter the structure and/or reduce
    it to a single summary value. The right-association makes it possible to
    cease computation on infinite streams of data.

    The folder must be a binary function, with the second argument being the
    accumulated value thus far.

    ## Examples

        iex> sum = fn xs -> right_fold(xs, 0, &+/2) end
        ...> sum.([1, 2, 3])
        6
        ...> sum.([4, 5, 6])
        15

    """
    @spec right_fold(Foldable.t(), any(), ((any(), any()) -> any())) :: any()
    def right_fold(foldable, seed, folder)
  end

  properties do
    # Free theorm
    def naturality(data) do
      foldable = generate(data)
      seed     = "seed"

      f = &Quark.constant/2
      g = &Quark.id/1

      left =
        foldable
        |> Foldable.right_fold(seed, f)
        |> g.()

      right =
        foldable
        |> g.()
        |> Witchcraft.Foldable.right_fold(fn(x, acc) -> f.((g.(acc)), x) end)

      equal?(left, right)
    end
  end

  @doc ~S"""
  The same as `right_fold/3`, but uses the first element as the seed

  ## Examples

      iex> right_fold([1, 2, 3], &+/2)
      6

      iex> right_fold([100, 2, 5], &//2)
      40.0 # (2 / (5 / 100))

      iex> right_fold([[], 1, 2, 3], fn(x, acc) -> [x | acc] end)
      [1, 2, 3]

  """
  @spec right_fold(Foldable.t(), fun()) :: any()
  def right_fold(foldable, folder) do
    case to_list(foldable) do
      []       -> []
      [a | as] -> right_fold(as, a, folder)
    end
  end

  @doc ~S"""
  Left-associative fold over a structure to alter the structure and/or reduce
  it to a single summary value.

  The folder must be a binary function, with the second argument being the
  accumulated value thus far.

  ## Examples

      iex> sum = fn xs -> right_fold(xs, 0, &+/2) end
      ...> sum.([1, 2, 3])
      6
      ...> sum.([4, 5, 6])
      15

      iex> left_fold([1, 2, 3], [], fn(x, acc) -> [x | acc] end)
      [[[[] | 1] | 2] | 3]

  """
  def left_fold(foldable, seed, folder) do
    right_fold(foldable, &Quark.id/1, fn(b, g) ->
      fn(x) ->
        x
        |> folder.(b)
        |> g.()
      end
    end).(seed)
  end

  @doc ~S"""
  The same as `left_fold/3`, but uses the first element as the seed

  ## Examples

      iex> left_fold([1, 2, 3], &+/2)
      6

      iex> left_fold([100, 2, 5], &//2)
      10.0 # ((100 / 2) / 5)

      iex> left_fold([1 | [2 | [3]]], fn(x, acc) -> [x | acc] end)
      [[1 | 2] | 3]

  """
  def left_fold(foldable, folder) do
    [x | xs] = to_list(foldable)
    left_fold(xs, x, folder)
  end

  @doc """
  Combine all elements using monoidal append

  ## Examples

      iex> fold([1, 2, 3])
      6

      iex> fold([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
      [1, 2, 3, 4, 5, 6, 7, 8, 9]

  """
  @spec fold(Foldable.t()) :: any()
  def fold(foldable), do: left_fold(foldable, &Semigroup.append/2)

  @doc """
  Map a functional over all elements and `fold` them together

  ## Examples

      iex> fold_map([1, 2, 3], fn x -> [x, x * 10] end)
      [1, 10, 2, 20, 3, 30]

      iex> fold_map([[1, 2, 3], [4, 5, 6], [7, 8, 9]], fn x -> [x, x] end)
      [
        [1, 2, 3], [1, 2, 3],
        [4, 5, 6], [4, 5, 6],
        [7, 8, 9], [7, 8, 9]
      ]

  """
  @spec fold_map(Foldable.t(), fun()) :: any()
  def fold_map(foldable, fun) do
    right_fold(foldable, Monoid.empty(foldable), fn(element, acc) ->
      element
      |> fun.()
      |> Semigroup.append(acc)
    end)
  end

  @doc """
  Turn any `Foldable` into a `List`

  ## Example

      iex> to_list({1, 2, 3})
      [1, 2, 3]

      iex> to_list(%{a: 1, b: 2, c: 3})
      [c: 3, b: 2, a: 1]

  """
  @spec to_list(Foldable.t()) :: [any()]
  def to_list(foldable), do: right_fold(foldable, [], fn(x, acc) -> [x | acc] end)

  @doc """
  Check if a foldable data structure is empty

  ## Examples

      iex> empty?("")
      true

      iex> empty?("hi")
      false

      iex> empty?(%{})
      true

  """
  @spec empty?(Foldable.t()) :: boolean
  def empty?(foldable), do: right_fold(foldable, true, fn(_focus, _acc) -> false end)

  @doc """
  Count the number of elements in a foldable structure

  ## Examples

      iex> use Witchcraft.Foldable
      ...> length(%{})
      0
      iex> length(%{a: 1, b: 2})
      2
      iex> length("ࠀabc")
      4

  """
  @spec length(Foldable.t()) :: non_neg_integer()
  def length(list) when is_list(list), do: Kernel.length(list)
  def length(foldable), do: right_fold(foldable, 0, fn(_, acc) -> 1 + acc end)

  defalias count(foldable), as: :length
  defalias size(foldable),  as: :length

  @doc """
  Check if a foldable structure contains a particular element

  ## Examples

      iex> member?([1, 2, 3], 2)
      true

      iex> member?([1, 2, 3], 99)
      false

      iex> member?(%{a: 1, b: 2}, 2)
      false

      iex> member?(%{a: 1, b: 2}, {:b, 2})
      true

  """
  @spec member?(Foldable.t(), any()) :: boolean()
  def member?(foldable, target) do
    right_fold(foldable, false, fn(focus, acc) -> acc or (focus == target) end)
  end

  @doc """
  Find the maximum element in a foldable structure using a custom comparitor

  Elements must implement `Witchcraft.Ord`.

  Comes in both a safe and unsafe(`!`) version

  ## Examples

      iex> use Witchcraft.Foldable
      ...> [1, 2, 7]
      ...> |> max(by: fn(x, y) ->
      ...>   x
      ...>   |> Integer.mod(3)
      ...>   |> Witchcraft.Ord.compare(Integer.mod(y, 3))
      ...> end)
      2

  """
  @spec max(Foldable.t(), by: ((any, any) -> Order.ordering())) :: Ord.t()
  def max(foldable, by: comparator) do
    Witchcraft.Foldable.right_fold(foldable, fn(focus, acc) ->
      case comparator.(focus, acc) do
        :greater -> focus
        _ -> acc
      end
    end)
  end

  @doc """
  Find the maximum element in a foldable structure using the default ordering
  from `Witchcraft.Ord`.

  Elements must implement `Witchcraft.Ord`.

  ## Examples

      iex> use Witchcraft.Foldable
      ...> max([2, 3, 1])
      3
      ...> max([[4], [1, 2, 3, 4]])
      [4]

      %BinaryTree{
        node: 1,
        left: %BinaryTree{
          node: 3
          left: 4
        },
        right: 2
      }
      |> max()
      #=> 4

  """
  @spec max(Foldable.t()) :: Ord.t()
  def max(foldable_comparable), do: max(foldable_comparable, by: &Ord.compare/2)

  @doc """
  Find the maximum element in a foldable structure using a custom comparitor

  Elements must implement `Witchcraft.Ord`.

  Comes in both a safe and unsafe(`!`) version

  ## Examples

      iex> use Witchcraft.Foldable
      ...> [8, 2, 1]
      ...> |> min(by: fn(x, y) ->
      ...>   x
      ...>   |> Integer.mod(4)
      ...>   |> Witchcraft.Ord.compare(Integer.mod(y, 4))
      ...> end)
      8

  """
  @spec min(Foldable.t(), by: ((any(), any()) -> Order.t())) :: any() | Maybe.t()
  def min(foldable, by: comparitor) do
    right_fold(foldable, fn(focus, acc) ->
      case comparitor.(focus, acc) do
        :lesser -> focus
        _ -> acc
      end
    end)
  end

  @doc """
  Find the minimum element in a foldable structure using the default ordering
  from `Witchcraft.Ord`.

  Elements must implement `Witchcraft.Ord`.

  ## Examples

      iex> use Witchcraft.Foldable
      ...> min([2, 3, 1])
      1
      ...> min([[4], [1, 2, 3, 4]])
      [1, 2, 3, 4]

      %BinaryTree{
        node: 4,
        left: %BinaryTree{
          node: 3
          left: 1
        },
        right: 2
      }
      |> min()
      #=> 1

  """
  def min(foldable), do: min(foldable, by: &Ord.compare/2)

  @spec random(Foldable.t()) :: any() | Foldable.EmptyError.t()
  def random(foldable) do
    foldable
    |> to_list
    |> safe(&Enum.random/1).()
    |> case do
         %Enum.EmptyError{} -> Foldable.EmptyError.new(foldable)
         value -> value
       end
  end

  @doc ~S"""
  Sum all numbers in a foldable

  ## Examples

      iex> sum([1, 2, 3])
      6

      %BinaryTree{
        left:  4,
        right: %BinaryTree{
          left: 2,
          right: 10
        }
      } |> sum()
      #=> 16

  """
  @spec sum(Foldable.t()) :: number()
  def sum(foldable), do: right_fold(foldable, 0, &+/2)

  @doc ~S"""
  Product of all numbers in a foldable

  ## Examples

      iex> product([1, 2, 3])
      6

      %BinaryTree{
        left:  4,
        right: %BinaryTree{
          left: 2,
          right: 10
        }
      }
      |> product()
      #=> 80

  """
  @spec product(Foldable.t()) :: number()
  def product(foldable), do: right_fold(foldable, &*/2)

  @doc ~S"""
  Concatenate all lists in a foldable structure

  ## Examples

      iex> concat([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
      [1, 2, 3, 4, 5, 6, 7, 8, 9]

      %BinaryTree{
        left:  [1, 2, 3],
        right: %BinaryTree{
          left:  [4, 5],
          right: [6]
        }
      }
      |> concat()
      #=> [1, 2, 3, 4, 5, 6]

  """
  @spec concat(Foldable.t()) :: [any()]
  def concat(contained_lists) do
    right_fold(contained_lists, [], &Semigroup.append/2)
  end

  @doc ~S"""
  Lift a function over a foldable structure generating lists of results,
  and then concatenate the resulting lists

  ## Examples

      iex> concat_map([1, 2, 3, 4, 5, 6], fn x -> [x, x] end)
      [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6]

      %BinaryTree{
        left:  1,
        right: %BinaryTree{
          left:  2,
          right: 3
        }
      }
      |> concat_map(fn x -> [x, x] end)
      #=> [1, 1, 2, 2, 3, 3]

  """
  @spec concat_map(Foldable.t(), (any() -> [any()])) :: [any()]
  def concat_map(foldable, mapper) do
    foldable
    |> right_fold([], fn(inner_focus, acc) ->
      [mapper.(inner_focus) | acc]
    end)
    |> concat()
  end

  @doc """
  Test whether the structure is empty. The default implementation is
  optimized for structures that are similar to lists, because there
  is no general way to do better.

  ## Examples

      iex> null?([])
      true

      iex> null?([1, 2, 3])
      false

  """
  @spec null?(Foldable.t()) :: boolean()
  def null?(foldable), do: right_fold(foldable, true, fn(_, _) -> false end)

  @doc ~S"""
  Check if a foldable is full of only `true`s

  ## Examples

      iex> all?([true, true, false])
      false

      %BinaryTree{
        left:  true,
        right: %BinaryTree{
          left:  true,
          right: false
        }
      } |> all?()
      #=> false

  """
  @spec all?(Foldable.t()) :: boolean()
  def all?(foldable_bools), do: right_fold(foldable_bools, true, &and/2)

  @doc ~S"""
  The same as `all?/1`, but with a custom predicate matcher

  ## Examples

      iex> import Integer
      ...> all?([1, 2, 3], &is_odd/1)
      false

      %BinaryTree{
        left:  1,
        right: %BinaryTree{
          left:  2,
          right: 3
        }
      }
      |> all?(&Integer.is_odd?/1)
      #=> false

  """
  @spec all?(Foldable.t(), (any() -> boolean())) :: boolean()
  def all?(foldable, predicate) do
    right_fold(foldable, true, fn(focus, acc) -> predicate.(focus) and acc end)
  end

  @doc ~S"""
  Check if a foldable contains any `true`s

  ## Examples

      iex> any? [true, true, false]
      true

      %BinaryTree{
        left:  true,
        right: %BinaryTree{
          left:  true,
          right: false
        }
      } |> any?()
      #=> true

  """
  @spec any?(Foldable.t()) :: boolean()
  def any?(foldable_bools), do: right_fold(foldable_bools, false, &or/2)

  @doc ~S"""
  The same as `all?/1`, but with a custom predicate matcher

  ## Examples

      iex> require Integer
      ...> any?([1, 2, 3], &Integer.is_odd/1)
      true

      %BinaryTree{
        left:  1,
        right: %BinaryTree{
          left:  2,
          right: 3
        }
      }
      |> any(&Integer.is_odd?/1)
      #=> true

  """
  @spec any?(Foldable.t(), (any() -> boolean())) :: boolean()
  def any?(foldable, predicate) do
    right_fold(foldable, false, fn(focus, acc) -> predicate.(focus) or acc end)
  end

  @doc """
  Run each action from left to right, discarding all values.

  Always returns `%Witchcraft.Unit{}` in the same foldbale structure that you started with.

  ## Examples

      iex> then_sequence([[1, 2, 3], [4, 5, 6]])
      [
        %Witchcraft.Unit{},
        %Witchcraft.Unit{},
        %Witchcraft.Unit{},
        %Witchcraft.Unit{},
        %Witchcraft.Unit{},
        %Witchcraft.Unit{},
        %Witchcraft.Unit{},
        %Witchcraft.Unit{},
        %Witchcraft.Unit{}
      ]

  """
  @spec then_sequence(Foldable.t()) :: Monad.t()
  def then_sequence(foldable_monad) do
    right_fold(foldable_monad, of(foldable_monad, %Unit{}), &then/2)
  end
end