import TypeClass
defclass Witchcraft.Foldable do
@moduledoc """
Data that can be folded over to change its structure by altering or combining elements.
Unlike `Witchcraft.Functors`s, the end result will not respect the original structure
unless you build it back up manually.
## 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.{Apply, Ord, Monad, Monoid, Semigroup, Unit}
import Kernel, except: [length: 1, max: 2, min: 2, then: 2]
import Exceptional.Safe, only: [safe: 1]
require Foldable.EmptyError
use Witchcraft.Internal, overrides: [min: 2, max: 2, length: 1], deps: [Semigroup, Ord]
use Witchcraft.Applicative
use Quark
@type t :: any()
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
iex> sum.([1, 2, 3])
6
iex> 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
|> Witchcraft.Foldable.right_fold(seed, f)
|> g.()
right =
foldable
|> g.()
|> Witchcraft.Foldable.right_fold(seed, fn x, acc -> f.(g.(x), acc) 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
iex> sum.([1, 2, 3])
6
iex> sum.([4, 5, 6])
15
iex> left_fold([1, 2, 3], [], fn(acc, x) -> [x | acc] end)
[3, 2, 1]
iex> left_fold({1, 2, 3}, [], fn(acc, x) -> [x | acc] end)
[3]
iex> left_fold([1, 2, 3], [4, 5, 6], fn(acc, x) -> [x | acc] end)
[3, 2, 1, 4, 5, 6]
Note the reducer argument order versus `right_fold/3`
iex> right_fold([1, 2, 3], [], fn(acc, x) -> [acc | x] end)
[1, 2, 3]
iex> left_fold([1, 2, 3], [], fn(acc, x) -> [acc | x] end)
[[[[] | 1] | 2] | 3]
"""
@spec left_fold(Foldable.t(), any(), (any(), any() -> any())) :: any()
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(acc, x) -> [x | acc] end)
[3, 2, 1]
Note the reducer argument order versus `right_fold/2`
iex> right_fold([100, 20, 10], &//2)
200.0
iex> left_fold([100, 20, 10], &//2)
0.5
"""
@spec left_fold(Foldable.t(), (any(), any() -> any())) :: any()
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})
[1, 2, 3]
"""
@spec to_list(Foldable.t()) :: [any()]
def to_list(list) when is_list(list), do: list
def to_list(tuple) when is_tuple(tuple), do: Tuple.to_list(tuple)
def to_list(string) when is_bitstring(string), do: String.to_charlist(string)
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
iex> 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)
true
iex> member?(%{a: 1, b: 2}, 99)
false
"""
@spec member?(Foldable.t(), any()) :: boolean()
def member?(list, target) when is_list(list), do: Enum.member?(list, target)
def member?(map, target) when is_map(map), do: map |> Map.values() |> Enum.member?(target)
def member?(tuple, target) when is_tuple(tuple) do
tuple
|> Tuple.to_list()
|> Enum.member?(target)
end
def member?(string, target) when is_bitstring(string) do
string
|> String.to_charlist()
|> Enum.member?(target)
end
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 -> Ord.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
iex> max([2, 3, 1])
3
iex> 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() -> Ord.t())) :: any()
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
iex> min([2, 3, 1])
1
iex> 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)
@doc """
Get a random element from a foldable structure.
## Examples
random([1, 2, 3])
#=> 1
random([1, 2, 3])
#=> 3
random(%BinaryTree{left: %Empty{}, node: 2, right: %BinaryTree{node: 1}})
1
"""
@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
iex> sum({1, 2, 3})
3
%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
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> flatten([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
[1, 2, 3, 4, 5, 6, 7, 8, 9]
iex> flatten({[1, 2, 3], [4, 5, 6], [7, 8, 9]})
[7, 8, 9]
%BinaryTree{
left: [1, 2, 3],
right: %BinaryTree{
left: [4, 5],
right: [6]
}
}
|> flatten()
#=> [1, 2, 3, 4, 5, 6]
"""
@spec flatten(Foldable.t()) :: [any()]
def flatten(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> flat_map([1, 2, 3, 4, 5, 6], fn x -> [x, x] end)
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6]
iex> flat_map({1, 2, 3, 4, 5, 6}, fn x -> [x, x] end)
[6, 6]
%BinaryTree{
left: 1,
right: %BinaryTree{
left: 2,
right: 3
}
}
|> flat_map(fn x -> [x, x] end)
#=> [1, 1, 2, 2, 3, 3]
"""
@spec flat_map(Foldable.t(), (any() -> [any()])) :: [any()]
def flat_map(foldable, mapper) do
foldable
|> right_fold([], fn inner_focus, acc ->
[mapper.(inner_focus) | acc]
end)
|> flatten()
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
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
iex> 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
Not that the `Tuple` instance behaves somewhat conterintuitively
iex> any? {true, true, false}
false
iex> any? {true, false, true}
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
iex> 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{}
]
iex> then_sequence({{1, 2, 3}, {4, 5, 6}})
{4, 5, %Witchcraft.Unit{}}
iex> then_sequence({[1, 2, 3], [4, 5, 6]})
[
%Witchcraft.Unit{},
%Witchcraft.Unit{},
%Witchcraft.Unit{}
]
"""
@spec then_sequence(Foldable.t()) :: Monad.t()
def then_sequence(foldable_monad) do
seed =
foldable_monad
|> to_list()
|> hd()
|> of(%Unit{})
right_fold(foldable_monad, seed, &Witchcraft.Apply.then/2)
end
@doc """
`traverse` actions over data, but ignore the results.
Not a typo: this is in the correct module, since it doens't depend directly
on `Witchcraft.Traversable`, but behaves in a similar manner.
## Examples
iex> [1, 2, 3]
...> |> then_traverse(fn x -> [x, x * 5, x * 10] end)
[
#
%Witchcraft.Unit{}, %Witchcraft.Unit{}, %Witchcraft.Unit{},
%Witchcraft.Unit{}, %Witchcraft.Unit{}, %Witchcraft.Unit{},
%Witchcraft.Unit{}, %Witchcraft.Unit{}, %Witchcraft.Unit{},
#
%Witchcraft.Unit{}, %Witchcraft.Unit{}, %Witchcraft.Unit{},
%Witchcraft.Unit{}, %Witchcraft.Unit{}, %Witchcraft.Unit{},
%Witchcraft.Unit{}, %Witchcraft.Unit{}, %Witchcraft.Unit{},
#
%Witchcraft.Unit{}, %Witchcraft.Unit{}, %Witchcraft.Unit{},
%Witchcraft.Unit{}, %Witchcraft.Unit{}, %Witchcraft.Unit{},
%Witchcraft.Unit{}, %Witchcraft.Unit{}, %Witchcraft.Unit{}
]
"""
@spec then_traverse(Foldable.t(), Apply.fun()) :: Apply.t()
def then_traverse(foldable, fun) do
right_fold(foldable, of(foldable, %Unit{}), fn step, acc ->
step
|> fun.()
|> Witchcraft.Apply.then(acc)
end)
end
@doc """
The same as `then_traverse`, but with the arguments flipped.
## Examples
iex> fn x -> [x, x * 5, x * 10] end
...> |> then_through([1, 2, 3])
[
#
%Witchcraft.Unit{}, %Witchcraft.Unit{}, %Witchcraft.Unit{},
%Witchcraft.Unit{}, %Witchcraft.Unit{}, %Witchcraft.Unit{},
%Witchcraft.Unit{}, %Witchcraft.Unit{}, %Witchcraft.Unit{},
#
%Witchcraft.Unit{}, %Witchcraft.Unit{}, %Witchcraft.Unit{},
%Witchcraft.Unit{}, %Witchcraft.Unit{}, %Witchcraft.Unit{},
%Witchcraft.Unit{}, %Witchcraft.Unit{}, %Witchcraft.Unit{},
#
%Witchcraft.Unit{}, %Witchcraft.Unit{}, %Witchcraft.Unit{},
%Witchcraft.Unit{}, %Witchcraft.Unit{}, %Witchcraft.Unit{},
%Witchcraft.Unit{}, %Witchcraft.Unit{}, %Witchcraft.Unit{}
]
"""
@spec then_through(Apply.fun(), Foldable.t()) :: Apply.t()
def then_through(fun, traversable), do: then_traverse(traversable, fun)
end
