4

I have been wondering how different standard Haskell functions could be implemented point-free. Currently, I am interested in uncurry and I feel this one is quite non-trivial.

The main problem is that we are unable (or as it seems to me) to group the arguments. If we had uncurry (in fact, uncurry ($) would suffice) in use, the solution would have been quite simple:

  1. Make a tuple (f, (x, y)).
  2. Apply assoc1 :: (a, (b, c)) -> ((a, b), c) to the tuple and get ((f, x), y).
  3. Apply the uncurried ($) to the first element of the pair and get (f x, y).
  4. Apply the uncurried ($) to the pair itself and get f x y.

Without the uncurried ($) we would have to extract both elements of the pair separately. E.g.:

uncurry f pair = f (fst pair) (snd pair)

I do not reckon this to be a smooth way to implement something point-free.

In fact, we have got this uncurried ($) at our behest: Control.Arrow.apply (other useful for the solution combinators could also be imported from Control.Arrow). Therefore:

import Control.Arrow ((>>>), (&&&), first, app)

myUncurry = let myAssoc1 = (fst &&& (fst . snd)) &&& (snd . snd)
            in (,) >>> (>>> myAssoc1 >>> first app >>> app)

Yet, this feels a small bit like cheating.

Are there any other approaches towards this problem which do not require anything like app?

