1

From this answer one learns how to implement the function \x y z -> f x (g y z) in a pointless way in Haskell, where f and g are functions. And my question is

How to write the function \x -> f (g x) (h x) in a pointfree manner in Haskell? Here f g h are functions for which f (g x) (h x) is defined.

The idea I currently have in mind is something like the following.

uncurry f (mapTuple ($ x) (g, h))

But several tries shows that this is fallacious; even the part map ($ x) [g, h] is suspicious: what if g and h have different ranges?

In addition, readability is not too much an issue here.

Any help is sincerely appreciated.

Community
  • 1
  • 1
awllower
  • 571
  • 1
  • 9
  • 21
  • 1
    That's just `liftA2 f g h`. – melpomene Jul 23 '16 at 16:03
  • Thanks for the suggestion. But I am having a headache understanding what `APPlicative` is. Maybe some other way without being `Applicative`? Thanks still. :) – awllower Jul 23 '16 at 16:13
  • 4
    Sure: `liftM2 f g h` :-) – melpomene Jul 23 '16 at 16:16
  • Thanks for this nice suggestion! Indeed monads come in quite handy in such higher-order tasks. I would like to see some `built from scratch` example, if any, though. Again thanks for pointing out this use of monads. :D – awllower Jul 23 '16 at 16:43
  • 1
    Note that `Applicative` is more fundamental than the monad; technically it's actually simpler (but for some strange reason, monads seem indeed easier to understand, I also struggled with applicatives for a while). Anyway, `liftA2`/`liftM2` rely on a particular, somewhat controversial applicative _instance_ of functions, so this isn't really “a monad solution” but a solution exploiting that instance. The really fundamental approach is to use the [cartesian monoidal category](https://en.wikipedia.org/wiki/Cartesian_monoidal_category) property of Haskell functions; this is what `Arrow` does. – leftaroundabout Jul 23 '16 at 17:28
  • @leftaroundabout Thanks for pointing out the interesting fact that `Arrow` uses the cartesian monoidal category property. I think I will have a long-time headache then. :-P – awllower Jul 23 '16 at 17:41
  • 3
    The process of converting a lambda term into an equivalent that instead of lambda abstraction uses a suitable set of combinators is called [abstraction elimination](https://en.wikipedia.org/w/index.php?title=Combinatory_logic&oldid=724463160#Completeness_of_the_S-K_basis). The link shows that combinators **S** and **K** are such a set, and `liftA2` or `liftM2` for the reader monad is just the **S** combinator. I wrote an article about this relationship a few years ago in [The Monad Reader #17](https://themonadreader.files.wordpress.com/2011/01/issue17.pdf). – Petr Jul 23 '16 at 18:07
  • 2
    @PetrPudlák `liftA2` is not **S**. `ap` is **S**. – melpomene Jul 23 '16 at 20:16
  • @melpomene You're right, that was a mistake. – Petr Jul 24 '16 at 08:41
  • @melpomene I don't see why `ap` is **S**: I am told `S x y z = x z (y z)`, but IMHO, `ap` just lifts function application? Also I like this abstraction elimination: quite interesting! – awllower Jul 24 '16 at 10:31
  • According to the abstraction-elimination process in the link we can also write ----------------------------------------- `S (S (K f) (S (K g) I)) (S (K h) I),` per chance? – awllower Jul 24 '16 at 10:40
  • @awllower https://gist.github.com/anonymous/7050431229399e6002dd3a56abf256a7 – melpomene Jul 24 '16 at 10:52
  • I see! Thanks for pointing out this detailed expansion of `ap` in the case of `(->) e` monad. So what I wrote above may be written as `ap (ap (const f) g) h` after eta reduction? – awllower Jul 24 '16 at 11:02
  • @leftaroundabout Sorry about the mention after a long time; I found that we can view arrows as strong monads in the bicategory of pro-functors, and in fact the notion of arrows is not limited to cartesian categories, but we can define it over a monodical category. BTW, I am referring to [this oar](http://www-kb.is.s.u-tokyo.ac.jp/~asada/papers/arrStrMnd.pdf). And this left me wondering if there is a more mathematical fit for applicative. :P – awllower Sep 02 '16 at 16:30
  • 1
    @awllower: well, that “monad in **Prof**” stuff is another aspect of `Arrow`, the one you get from `arr`. However, I feel `arr` is foremostly a bit of a hack to get access to the simple isomorphisms you need for a cartesian monoidal category, without needing a whole bunch of methods (`(a,b)->(b,a)` and `((a,b),c)->(a,(b,c))`, etc.). An arrow is not “defined over a cartesian category”, it **is** a CMC. — That's not to say the 2-category view as in the article you linked isn't valid – just, I don't see how this is useful, and fear it's somewhat responsible for the bad rep `Arrow` is getting. – leftaroundabout Sep 03 '16 at 00:24

4 Answers4

6

The arrow version would be

uncurry f . (g &&& h)

or

(g &&& h) >>> uncurry f

As a diagram:

        g ────
       ╱          ╲
──── &&&      >>>  uncurry f ───
       ╲          ╱
        h ────
leftaroundabout
  • 117,950
  • 5
  • 174
  • 319
3

As melpomene suggested, \x -> f (g x) (h x) is equivalent to liftM2 f g h.

When you have question concerning how to convert Haskell code into pointfree Haskell code, you can just try Pointfree.io.

It is a great tool which often can tell you when NOT to use pointfree code because it goes completely unreadable sometimes :-)

enter image description here

Community
  • 1
  • 1
zigazou
  • 1,725
  • 9
  • 13
  • Thanks for the answer and this interesting website. :) – awllower Jul 23 '16 at 17:08
  • 2
    Better use `liftA2` instead of `liftM2`, the latter is kinda deprecated since the AMP. – leftaroundabout Jul 23 '16 at 17:14
  • You can also use the `pointfree` command line utility (and optionally write bindings to integrate it into ghci sessions): https://hackage.haskell.org/package/pointfree – Benjamin Kovach Jul 23 '16 at 23:22
  • @BenjaminKovach I tried to `cabal install pointfree` butter some reason the package cannot be installed. It told me such modules as Plugin.Pl.Common cannot be found while those modules are in the correct position. So I guess I will make do with pointfree.io. Thanks for the suggestion. :) – awllower Jul 24 '16 at 09:37
