Ruota il primo argomento in una funzione per diventare n.

Question

Dato una funzione con almeno n argomenti, voglio ruotare il primo argomento in modo che diventi l'argomento n. Ad esempio (nel calcolo lambda non tipizzato):

r(λa. a)     = λa. a 
r(λa. λb. a b)    = λb. λa. a b 
r(λa. λb. λc. a b c)  = λb. λc. λa. a b c 
r(λa. λb. λc. λd. a b c d) = λb. λc. λd. λa. a b c d 

E così via.

Si può scrivere r in modo generico? Che cosa succede se si conosce che n >= 2?

Ecco il problema indicato nel Scala:

trait E 
case class Lam(i: E => E) extends E 
case class Lit(i: Int) extends E 
case class Ap(e: E, e: E) extends E 

La rotazione dovrebbe prendere Lam(a => Lam(b => Lam(c => Ap(Ap(a, b), c)))) e tornare Lam(b => Lam(c => Lam(a => Ap(Ap(a, b), c)))), per esempio.

Answer 1

OK, grazie a tutti coloro che hanno fornito una risposta. Ecco la soluzione con cui ho finito. Approfittando del fatto che conosco n:

rot :: Int -> [Expr] -> Expr 
rot 0 xs = Lam $ \x -> foldl App x (reverse xs) 
rot n xs = Lam $ \x -> rot (n - 1) (x : xs) 

rot1 n = rot n [] 

non credo che questo può essere risolto senza dare n, dal momento che nel lambda calcolo, arity di un termine può dipendere dal suo argomento. Cioè non esiste un "ultimo" argomento definito. Modificata la domanda di conseguenza.

Answer 2

Si può scrivere r in modo generico? Cosa succede se sapete n?

Haskell

Non in plain vanilla Haskell. Dovresti usare una magia di templatura profonda che probabilmente qualcun altro (molto più saggio di me) pubblicherà.

In semplice Haskell, proviamo a scrivere un corso.

class Rotatable a where 
    rotate :: a -> ??? 

Cosa diavolo è il tipo per ruotare? Se non puoi scrivere la sua firma del tipo, probabilmente hai bisogno di modelli da programmare al livello di generalità che stai cercando (in Haskell, comunque).

Tuttavia, è abbastanza facile tradurre l'idea in funzioni Haskell.

r1 f = \a -> f a 
r2 f = \b -> \a -> f a b 
r3 f = \b -> \c -> \a -> f a b c 

ecc

---

Lisp (s)

Alcune lingue Lispy hanno la apply function (linked: r5rs), che prende una funzione e una lista, e applica gli elementi della lista come argomenti alla funzione. Immagino che in quel caso non sarebbe così difficile semplicemente annullare la rotazione della lista e inviarla a modo suo. Di nuovo rimando ai guru per risposte più profonde.

Answer 3

Sì, sto postando un'altra risposta. E potrebbe ancora non essere esattamente quello che stai cercando. Ma penso che potrebbe essere comunque utile. È a Haskell.

data LExpr = Lambda Char LExpr 
      | Atom Char 
      | App LExpr LExpr 

instance Show LExpr where 
    show (Atom c) = [c] 
    show (App l r) = "(" ++ show l ++ " " ++ show r ++ ")" 
    show (Lambda c expr) = "(λ" ++ [c] ++ ". " ++ show expr ++ ")" 

Quindi qui ho preparato un tipo di dati algebrici di base per esprimere il calcolo lambda. Ho aggiunto un'istanza Show semplice, ma efficace.

ghci> App (Lambda 'a' (Atom 'a')) (Atom 'b') 
((λa. a) b) 

Per divertimento, ho gettato in un metodo semplice reduce, con aiutante replace. Attenzione: non attentamente pensato o testato. Non usare per scopi industriali. Impossibile gestire determinate espressioni sgradevoli.: P

reduce (App (Lambda c target) expr) = reduce $ replace c (reduce expr) target 
reduce v = v 

replace c expr av@(Atom v) 
    | v == c = expr 
    | otherwise = av 
replace c expr ap@(App l r) 
       = App (replace c expr l) (replace c expr r) 
replace c expr lv@(Lambda v e) 
    | v == c = lv 
    | otherwise = (Lambda v (replace c expr e)) 

Sembra funzionare, anche se in realtà sono solo io ad essere sviato. (it in ghci si riferisce all'ultimo valore valutato al prompt)

ghci> reduce it 
b 

Così ora per la parte divertente, rotate. Quindi immagino di poter staccare il primo strato, e se è un Lambda, grande, salverò l'identificatore e continuerò a perforare fino a quando non colpirò un non-Lambda. Poi inserirò la Lambda e l'identificatore proprio nell'ultimo punto. Se non era un Lambda in primo luogo, allora non fare nulla.

rotate (Lambda c e) = drill e 
    where drill (Lambda c' e') = Lambda c' (drill e') -- keep drilling 
      drill e' = Lambda c e'  -- hit a non-Lambda, put c back 
rotate e = e 

Perdona i nomi di variabili non fantasiose. L'invio di questo attraverso ghci mostra buoni segnali:

ghci> Lambda 'a' (Atom 'a') 
(λa. a) 
ghci> rotate it 
(λa. a) 
ghci> Lambda 'a' (Lambda 'b' (App (Atom 'a') (Atom 'b'))) 
(λa. (λb. (a b))) 
ghci> rotate it 
(λb. (λa. (a b))) 
ghci> Lambda 'a' (Lambda 'b' (Lambda 'c' (App (App (Atom 'a') (Atom 'b')) (Atom 'c')))) 
(λa. (λb. (λc. ((a b) c)))) 
ghci> rotate it 
(λb. (λc. (λa. ((a b) c)))) 

