Convert pointfree to pointful

9

Being a Haskell hacker, I prefer pointfree notation over pointful. Unfortunately some people find pointfree notation hard to read, and I find it hard to get the correct number of parentheses when I write in pointful. Help me convert code written in pointfree to pointful notation!

About

In pointfree notation we use points (yes, really) to feed the output of one function into another. Say, if you had a function succ that takes a number and adds 1 to it, and you wanted to make a function that adds 3 to a number, instead of doing this:

\x -> succ(succ(succ(x)))

you could do this:

succ.succ.succ

Pointfree only works with functions that take a single parameter however (in this challenge anyway), so if our function wasn't succ but rather add which take 2 numbers and adds them together, we would have to feed it arguments until there is only one left:

pointful:  \x -> add 1(add 1(add 1 x)) 
pointfree: add 1 . add 1 . add 1

Lastly, functions may take other functions as arguments:

Pointfree: map (f a . f b) . id
Pointful:  \x -> map (\x -> f a (f b x)) (id x)

Javascript equivalent: x => map (x => f(a,f(b,x)), id(x))

Input and expected output

f . f . f
\x -> f (f (f x))

f a . f b . f c
\x -> f a (f b (f c x))

f (f a . f b) . f c
\x -> f (\x -> f a (f b x)) (f c x)

a b c . d e . f g h i . j k l . m
\x -> a b c (d e (f g h i (j k l (m x))))

a.b(c.d)e.f g(h)(i j.k).l(m(n.o).p)
\x->a(b(\y->c(d y))e(f g h(\z->i j(k z))(l(\q->m(\w->n(o w))(p q))x)))

Rules

  • Your output may have more spaces or parentheses than required, as long as they are balanced
  • You don't have to make sure that the name of the variable you create \x isn't already used somewhere else in the code
  • It is your choice whether to create a function or a full program
  • This is codegolf, shortest code in bytes win!

You might find blunt useful, it converts between the two notations (but also factorizes the code when possible): https://blunt.herokuapp.com

BlackCap

Posted 2016-09-29T09:14:04.960

Reputation: 3 576

15In pointfree notation we use points to feed the output of one function into another That's clearly an attempt to prove that pointfree is not pointless – Luis Mendo – 2016-09-29T09:22:45.450

1"Pointfree only works with functions that take a single parameter". That's not true: (+).(*3) is the same as \x y->3*x+y – Damien – 2016-09-29T09:33:45.783

2@Damien I was trying to make the challenge more accessible. You can also do things like the owl: (.).(.) which converts to \i b c f -> i (b c f) – BlackCap – 2016-09-29T09:37:02.620

That's what I thought. Thanks for the clarification. As a huge fan of pointfree style, I had to notice that. – Damien – 2016-09-29T09:40:50.407

2So for clarity for those who don't know the syntax of Haskell by heart: we should first match parentheses in the input and recurse on each top-level parenthesised expression; and then replace each . with a (, prepend a \x and append a corresponding x and as many ) as are required? Or is it more complicated than that? – Peter Taylor – 2016-09-29T11:01:02.860

@PeterTaylor No, that's it exactly – BlackCap – 2016-09-29T11:19:08.420

This could be an interesting challenge for Dyalog APL or J too, but they have complex rules: f g h{(f ⍵) g (h ⍵)}, and allow two arguments, : f g h{(⍺ f ⍵) g (⍺ h ⍵)}... – Adám – 2016-09-29T12:13:32.390

Is it ok if an input like (h) will be converted to (\x->h x)? In my understanding (h) could be considered as pointfree, whereas (\x->h x) is definitely pointful. – Laikoni – 2016-09-30T16:56:58.073

I don't know Haskell but why doesn't f.(f.).f resolve to \d->f(\k->f(k))(f d)?

– Linus – 2016-10-01T02:57:32.460

1@Linus \ d->f(\k->f(f d k)), but you can assume that all the dots are fed two arguments in this challenge – BlackCap – 2016-10-01T11:35:40.677

@Linus Oh, and it's because (.) = \f a x -> f(a(x)), so (succ.) = \a x -> succ(a(x)) and succ.succ = \x -> succ(succ(x)) – BlackCap – 2016-10-01T12:09:15.897

Answers

4

Haskell, 163 142 133 bytes

p(x:r)|[a,b]<-p r=case[x]of"("->["(\\x->"++a++p b!!0,""];"."->['(':a++")",b];")"->[" x)",r];_->[x:a,b]
p r=[r,r]
f s=p('(':s++")")!!0

Try it on Ideone.

Ungolfed:

p('(':r)|(a,b)<-p r = ("(\\x->"++a++(fst(p b)),"")
p('.':r)|(a,b)<-p r = ('(':a++")",              b)
p(')':r)            = (" x)",                   r)
p(x  :r)|(a,b)<-p r = (x:a,                     b)
p _                 = ("",                     "")

f s=fst(p('(':s++")"))

Laikoni

Posted 2016-09-29T09:14:04.960

Reputation: 23 676

2

Haskell, 402 289 bytes

Quite long, but I think it works..

(!)=elem
n%'('=n+1
n%')'=n-1
n%_=n
a?n=a!"."&&n<1
a#n=a!" ("&&n<1||a!")"&&n<2
q a='(':a++")"
p s o n[]=[s]
p s o n(a:b)|o a n=[t|t@(q:r)<-s:p""o(n%a)b]|0<1=p(s++[a])o(n%a)b
k=foldr((++).(++" ").f)"".p""(#)0
f t|not$any(!"(. ")t=t|l@(x:r)<-p""(?)0t=q$"\\x->"++foldr((.q).(++).k)"x"l|0<1=k t

Damien

Posted 2016-09-29T09:14:04.960

Reputation: 2 407