Поверните первый аргумент в функцию, чтобы стать nth
Учитывая функцию с аргументами не менее n
, я хочу повернуть первый аргумент, чтобы он стал аргументом n
th. Например (в нетипизированном лямбда-исчислении):
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
И так далее.
Можете ли вы написать r
общим способом? Что, если вы знаете, что n >= 2
?
Здесь проблема, изложенная в 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
Вращение должно принимать Lam(a => Lam(b => Lam(c => Ap(Ap(a, b), c))))
и возвращать Lam(b => Lam(c => Lam(a => Ap(Ap(a, b), c))))
, например.
Ответы
Ответ 1
ОК, спасибо всем, кто дал ответ. Вот решение, с которым я столкнулся. Воспользовавшись тем, что я знаю 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 []
Я не думаю, что это можно решить без предоставления n
, так как в исчислении лямбда термин arity может зависеть от его аргумента. То есть нет определенного "последнего" аргумента. Соответственно изменился вопрос.
Ответ 2
Трюк состоит в том, чтобы пометить "окончательное" значение задействованных функций, так как для обычного haskell оба a -> b
и a -> (b->c)
являются просто функциями одной переменной.
Если мы это сделаем, мы сможем это сделать.
{-# 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
Затем, чтобы увидеть это в действии:
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
Ответ 3
Возможно, это невозможно без нарушения "легитимности HOAS" в том смысле, что E => E
должен использоваться не только для привязки к языку объекта, но и для вычисления в метаязыке. Тем не менее, здесь решение в Haskell. Он злоупотребляет Literal
node, чтобы удалить уникальный идентификатор для последующей замены. Наслаждайтесь!
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
со следующим результатом:
\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))
(Не обманывайтесь похожими именами переменных. Это вращение, которое вы ищете, по модулю альфа-преобразования.)
Ответ 4
Да, я отправляю еще один ответ. И все равно это не совсем то, что вы ищете. Но я думаю, что это может быть полезно, тем не менее. Это в 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 ++ ")"
Итак, здесь я подготовил базовый тип алгебраических данных для выражения лямбда-исчисления. Я добавил простой, но эффективный, настраиваемый экземпляр Show.
ghci> App (Lambda 'a' (Atom 'a')) (Atom 'b')
((λa. a) b)
Для удовольствия я бросил простой метод reduce
, с помощником replace
. Предупреждение: не тщательно продумано и не проверено. Не использовать в промышленных целях. Невозможно обработать некоторые неприятные выражения.: P
reduce (App (Lambda c target) expr) = reduce $ replace c (reduce expr) target
reduce v = v
replace c expr [email protected](Atom v)
| v == c = expr
| otherwise = av
replace c expr [email protected](App l r)
= App (replace c expr l) (replace c expr r)
replace c expr [email protected](Lambda v e)
| v == c = lv
| otherwise = (Lambda v (replace c expr e))
Кажется, что это работает, хотя на самом деле меня просто отвлекает. (it
в ghci ссылается на последнее значение, полученное в подсказке)
ghci> reduce it
b
Итак, теперь для забавной части, rotate
. Поэтому я полагаю, что могу просто снять первый слой, и если это Лямбда, здорово, я сохраню идентификатор и продолжу бурение до тех пор, пока не удалю не-Лямбду. Затем я просто поставлю Лямбду и идентификатор обратно в "последнее" место. Если это не Лямбда в первую очередь, тогда ничего не делайте.
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
Пропустите имена невообразимых переменных. Отправка этого через ghci показывает хорошие знаки:
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))))
Ответ 5
Один из способов сделать это с помощью шаблона haskell будет таким:
С помощью этих двух функций:
import Language.Haskell.TH
rotateFunc :: Int -> Exp
rotateFunc n = LamE (map VarP vars) $ foldl1 AppE $ map VarE $ (f:vs) ++ [v]
where [email protected](f:v:vs) = map (\i -> mkName $ "x" ++ (show i)) [1..n]
getNumOfParams :: Info -> Int
getNumOfParams (VarI _ (ForallT xs _ _) _ _) = length xs + 1
Тогда для функции myF
с переменным числом параметров вы можете повернуть их следующим образом:
$(return $ rotateFunc $ read $(stringE . show =<< (reify 'myF >>= return . getNumOfParams))) myF
Там, безусловно, есть более аккуратные способы сделать это с TH, я очень новичок в этом.
Ответ 6
Я думаю, вы могли бы использовать методы, описанные в статье n-ary zipWith в Haskell для этого.
Ответ 7
Можете ли вы написать r
общим способом? Что делать, если вы знаете n
?
Haskell
Не в простой ваниль Haskell. Вам нужно будет использовать некоторую глубокую магическую магию, которую кто-то другой (гораздо более мудрый, чем я), вероятно, опубликует.
В простом Haskell попробуйте написать класс.
class Rotatable a where
rotate :: a -> ???
Что такое тип вращения? Если вы не можете написать свою подпись типа, то вам, вероятно, нужны шаблоны для программирования на уровне общности, который вы ищете (в Haskell, в любом случае).
Легко перевести эту идею в функции Haskell.
r1 f = \a -> f a
r2 f = \b -> \a -> f a b
r3 f = \b -> \c -> \a -> f a b c
и др.
Lisp (ы)
На некоторых языках Lisp есть функция apply
(связанная: r5rs), которая принимает функцию и список и применяет элементы список в качестве аргументов функции. Я предполагаю, что в этом случае было бы не так просто просто повернуть список и отправить его на своем пути. Я снова отвечаю гуру за более глубокие ответы.