Answer 4

E 'probabilmente impossibile senza violare la 'legittimazione' di HOAS, nel senso che il E => E non deve essere utilizzato solo per il legame nella lingua oggetto, ma per il calcolo del meta lingua. Detto questo, ecco una soluzione in Haskell. Abusa un nodo Literal per inserire un ID univoco per la sostituzione successiva. Godere!

import Control.Monad.State 

-- HOAS representation 
data Expr = Lam (Expr -> Expr) 
      | App Expr Expr 
      | Lit Integer 

-- Rotate transformation 
rot :: Expr -> Expr 
rot e = case e of 
    Lam f -> descend uniqueID (f (Lit uniqueID)) 
    _ -> e 
    where uniqueID = 1 + maxLit e 

descend :: Integer -> Expr -> Expr 
descend i (Lam f) = Lam $ descend i . f 
descend i e = Lam $ \a -> replace i a e 

replace :: Integer -> Expr -> Expr -> Expr 
replace i e (Lam f) = Lam $ replace i e . f 
replace i e (App e1 e2) = App (replace i e e1) (replace i e e2) 
replace i e (Lit j) 
    | i == j = e 
    | otherwise = Lit j 

maxLit :: Expr -> Integer 
maxLit e = execState (maxLit' e) (-2) 
    where maxLit' (Lam f) = maxLit' (f (Lit 0)) 
     maxLit' (App e1 e2) = maxLit' e1 >> maxLit' e2 
     maxLit' (Lit i) = get >>= \k -> when (i > k) (put i) 

-- Output 
toStr :: Integer -> Expr -> State Integer String 
toStr k e = toStr' e 
    where toStr' (Lit i) 
      | i >= k = return $ 'x':show i -- variable 
      | otherwise = return $ show i -- literal 
     toStr' (App e1 e2) = do 
      s1 <- toStr' e1 
      s2 <- toStr' e2 
      return $ "(" ++ s1 ++ " " ++ s2 ++ ")" 
     toStr' (Lam f) = do 
      i <- get 
      modify (+ 1) 
      s <- toStr' (f (Lit i)) 
      return $ "\\x" ++ show i ++ " " ++ s 

instance Show Expr where 
    show e = evalState (toStr m e) m 
    where m = 2 + maxLit e 

-- Examples 
ex2, ex3, ex4 :: Expr 

ex2 = Lam(\a -> Lam(\b -> App a (App b (Lit 3)))) 
ex3 = Lam(\a -> Lam(\b -> Lam(\c -> App a (App b c)))) 
ex4 = Lam(\a -> Lam(\b -> Lam(\c -> Lam(\d -> App (App a b) (App c d))))) 

check :: Expr -> IO() 
check e = putStrLn(show e ++ " ===> \n" ++ show (rot e) ++ "\n") 

main = check ex2 >> check ex3 >> check ex4 

con il seguente risultato:

\x5 \x6 (x5 (x6 3)) ===> 
\x5 \x6 (x6 (x5 3)) 

\x2 \x3 \x4 (x2 (x3 x4)) ===> 
\x2 \x3 \x4 (x4 (x2 x3)) 

\x2 \x3 \x4 \x5 ((x2 x3) (x4 x5)) ===> 
\x2 \x3 \x4 \x5 ((x5 x2) (x3 x4)) 

(Non fatevi ingannare dai nomi delle variabili simili di aspetto Questa è la rotazione che si cercano, modulo alfa-conversione..)

Answer 5

I penso che si possa usare le tecniche descritte nella carta An n-ary zipWith in Haskell per questo.

Answer 6

Il trucco consiste nel taggare il valore "finale" delle funzioni coinvolte, poiché in normale haskell, sia a -> b sia a -> (b->c) sono solo funzioni di una singola variabile. Se lo facciamo, però, possiamo farlo.

{-# LANGUAGE TypeFamilies,FlexibleInstances,FlexibleContexts #-} 
module Rotate where 

data Result a = Result a 

class Rotate f where 
    type After f 
    rotate :: f -> After f 

instance Rotate (a -> Result b) where 
    type After (a -> Result b) = a -> Result b 
    rotate = id 

instance Rotate (a -> c) => Rotate (a -> b -> c) where 
    type After (a -> b -> c) = b -> After (a -> c) 
    rotate = (rotate .) . flip 

Poi, per vederlo in azione:

f0 :: Result a 
f0 = Result undefined 

f1 :: Int -> Result a 
f1 = const f0 

f2 :: Char -> Int -> Result a 
f2 = const f1 

f3 :: Float -> Char -> Int -> Result a 
f3 = const f2 

f1' :: Int -> Result a 
f1' = rotate f1 

f2' :: Int -> Char -> Result a 
f2' = rotate f2 

f3' :: Char -> Int -> Float -> Result a 
f3' = rotate f3 

Answer 7

Un modo per farlo con template Haskell sarebbe come questo:

Con queste due funzioni:

import Language.Haskell.TH 

rotateFunc :: Int -> Exp 
rotateFunc n = LamE (map VarP vars) $ foldl1 AppE $ map VarE $ (f:vs) ++ [v] 
    where vars@(f:v:vs) = map (\i -> mkName $ "x" ++ (show i)) [1..n] 

getNumOfParams :: Info -> Int 
getNumOfParams (VarI _ (ForallT xs _ _) _ _) = length xs + 1 

Poi per una funzione myF con un numero variabile di parametri che si poteva ruotare loro in questo modo :

$(return $ rotateFunc $ read $(stringE . show =<< (reify 'myF >>= return . getNumOfParams))) myF 

Ci sono sicuramente modi più netti per farlo con TH, sono molto nuovo.