Chcę napisać funkcję podobną do `flip` w Haskell, aby pozbyć się wyrażeń lambda. Ale nie mogę sobie poradzić z tym typem:

Question

Chcę napisać funkcję Haskella, która działa jak flip, ale jest znacznie bardziej ogólna i może uczynić dowolny parametr funkcji ostatnim parametrem. Dla wygody używamy pull, aby go reprezentować.

Łatwo jest napisać następujący kod:

Prelude> :t flip   --we just call this function a swap 
flip :: (a -> b -> c) -> b -> a -> c 
Prelude> :t (flip.)  --we just call this function a swap 
(flip.) :: (a -> a1 -> b -> c) -> a -> b -> a1 -> c 
Prelude> :t ((flip.).) --we just call this function a swap 
((flip.).) :: (a -> a1 -> a2 -> b -> c) -> a -> a1 -> b -> a2 -> c 
Prelude> :t (((flip.).).) --we just call this function a swap 
(((flip.).).) 
    :: (a -> a1 -> a2 -> a3 -> b -> c) -> a -> a1 -> a2 -> b -> a3 -> c 

I okazuje się, że z bardziej stosowane odwrócić, może zamienić dowolną parę sąsiednich parametrów (.). I z powyższych wyników możemy napisać:

Prelude> :t flip 
flip :: (a -> b -> c) -> b -> a -> c 
Prelude> :t (flip.) . flip 
(flip.) . flip :: (a1 -> a -> b -> c) -> a -> b -> a1 -> c 
Prelude> :t ((flip.).) . (flip.) . flip 
((flip.).) . (flip.) . flip 
    :: (a2 -> a -> a1 -> b -> c) -> a -> a1 -> b -> a2 -> c 
Prelude> :t (((flip.).).) . ((flip.).) . (flip.) . flip 
(((flip.).).) . ((flip.).) . (flip.) . flip 
    :: (a3 -> a -> a1 -> a2 -> b -> c) -> a -> a1 -> a2 -> b -> a3 -> c 

możemy stwierdzić, że z więcej swapy składzie, to może ciągnąć dowolny parametr na ostatnim miejscu. W wielu przypadkach możemy pozbyć się wyrażeń lambda. Ale powyższy ekspres jest bardzo rozdęty.

Moim głównym pomysłem jest wykonanie funkcji pull w celu uogólnienia powyższych funkcji. Model pull działa w przybliżeniu jak poniżej.

let f = undefined    --For convenience, we let f be undefined. 

:t pull 0 (f::a->b->z)   --the type variable z is not a function type. 
>pull 0 (f::a->b->z) :: b->a->z --pull is just like flip for 0 and a function of this type. 
:t pull 0 (f::a->b->c->z)  --the type variable z is not a function type. 
>pull 0 (f::a->b->c->z) :: b->c->a->z 

:t pull 1 (f::a->b->c->z)  --the type variable z is not a function type. 
>pull 1 (f::a->b->c->z) :: a->c->b->z 
:t pull 1 (f::a->b->c->d->z) --the type variable z is not a function type. 
>pull 1 (f::a->b->c->d->z) :: a->c->d->b->z 

:t pull 2 (f::a->b->c->d->z) --the type variable z is not a function type. 
>pull 2 (f::a->b->c->d->z) :: a->b->d->c->z 
:t pull 2 (f::a->b->c->d->e->z) --the type variable z is not a function type. 
>pull 2 (f::a->b->c->d->e->z) :: a->b->d->e->c->z 

Próbowałem na wiele sposobów, aby to zrobić. Naivest jeden jest:

swap :: Word -> a -> a 
swap 0 = flip 
swap n = dot $ swap (n-1) 

i ghc narzekali jak mieszka i rozumiem dlaczego:

