9

|fib| などの通常の再帰表記を翻訳する方法を見つけようとしています。再帰表記の構造を可能な限り保持しながら、下の関数を矢印に置き換えます。さらに、矢印を調べたいと思います。このために、各 Arrow{..} クラスのコンストラクターを含むデータ型を作成しました。

フィブ:

fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)

私のRデータ型、このデータ型のインスタンスは、適切なコンストラクターへのマッピングで構成されています:

data R x y where
  -- Category
  Id       :: R a a
  Comp     :: R b c    -> R a b          -> R a c
  -- Arrow
  Arr      :: (a -> b) -> R a b
  Split    :: R b c    -> R b' c'        -> R (b,b') (c,c')
  Cache    :: (a -> a -> Bool) -> R a a
  -- ArrowChoice
  Choice   :: R b c -> R b' c' -> R (Either b b') (Either c c')
  -- ArrowLoop
  Loop     :: R (b, d) (c, d)  -> R b c
  -- ArrowApply
  Apply    :: R (R b c, b) c

|fib|の翻訳 上記の関数は、最初に次の定義をもたらしました。ただし、|fibz| の宣言の右側にある proc n のために許可されていません。Arrow Notation の文法がこれを妨げていることは知っていますが、その根本的な理由は何ですか?

fib' :: (ArrowChoice r, ArrowLoop r) => r Int Int
fib' = proc x -> do
  rec fibz <- proc n -> case n of
                          0  -> returnA -< 0
                          1  -> returnA -< 1
                          n' -> do l <- fibz -< (n'-2)
                                   r <- fibz -< (n'-1)
                                   returnA -< (l+r)
  fibz -<< x

上記の関数を let ステートメントを使用するように書き換えると、コンパイルが実行されます。ただし、ここで 2 つ目の問題が発生します。再帰が発生する場所を検査できるようにしたい。ただし、この場合 |fibz| 無限木です。再帰を fibz にキャプチャしたいと思います。rec が |loop| と組み合わせてそれを支援してくれることを願っています。しかし、多分私は間違っていますか？

fib'' :: (ArrowChoice r, ArrowLoop r, ArrowApply r) => r Int Int
fib'' = proc x -> do
  let fibz = proc n -> case n of
                          0  -> returnA -< 0
                          1  -> returnA -< 1
                          n' -> do l <- fibz -< (n'-2)
                                   r <- fibz -< (n'-1)
                                   returnA -< (l+r)
  fibz -<< x

基本的に、この種の再帰を観察することは可能ですか? (おそらく Arrow Notation の境界内でも) fix のような別のコンストラクターを追加することもできます。たぶん、変数の参照が可能になるように、変数のバインディングを観察できるはずです。ただし、これは Arrows の範囲外になります。

これについて何か考えはありますか？

更新 1: 矢印表記以外で、このフォームを思いつきました。これにより、内に再帰が隠されるappため、矢印の有限表現になります。fibただし、内部への呼び出しをapp最適化されたバージョンのfib.

fib :: (ArrowChoice r, ArrowLoop r, ArrowApply r) => r Int Int
fib
  = (arr
       (\ n ->
          case n of
              0 -> Left ()
              1 -> Right (Left ())
              n' -> Right (Right n'))
       >>>
       (arr (\ () -> 0) |||
          (arr (\ () -> 1) |||
             (arr (\ n' -> (n', n')) >>>
                (first ( arr (\ n' -> app (fib, n' - 2))) >>>
                   arr (\ (l, n') -> (n', l)))
                  >>>
                  (first (arr (\ n' -> app (fib, n' - 1))) >>>
                     arr (\ (r, l) -> (l + r)))))))

このコードは、以下の矢印表記に対応しています。

