15

少なくともn引数を持つ関数が与えられた場合、最初の引数を回転させて、それがnth 引数になるようにします。例 (型なしラムダ計算):

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))))

4

7 に答える 7

7

a -> b通常の Haskell では、との両方a -> (b->c)が 1 つの変数の関数にすぎないため、関係する関数の「最終」値にタグを付けるのがコツです。しかし、そうすれば、これを行うことができます。

{-# 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
于 2011-03-04T18:14:34.487 に答える
5

E => Eオブジェクト言語でのバインドだけでなく、メタ言語での計算にも使用する必要があるという意味で、HOASの「正当性」に違反しない限り不可能です。そうは言っても、これがHaskellの解決策です。ノードを悪用してLiteral、後で置換するために一意のIDをドロップします。楽しみ！

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))

（似たような変数名にだまされないでください。これは、求める回転、モジュロアルファ変換です。）

于 2011-03-04T04:49:23.097 に答える
4

はい、別の回答を投稿しています。そして、それはまだあなたが探しているものではないかもしれません. でもそれでも使えると思います。ハスケルにあります。

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、 helper を使用した単純なメソッドを投入しreplaceました。警告: 慎重に検討またはテストされていません。工業用には使用しないでください。特定の厄介な表現を処理できません。：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))

それはうまくいくようですが、それは本当に私が脇道にそれているだけです。( itin ghci は、プロンプトで評価された最後の値を指します)

ghci> reduce it
b

それでは、楽しい部分ですrotate。したがって、最初のレイヤーをはがすだけでよいと思います。それが Lambda の場合は、識別子を保存して、非 Lambda に到達するまでドリルダウンを続けます。次に、Lambda と識別子を「最後の」場所に戻します。そもそも Lambda ではなかった場合は、何もしません。

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))))
于 2011-03-04T04:09:34.673 に答える
3

テンプレート haskell でそれを行う 1 つの方法は次のようになります。

これらの 2 つの関数を使用すると、次のようになります。

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

次にmyF、可変数のパラメーターを持つ関数の場合、次の方法でそれらを回転させることができます。

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

THでこれを行うためのもっときちんとした方法があることは間違いありません。私はそれに非常に慣れていません。

于 2011-03-05T00:15:50.663 に答える
1

OK、答えてくれたみんなに感謝します。これが私が最終的に行った解決策です。私が知っているという事実を利用して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ラムダ計算では、項のアリティがその引数に依存する可能性があるため、これは を与えずに解決できるとは思いません。つまり、明確な「最後の」引数はありません。それに応じて質問を変更しました。

于 2011-03-04T22:16:08.813 に答える
0

これには、 An n-ary zipWith in Haskellという論文で説明されている手法を使用できると思います。

于 2011-03-04T08:21:16.133 に答える
-1

一般的な方法で書くことができます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（s）

一部のLispy言語には、apply関数（リンク：r5rs）があります。この関数は、関数とリストを受け取り、リストの要素を引数として関数に適用します。その場合、リストのローテーションを解除して送信するのはそれほど難しいことではないと思います。私は再び、より深い答えを求めて教祖に任せます。

于 2011-03-04T01:54:51.213 に答える