2

Applicative-style

f <$> g <*> h

Control.Compose

join ((g ~> h ~> id) f)

Data.Function.Meld

join (f $* g $$ h *$ id)

Data.Function.Tacit

lurryA @N1 (f <$> (g <$> _1) <*> (h <$> _1))
lurryA @N4 (_1 <*> (_2 <*> _4) <*> (_3 <*> _4)) f g h
erisco
  • 14,154
  • 2
  • 40
  • 45
  • After a long time I finally got what this code says: `f <$> g <*> h`. I think it is no other than `ap (f . g) h`. In any case, thanks for such useful information. – awllower Aug 24 '16 at 07:28
  • 1
    @awllower check out the "intuitions" I posted here http://stackoverflow.com/a/34536499/260584 which offer a straight-forward way to think about Applicative on functions. Note also that `<$>` is `.`, `<*>` is the Lambda Calculus combinator S, and `pure` is the combinator K (which is `const`). – erisco Aug 24 '16 at 15:45
0

This only serves to collect and put into order the answers in the comments. According to the abstraction-elimination process in the link in the comment by @ PetrPudlák, we can also write 

S (S (K f) (S (K g) I)) (S (K h) I),

or, after eta reduction,

S (S (K f) g) h,

where 

S x y z = x z (y z)
K x y = x

Specifically in Haskell, thanks to @melpomene for pointing this out, the role of S is played by ap, and that of K by const. Therefore we can write 

ap (ap (const f) g) h

In fact we can further reduce: 

ap (const f) g = f . g

So our function can be written as:

ap (f . g) h

If translated to Applicative style, we obtain:

f <$> g <*> h

Then this systematic approach can be applied to all lambda terms, and gives the point-free style. :)

awllower
  • 571
  • 1
  • 9
  • 21