-- Prelude> :reload 
-- [1 of 1] Compiling Main    (ModifyArbitrayParameterOfAFunction.hs, interpreted) 
-- 
-- ModifyArbitrayParameterOfAFunction.hs:4:21: 
--  Occurs check: cannot construct the infinite type: c0 = a1 -> c0 
--  Expected type: (a1 -> c0) -> c0 
--  Actual type: (a1 -> c0) -> a1 -> c0 
--  In the return type of a call of `modify' 
--  Probable cause: `modify' is applied to too few arguments 
--  In the first argument of `(.)', namely `(modify (n - 1) modi)' 
--  In the expression: (modify (n - 1) modi) . f1 
-- 
-- ModifyArbitrayParameterOfAFunction.hs:4:42: 
--  Occurs check: cannot construct the infinite type: c0 = a1 -> c0 
--  Expected type: a1 -> a1 -> c0 
--  Actual type: a1 -> c0 
--  In the second argument of `(.)', namely `f1' 
--  In the expression: (modify (n - 1) modi) . f1 
--  In an equation for `modify': 
--   modify n modi f1 = (modify (n - 1) modi) . f1 
-- Failed, modules loaded: none. 

Może moim celem jest tylko pobożne życzenie, ale biorąc pod uwagę system typu Haskell jest jeszcze możliwość zapisu wyrażeń lambda , Ośmielę się powiedzieć, że musi być jakiś sposób, aby to zrobić.

Answer 1

Jak wspomniano w komentarzach, nie można mieć funkcji, której przekażesz funkcję, którą chcesz odwrócić. Parametry są obliczane w czasie wykonywania, podczas gdy potrzebujesz wartości w czasie kompilacji, abyś mógł określić właściwy typ.

Nie można tego zrobić, nie przekazując jej w jakiś sposób. Na przykład a -> b -> c -> d może być wyświetlany jako funkcja trzech argumentów zwracających d lub jako funkcja, jeśli dwa argumenty zwracają c -> d.

Prawdopodobnie najłatwiejszym rozwiązaniem byłoby jednoznaczne zdefiniowanie funkcji, takich jak flip2, flip3 itd. Wiem, że nie jest to coś, czego szukasz, ale jest to najbardziej praktyczne rozwiązanie.

Inną opcją byłoby użycie szablonu Haskell. Wtedy sytuacja jest inna, ponieważ Template Haskell wykonuje (powiedziałbym "meta-") kod podczas kompilacji. Z TH można utworzyć funkcję, która przyjmuje liczbę naturalną i generuje wyrażenie TH, które może być skompilowane do innego modułu.Meta-funkcja może być zdefiniowana jako

{-# LANGUAGE TemplateHaskell #-} 
module GenFlipTH where 

import Language.Haskell.TH 

pull :: Int -> Q Exp 
pull 0    = varE 'flip 
pull n | n < 0  = fail "Negative arity" 
     | otherwise = [| fmap $(pull (n - 1)) . flip |] 
-- Here we use the fact that `(->) r` is a functor. 

i wykorzystane w innym module, aby wygenerować odpowiedni wyraz jak

{-# LANGUAGE TemplateHaskell #-} 
import GenFlipTH 

flip3 :: (a -> b3 -> b2 -> b1 -> b -> c) -> (b3 -> b2 -> b1 -> b -> a -> c) 
flip3 = $(pull 3) 

to prawdopodobnie zamyka wymagań mogę - określić funkcję przez numer i uzyskają gwarancję na kompilację, że jest on tworzony i używany poprawnie.

Answer 2

Nie można tego zrobić w normalny sposób, ponieważ typ funkcji zależy od danych wejściowych. Możesz to zrobić za pomocą polimorfizmu ad-hoc wprowadzonego przez typografy i zależności funkcjonalne. Jednak nawet wtedy będziesz potrzebował wielu rozszerzeń, aby zezwolić na coś takiego jak Oleg's IsFunction (patrz: http://okmij.org/ftp/Haskell/isFunction.lhs). To brakujący element, który pozwala określić, czy osiągnąłeś podstawowy przypadek rekurencji typeclass.