fib :: (ArrowChoice r, ArrowLoop r, ArrowApply r) => r Int Int
fib  = proc n ->
   case n of
     0  -> returnA -< 0
     1  -> returnA -< 1
     n' -> 
           do l <- fib -<< (n'-2)
              r <- fib -<< (n'-1)
              returnA -< (l+r)
4

2 に答える 2

3

fibたとえば、次のようにループの観点から書くことができます。

fib'' :: (ArrowChoice r, ArrowLoop r, ArrowApply r) => r Int Int
fib'' = loop $ proc (i, r) -> do
    i' <- r -<< i
    returnA -< (i', proc j -> case j of
        0 -> returnA -< 0
        1 -> returnA -< 1
        _ -> do
            a <- r -< j-2
            b <- r -< j-1
            returnA -< a + b)

しかし、これは実際には必要のない問題に人為的なループを導入しているだけであり、可観測性の点でもあまりメリットがありません。ある種のループが存在することはわかりますが、再帰がどこで発生するかを正確に特定することは不可能だと思います。

具体化された表現では、他の矢印への呼び出しは基本的に「インライン化」され、これには同じ矢印への呼び出しが含まれます。どの矢印が呼び出されているかを見つけることは言うまでもなく、そもそもこれらの呼び出しサイトを実際に検出することはできません。矢印の具体化に関するもう 1 つの問題は、入力がどのように渡されるかについての興味深い情報の多くがArrブラックホール内で失われることです。

私は確かに矢の専門家ではなく、誰かが私が間違っていることを証明してくれることを願っていますが、あなたが達成しようとしていることは確実に行うことは不可能であるか、少なくとも非常に非現実的であると考える傾向があります. 私が考えることができるリソースの 1 つは、Haskell での Type-Safe Observable Sharingとdata-reifyパッケージです。

于 2012-10-12T05:10:24.623 に答える
0

コードをディスクに保存して再度ロードする関数を定義できる範囲で、カテゴリを使用して fib を完全に具体化できます。それは少し醜いですが。

{-# LANGUAGE GADTs, RankNTypes #-}

module Main where

import Control.Category

data RRef s1 s2 = RRef Int

data R s1 s2 where
  Id :: forall s. R s s
  Compose :: forall s1 s2 s3. R s2 s3 -> R s1 s2 -> R s1 s3
  Lit :: forall s a. a -> R s (a,s)
  Dup :: forall s a. R (a,s) (a,(a,s))
  Drop :: forall s b. R (b,s) s
  Add :: forall s a. Num a => R (a,(a,s)) (a,s)
  Decrement :: forall s. R (Int,s) (Int,s)
  Deref :: forall s1 s2. RRef s1 s2 -> R s1 s2
  Rec :: forall s1 s2. (RRef s1 s2 -> R s1 s2) -> R s1 s2
  IsZero :: forall s. R (Int,s) (Bool,s)
  If :: forall s1 s2. R s1 s2 -> R s1 s2 -> R (Bool,s1) s2
  Swap :: forall s a b. R (a,(b,s)) (b,(a,s))
  Over :: forall s a b. R (a,(b,s)) (a,(b,(a,s)))
  Rot :: forall s a b c. R (a,(b,(c,s))) (b,(c,(a,s)))

instance Category R where
  id = Id
  (.) = Compose

fib :: R (Int,()) (Int,())
fib =
  Lit 0 >>>
  Lit 1 >>>
  Rot >>>
  Rot >>>
  Rec (\ref ->
    Dup >>> IsZero >>> (
      If
        (Drop >>> Swap >>> Drop)
        (Decrement >>> Rot >>> Rot >>> Over >>> Add >>> Rot >>> Rot >>> (Deref ref))
    )
  )

Rこれはインデックス付きのモノイドで、 と同じであることがわかりますCategory。R操作前後のスタックの型シグネチャを表す 2 つの型パラメーター。アセンブリ コードのような、プログラム スタックとしてのスタック。スタック型のタプルは、異種のリストを形成して、スタック上の各要素を型付けします。すべての操作 (If を除く) はパラメーターを使用せず、スタックを操作するだけです。If は 2 つのコード ブロックを受け取り、パラメーターをとらず、スタックを操作するだけのコードを返します。

Rec再帰に使用されます。インタープリターは再帰関数の一意の名前 (整数として) を見つけ、再帰関数はその名前を参照してDeref、再帰を形成するそれ自体にワイヤバックします。

これは、スタック上の値に対してタイプセーフであることを除いて、Forth のような連結プログラミング言語 (EDSL として) と考えることができます。

于 2016-06-26T09:41:22.387 に答える