A composition operator

[oxinabox]

In https://github.com/google-research/dex-lang/pull/35

@dougalm said:

This is calling out for a composition operator. I'm tempted to co-opt o for composition. Haskell uses . but we're already overloading that in a few places. Then we could write neg o f instead of defining a separate negf.

@oxinabox said

Yes. Julia uses ∘, and endowers the REPL (and all text editors via plugins) with ability to type that as \circ tab Could be interresting here. Could go with something like ($) or $$

---

Making this an issue so it doesn't get lost.

[dougalm]

Thanks for tracking the issue. I really like the way Haskell handles infix operators. You can use backticks for ad-hoc infix binary function application (x `f` y instead of f x y) and define your own infix symbols out of non-alphanumeric characters. Let's do the same. Then we can define ∘ purely in userspace.

[oxinabox]

I don't know that its possible to define multi-arg compose in Dex right now. At least my first attempt failed

compose:: (a->b)->(c->a)->(c->b)
compose f g x = f $ g $ x

b2rAlt = compose real b2i

:p b2rAlt True
> 1.0

ixkey2 :: A n::Ix m::Ix. Key -> n -> m -> Key
ixkey2 x i = ixkey $ ixkey x i

ixkey2Alt:: A n::Ix m::Ix. Key -> n -> m -> Key
ixkey2Alt = compose ixkey ixkey
> Type error:
Expected: (?_4 -> Key)
  Actual: (Key -> (?_10 -> Key))
In: ixkey

ixkey2Alt = compose ixkey ixkey
                          ^^^^^

The behavour I want is for compose f g to return a function that gives its arguments to g until its done, then to f

i,e a type signature that looks like (for the n-1, m arg case assuming n>3, m>2)

compose:: ..
    (f1->f2->f3->...->fn) ..
    ->(g1->g2->...->gm->f1) ..
    ->(g1->g2->...->gm->f2->f3->...->fn)

[dougalm]

Your first example, compose:: (a->b)->(c->a)->(c->b), is the normal way to do it. I just added it to the prelude. Using backticks for infix application, you can write f `compose` g. That's not as nice as f ∘ g but it'll do for now. Haskell-style custom infix operators are awesome but they complicate the parser quite a bit so we'll hold off on that for now.

The behavour I want is for compose f g to return a function that gives its arguments to g until its done, then to f

Yes, that does sound tricky to express in a Hindley-Milner-style type system. Part of the problem is that it's clear not what "until it's done" means because the arity of polymorphic functions isn't well defined. A function a -> b looks like it takes one argument, but if you instantiate b with Real -> Real suddenly it looks like it takes two.

[oxinabox]

Haskell-style custom infix operators are awesome but they complicate the parser quite a bit so we'll hold off on that for now.

I am rather dubious at the idea of being able to set the precidence of your operator. Feels to me like it would make reading code much harder.

For interest, julia defines a huge number of unicode operators to have a predefined precidence in the parser. https://github.com/JuliaLang/julia/blob/aa35ee2d30065803410718378e5673c7f845da62/src/julia-parser.scm And then defines that sub/super-scripts after them are infix operators with the same precidence.

julia> ∩ᵇᵃᵍ(x, y) = Bag(min(x[k], y[k]) for k in keys(x) ∩ keys(y))
∩ᵇᵃᵍ (generic function with 1 method)

Which has the advantage of making precidences clear (since mathematical symbols as operators tend to have natural precidence)

---

Yes, that does sound tricky to express in a Hindley-Milner-style type system. Part of the problem is that it's clear not what "until it's done" means because the arity of polymorphic functions isn't well defined. A function a -> b looks like it takes one argument, but if you instantiate b with Real -> Real suddenly it looks like it takes two.

oh, that's unfortunate.