Zhiltsoff Igor
  • 1,812
  • 8
  • 24
  • 3
    I can't see any simpler solution at the moment. Also the rules of the "point free" game are slightly fuzzy, since it depends on what library primitives are allowed. I tend to use `curry` and `uncurry` as primitives when I write point free code. – chi Jun 16 '20 at 08:11
  • @chi True, but that's kind of the point. `curry` could be implemented point-free way easier though. – Zhiltsoff Igor Jun 16 '20 at 08:42
  • I don't wish to steal your joy of solving these problems, so I'll just mention that there is a simple algorithm for making functions point free, as long as you have a couple basic combinators available – luqui Jun 16 '20 at 09:39
  • @luqui yes, I'm aware of that. I usually call this "dragging the argument out" as we are aiming to replace all `$`'s with `.`'s. Yet, as chi mentioned above, `uncurry` occurs (at least to me) to be the part and parcel of the set of available combinators. – Zhiltsoff Igor Jun 16 '20 at 09:47
  • @luqui the algo might be simple to state as a non-deterministic one, but its branching factor is high and choosing the "right" path is an "art". – Will Ness Jun 16 '20 at 17:03
  • 1
    I think there's a good *reason* `uncurry` is generally included. We make things point-free to bring them into the land of profunctors. `curry` and `uncurry` are very simple adaptors in that context. – dfeuer Jun 16 '20 at 17:14
  • 3
    You can do everything with just `(<*>)` and `const` (and occasionally `fix` for type checking reasons) (and of course constructors/eliminators for any data types you are using). Technically you don't even need `(.)`. The result is not usually very pretty, so the additional combinators like `uncurry` essentially serve a beautification purpose. – luqui Jun 16 '20 at 17:17
  • @luqui can you please, elaborate on being able to implement everything with exclusive use of `(<*>)` and `const`? Or can you recommend any materials to wrap one's head around the essence of point-free. As I have mentioned above, I have always perceived it as a simple rearrangement of parts of the function. – Zhiltsoff Igor Jun 16 '20 at 17:29
  • 1
    @ZhiltsoffIgor `(<*>)` and `const` are the `S` and `K` in [SKI combinators](https://en.wikipedia.org/wiki/SKI_combinator_calculus), which are known to be turing complete. So it makes some sense that you can combine functions in any conceivable way with them. You do need constructors and eliminators for the types you're using, as luqui says (here `fst`, `snd`, and `(,)`), but you can juggle them around any way you like with SKI. – amalloy Jun 16 '20 at 17:33
  • 2
    There are all sorts of different ways to phrase the same underlying structure: `uncurry f pair = f (fst pair) (snd pair)` = `uncurry f = f <$> fst <*> snd` = `uncurry f = liftA2 f fst snd` = `uncurry = (<*> snd) . (<$> fst)` = `uncurry = flip (flip liftA2 fst) snd` = … – Jon Purdy Jun 16 '20 at 23:21
  • 1
    @ZhiltsoffIgor also see https://en.wikipedia.org/wiki/B,_C,_K,_W_system#Connection_to_other_combinators which gives translations of **B** (`(.)`), **C** (`flip`), **W** (`join`) and even **I** (`id`) in terms of **S** (`(<*>)`) and **K** (`const`). not every combination has type in Haskell though, e.g. **U**x = xx = **WI**x doesn't. – Will Ness Jun 17 '20 at 08:54

3 Answers3

4

join on functions gives you (a -> a -> b) -> a -> b, so:

myUncurry f = join (\x y -> f (fst x) (snd y))
myUncurry f = join (\x -> f (fst x) . snd)
myUncurry f = join ((.snd) . f . fst)
myUncurry f = join ((.fst) ((.snd) . f))
myUncurry f = join ((.fst) ((.) (.snd) f))
myUncurry = join . (.fst) . \f -> (.) (.snd) f
myUncurry = join . (.fst) . ((.snd).)

join . (.fst) . ((.snd).) is very readable indeed

Ry-
  • 218,210
  • 55
  • 464
  • 476
  • Thank you! Truth be told, I have never heard of `join` before. It seems pretty cool. – Zhiltsoff Igor Jun 16 '20 at 08:41
  • 1
    In category theory, `join` is a basic part of the definition of a monad, and you would implement `m >>= f = join (fmap f m)`. In Haskell, `(>>=)` is the basic component, and `join m = m >>= id`. Its generic type signature is `Monad m => m (m a) -> m a`, so when `m ~ (->) a`, you get `((->) a) (((->) a) b) -> ((->) a) b`, or `(a -> a -> b) -> a -> b`. – chepner Jun 16 '20 at 16:20
4

With Lambda Calculus' S combinator, Sabc = (a <*> b) c = a c $ b c,

uncurry f (x,y)  =   f (fst (x,y)) (snd (x,y))
                 =  (f . fst  <*>  snd) (x,y)
uncurry f  =  (<*> snd) (f . fst)
           =  (<*> snd) . (. fst) $ f

hence,

uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry  =  (<*> snd) . (. fst)

(edit:)

Still it's much more readable (and somewhat elucidating) with one explicit argument left there, as seen above:

uncurry f  =  f . fst  <*>  snd

But then this variant, shown by Jon Purdy in the comments,

uncurry f  =  liftA2 f fst snd

just might be the clearest.

This is because for functions, the monad and the applicative are equivalent in power,

(k =<< f) x  =  k (f x) x  =  flip k x (f x)  =  (flip k <*> f) x

-- i.e.,  uncurry f  =  flip (f . fst) =<< snd

and liftA2 f fst snd means, by definition,

           =  [ f a b | a <- fst ; b <- snd ]
           = 
              do {            a   <- fst    ; 
                                b <- snd    ; 
                    return (f a b)
                 }
           =  \x -> let 
                 {            a   =  fst  x ; 
                                b =  snd  x ;
                 } 
                 in  const (f a b)        x

(the first one written with Monad Comprehensions). Thus,

uncurry f x  =  liftA2 f   fst    snd     x
             =  let 
                 {            a   =  fst  x ; 
                                b =  snd  x ;
                 } 
                 in         f a b
             =
                       f (fst x) (snd x)
             =
                     (f . fst <*> snd) x
             =
               (flip (f . fst) =<< snd) x
             =
                flip (f . fst)    (snd x) x
             =
               (flip (f . fst)  .  snd) x x
             =
          join (flip (f . fst)  .  snd)  x 
             =
          join (flip (f . fst) <$> snd)  x

following the well known equivalence, k =<< m = join (fmap k m) (and for functions, (<$>) = fmap = (.)).

So we've found yet another expression here,

uncurry f x  =  join (flip (f . fst) . snd)
             =  liftA2      f   fst    snd
             =              f . fst <*> snd
             =        flip (f . fst) =<< snd

The liftA2 one just might be the clearest and the least noisy.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
4

The artless, mechanical solution, by "pushing lambdas inward".

uncurry f (x,y) = f x y
uncurry f p = f (fst p) (snd p)
uncurry f = \p -> f (fst p) (snd p)
uncurry f = (<*>) (\p -> f (fst p)) (\p -> snd p)
uncurry f = (<*>) (f . fst) snd
uncurry = \f -> (<*>) (f . fst) snd
uncurry = flip (\f -> (<*>) (f . fst)) snd
uncurry = flip ((<*>) . (\f -> f . fst)) snd
uncurry = flip ((<*>) . (. fst)) snd
luqui
  • 59,485
  • 12
  • 145
  • 204