Julia `Bind`, defer evaluation for some symbolic reasoning

curry.jl

# See https://github.com/JuliaLang/julia/pull/36180

using Base: tail
interleave(bind::Tuple{}, args::Tuple{}) = ()
interleave(bind::Tuple{}, args::Tuple) = error("more args than positions")
interleave(bind, args) = _interleave(first(bind), tail(bind), args)

# `nothing` indicates a position to be bound
_interleave(firstbind::Nothing, tailbind::Tuple, args::Tuple) = (
  first(args), interleave(tailbind, tail(args))...)

# allow escaping of e.g. `nothing`
_interleave(firstbind::Some{T}, tailbind::Tuple, args::Tuple) where T = (
  something(firstbind), interleave(tailbind, args)...)

_interleave(firstbind::T, tailbind::Tuple, args::Tuple) where T = (
  firstbind, interleave(tailbind, args)...)

struct Bind{F, A}
  f::F
  a::A
end

function (c::Bind)(args...)
  c.f(interleave(c.a, args)...)
end

is3 = Bind(==, (3, nothing))
isnothing2 = Bind(===, (Some(nothing), nothing))


"""
`@bind f(a,b)` is equivalent to `Bind(f, (a, b))`
"""
macro bind(ex)
    ex.head == :call || error()
    f = ex.args[1]
    x = tuple(ex.args[2:end]...)
    quote
        Bind($(f), ($(esc(x[1])), $(esc(x[2])))) # TODO how to use splatting to generalize to n arguments
    end
end

#=
example replacement of Rational
=#

using Base: divgcd

function Base.:*(x::Bind{typeof(/), Tuple{N1, D1}}, y::Bind{typeof(/), Tuple{N2, D2}}) where {N1, D1, N2, D2}
  xn, yd = divgcd(x.a[1], y.a[2])
  xd, yn = divgcd(x.a[2], y.a[1])
  @bind (xn * yn) / (xd * yd) # TODO use `unsafe_rational` and `checked_mul`
end

"""
julia> (@bind 1/3) * (@bind 3/2)
Bind{typeof(/),Tuple{Int64,Int64}}(/, (1, 2))
"""


#=
example deferring `Set` operations
=#

"""Produce a "useful" bound, in the sense that `x ∈ input` implies `x ∈ result_type`"""
function bounding(result_type, input) end

bounding(::Type{>:UnitRange}, v::Vector{<:Integer}) = UnitRange(extrema(v)...)
# bounding(URT::Type{UnitRange{T}}, v::Vector{<:Integer}) where T<:Integer = URT(extrema(v)...)

function bounding(::Type{>:UnitRange}, _union::Bind{typeof(union), Tuple{UnitRange{T}, UnitRange{T}}}) where T <: Integer
    (a, b) = _union.a
    UnitRange(min(minimum(a), minimum(b)), max(maximum(a), maximum(b)))
end

# eagerly generates intermediate representation of `union(1:3,5:7)`
bounding(UnitRange, union(1:3,5:7))
# use specialized method for bounding unions of `UnitRange`s
bounding(UnitRange, @bind union(1:3,5:7))