Tuple addition in pointfree

16

1

What is the shortest way we can express the function

f(a,b)(c,d)=(a+c,b+d)

in point-free notation?

pointfree.io gives us

uncurry (flip flip snd . (ap .) . flip flip fst . ((.) .) . (. (+)) . flip . (((.) . (,)) .) . (+))

which with a little bit of work can be shortened to

uncurry$(`flip`snd).((<*>).).(`flip`fst).((.).).(.(+)).flip.(((.).(,)).).(+)

for 76 bytes. But this still seems really long and complex for such a simple task. Is there any way we can express pairwise addition as a shorter point-free function?

To be clear by what I mean by point-free, a point-free declaration of a function involves taking existing functions and operators and applying them to each other in such a way that the desired function is created. Backticks, parentheses and literal values ([],0,[1..3], etc.) are allowed but keywords like where and let are not. This means:

  • You may not assign any variables/functions

  • You may not use lambdas

  • You may not import

Here is the same question when it was a CMC

Post Rock Garf Hunter

Posted 2017-12-29T17:04:06.257

Reputation: 55 382

9I never understood why it is called “point-free” when it is actually full of points. :P – Mr. Xcoder – 2017-12-29T17:10:19.117

What's considered an external library? Are imports from base allowed?

– Petr Pudlák – 2017-12-29T17:23:49.547

I think so. So no keywords are allowed at all? I'd suggest explicitly allowing literal values like 0 and the empty tuple. Also, your example uses backticks, it should be clear then that's allowed. – xnor – 2017-12-29T17:41:12.953

@xnor Literals are allowed, keywords are not. Thanks for asking for clarifications, hopefully everything is clear. – Post Rock Garf Hunter – 2017-12-29T17:44:37.567

5

It's a shame we're not allowed to import the best Haskell package, or else the solution would just be (+)***(+).

– Silvio Mayolo – 2017-12-30T03:05:00.243

2An idea: (+)<$>([1],2)<*>([3],4) gives ([1,3],6). – xnor – 2017-12-30T05:40:02.720

1

@SilvioMayolo Please add this to the tips for golfing in haskell! (and I invite you to join of monads and men :)

– flawr – 2017-12-30T10:29:56.153

2

I spent some time trying to craft a fine solution utilizing xnor's tip... but I ended up with this garbage. I don't even know why I try sometimes...

– totallyhuman – 2017-12-30T13:59:07.917

@flawr What is the meta consensus on using external packages? The package I referenced isn't part of base so it would have to be installed. – Silvio Mayolo – 2017-12-30T17:56:11.023

1@SilvioMayolo You are allowed to use packages. If it's not in base its a different language, that's all. – Post Rock Garf Hunter – 2017-12-30T17:57:37.597

If not for the import ban, I'd say Biapplicative was the way to go. – dfeuer – 2019-06-14T22:35:58.317

Answers

11

44 bytes

Got this from \x y -> (fst x + fst y, snd x + snd y)

(<*>).((,).).(.fst).(+).fst<*>(.snd).(+).snd

Try it online!

H.PWiz

Posted 2017-12-29T17:04:06.257

Reputation: 10 962

8

44 bytes

-8 bytes thanks to Ørjan Johansen. -3 bytes thanks to Bruce Forte.

(.).flip(.)<*>(zipWith(+).)$mapM id[fst,snd]

Try it online!

Translates to:

f t1 t2 = zipWith (+) (mapM id [fst, snd] $ t1) (mapM id [fst, snd] $ t2)

67 bytes

-8 bytes thanks to Ørjan Johansen. -1 byte thanks to Bruce Forte.

If tuple output is required:

(((,).head<*>last).).((.).flip(.)<*>(zipWith(+).)$mapM id[fst,snd])

Try it online!

Yup, me manually doing it doesn't produce ripe fruit. But I am happy with the [a] → (a, a) conversion.

listToPair ∷ [a] → (a, a)
listToPair = (,) . head <*> last
-- listToPair [a, b] = (a, b)

Now if there was a short function with m (a → b) → a → m b.

totallyhuman

Posted 2017-12-29T17:04:06.257

Reputation: 15 378

3Hate to break it to you, but mapM id[fst,snd] is shorter. – Ørjan Johansen – 2017-12-30T01:03:54.080

Sadly, mapM id is the golfed version of the function you're probably looking for, sequence. – Ørjan Johansen – 2017-12-30T02:06:26.473

Yeah, that's true. I'm just looking at (<*>)'s signature which is m (a → b) → m a → m b. So close... – totallyhuman – 2017-12-30T02:08:27.367

1There's also Control.Lens.??, which may have been proposed for inclusion in base at some point. – Ørjan Johansen – 2017-12-30T02:15:02.513

I want to extract the repeated (.mapM id[fst,snd]) like let r=(.mapM id[fst,snd]) in r(r.zipWith(+)), but I haven't been able to get the typechecker to accept a pointfree version. – xnor – 2017-12-30T02:55:13.853

@xnor It's monotyped if you drop the .. – Ørjan Johansen – 2017-12-30T03:35:10.247

4

60 bytes

I'm not seeing any uncurry love here, so I figured I'd pop in and fix that.

uncurry$(uncurry.).flip(.)(flip(.).(+)).(flip(.).((,).).(+))

I thought, with all of the fst and snd, that unpacking the arguments with uncurry might yield some results. Clearly, it was not as fruitful as I had hoped.

Silvio Mayolo

Posted 2017-12-29T17:04:06.257

Reputation: 1 817

2uncurry is so verbose. :( But you can replace the outermost parentheses with $. – Ørjan Johansen – 2017-12-30T03:39:32.563

Yeah, and that's unfortunately the issue with a lot of function names in Haskell. Just too long for golfing. But thanks for the 1-character savings! – Silvio Mayolo – 2017-12-30T05:07:43.330

4

54 bytes

I honestly doubt that we'll beat @H.PWiz's 44 bytes solution, but nobody was using the fact that (,) implements the type class Functor, so here's another interesting one which isn't too bad:

((<*>snd).((,).).(.fst).(+).fst<*>).flip(fmap.(+).snd)

Try it online!

Explanation

The implementation of the type class Functor for 2-Tuples are very similar to that of Either (from base-4.10.1.0):

instance Functor ((,) a) where
    fmap f (x,y) = (x, f y)

instance Functor (Either a) where
    fmap _ (Left x) = Left x
    fmap f (Right y) = Right (f y)

What this means for this challenge, is that the following function adds the second elements while keeping the first element of the second argument:

λ f = fmap.(+).snd :: Num a => (a, a) -> (a, a) -> (a, a)
λ f (1,-2) (3,-4)
(3,-6)

So if only we got some little helper helpPlz = \a b -> (fst a+fst b,snd b) we could do (helpPlz<*>).flip(fmap.(+).snd) and would be done. Luckily we have the tool pointfree which gives us:

helpPlz = (`ap` snd) . ((,) .) . (. fst) . (+) . fst

So by simply plugging that function back in we arrive at the above solution (note that (<*>) = ap which is in base).

ბიმო

Posted 2017-12-29T17:04:06.257

Reputation: 15 345