Как реализовать uncurry point-free в Haskell без приложения? - PullRequest
Новая
       214

Как реализовать uncurry point-free в Haskell без приложения?

3 голосов
/ 16 июня 2020

Мне было интересно, как различные стандартные Haskell функции могут быть реализованы без точек. В настоящее время меня интересует uncurry, и я считаю, что это довольно нетривиально.

Основная проблема в том, что мы не можем (или как мне кажется) сгруппировать аргументы. Если бы у нас было uncurry (на самом деле, uncurry ($) было бы достаточно), решение было бы довольно простым:

  1. Сделайте кортеж (f, (x, y)).
  2. Применить assoc1 :: (a, (b, c)) -> ((a, b), c) к кортежу и получите ((f, x), y).
  3. Примените незатянутый ($) к первому элементу пары и получите (f x, y).
  4. Примените незакрепленный ($) к саму пару и получаем f x y.

Без необработанного ($) нам пришлось бы извлекать оба элемента пары отдельно. Например:

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

Я не считаю, что это простой способ реализовать что-то бессмысленное.

Фактически, по нашей просьбе мы получили этот необработанный ($): Control.Arrow.apply (другие полезные комбинаторы решений также могут быть импортированы из Control.Arrow). Следовательно: 

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

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

Тем не менее, это немного похоже на обман.

Существуют ли другие подходы к этой проблеме, не требующие ничего подобного app?

Ответы [ 3 ]

4 голосов
/ 16 июня 2020

Комбинатор с лямбда-исчислением S , 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

, следовательно, 

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

( edit: )

Тем не менее, это гораздо более читабельно (и несколько проясняет) с одним явным аргументом, оставленным там, как показано выше: 

uncurry f  =  f . fst  <*>  snd

Но то этот вариант, показанный Jon Purdy в комментариях , 

uncurry f  =  liftA2 f fst snd

, может быть самым ясным.

Это потому, что для функций , монада и аппликатив эквивалентны по мощности, 

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

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

и liftA2 f fst snd означает, по определению, 

           =  [ 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

(первое, написанное с помощью Monad Computing). Таким образом, 

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

, следуя хорошо известной эквивалентности , k =<< m = join (fmap k m) (а для функций (<$>) = fmap = (.)).

Итак, мы нашли еще одно выражение здесь 

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

Один liftA2 может быть самым четким и наименее шумным.

4 голосов
/ 16 июня 2020

Простое механическое решение, «проталкивая лямбды внутрь» . 

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
4 голосов
/ 16 июня 2020

join в функциях дает вам (a -> a -> b) -> a -> b, поэтому: 

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).) действительно очень читабельно

...