18
\$\begingroup\$

I'm trying to make a pointfree function f that can act like APL's dyadic forks/Husk's §, so f g h i a b equals g (h a) (i b), where g is a binary function, h and i are unary functions, and a and b are integers (I'm only dealing with integers and not other types right now). I converted the function to pointfree in the following steps, but it's 26 bytes with a lot of parentheses and periods and even a flip, so I'd like to know how to golf it.

f g h i a b=g(h a)(i b)
f g h i=(.i).g.h
f g h=(.g.h).(.)
f g=(.(.)).(flip(.)).(g.)
f=((.(.)).).((flip(.)).).(.)

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ Plugging into pointfree.io gives an 20-byter ((flip.((.).)).).(.). \$\endgroup\$
    – Bubbler
    Aug 4, 2021 at 23:21
  • \$\begingroup\$ @Bubbler ...Oh. Can you put that as an answer, with an explanation of how it works? It'd be very helpful. \$\endgroup\$
    – user
    Aug 4, 2021 at 23:22
  • 3
    \$\begingroup\$ The reason I wrote it in a comment is that I don't know how it works :P Btw, should the arguments be ordered exactly like that? \$\endgroup\$
    – Bubbler
    Aug 4, 2021 at 23:22

1 Answer 1

15
\$\begingroup\$

18 bytes

(flip.).(.).((.).)

Try it online!

Since your function has no argument repetition and no argument deletion, it essentially becomes a BC calculus golf (in Haskell terms, a golf using just B=(.) and C=flip). I will use B and C combinators and convert to Haskell code later.

\g h i a b -> g (h a) (i b)
\g h i a -> B (g (h a)) i
\g h i -> C (\a -> B (g (h a))) i
\g h -> C (\a -> B (g (h a)))

-- choice 1
\g h -> C (B B (B g h))
-- choice 1.1
\g -> B C (B (B B) (B g))
B C.B (B B).B
(flip.).(((.).).).(.)  -- 21 bytes
-- choice 1.2
\g -> B (B C (B B)) (B g)
B (B C (B B)).B
((flip.((.).)).).(.)  -- 20 bytes; pointfree.io

-- choice 2
\g h -> C (B (B B g) h)
\g -> B C (B (B B g))
B C.B.B B
(flip.).(.).((.).)  -- 18 bytes; shortest

As a bonus, if you can swap i and a in the definition of f, it becomes an ordered LC and allows a very short form using just (.):

\g h a i b -> g (h a) (i b)
\g h a i -> B (g (h a)) i
\g h a -> B (g (h a))
\g h -> B (B B g) h
\g -> B (B B g)
B B (B B)
(.).((.).)  -- 10 bytes
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Excellent answer. It seems like a mechanical process of enumeration. Why is pointfree.io not able to find the shortest one? Is the original insight that the problem was equivalent to a BC calculus golf the stumbling block? \$\endgroup\$
    – Jonah
    Aug 5, 2021 at 0:27
  • 4
    \$\begingroup\$ @Jonah The primary reason is that a.b.c can be both (a.b).c and a.(b.c), which give different results at the end. I'm pretty sure pointfree.io uses only one of the possible abstractions to get some correct result. \$\endgroup\$
    – Bubbler
    Aug 5, 2021 at 0:34
  • \$\begingroup\$ what does "BC calculus" mean? Where can I find more info to learn about it? \$\endgroup\$ Aug 5, 2021 at 17:23
  • \$\begingroup\$ B and C are combinators, i.e. essentially functions that are used in a system with no explicit variables. Asking for a point-free definition of a function is more or less asking for a definition in terms of combinators. BC calculus is simply the system you get if you allow combinators B and C (+ applications) only. \$\endgroup\$
    – zale
    Aug 5, 2021 at 20:36
  • \$\begingroup\$ @NooneAtAll To add to zale's comment, BC calculus is equivalent to linear logic/linear lambda calculus where each argument is used exactly once in some order. \$\endgroup\$
    – Bubbler
    Aug 6, 2021 at 0:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.