How to implement uncurry point-free in Haskell without app?

user_11143763 0
Viewed 314

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?

arrows pointfree tuples currying haskell
3 Answers

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

user_7071110

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.

user_8498910

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
user_337960
Related