3

私は現在、 JohnHughesによるProgrammingwith Arrowsの論文を読んでおり、セクション2.5の20ページの最初の演習ですでに困惑しています。

自由に使える型クラスと型クラス、および型を介した関数、流れ関数Arrow、モナディック関数のインスタンスがあります。ArrowChoice[a] -> [b]a -> m bKleisli

mapA例が示されました：

mapA f = arr listcase >>>
         arr (const []) ||| (f *** mapA >>> arr (uncurry (:)))

これが試みです：

listcase :: [a] -> (Either () (a,[a]))
listcase [] = Left ()
listcase (x:xs) = Right (x,xs)

helper :: (Bool,a) -> [a] -> Either (a,[a]) [a]
helper (True,x)  y = Left (x,y)
helper (False,x) y = Right y

test :: Arrow a => (b -> Bool) -> a (b,c) ((Bool,b), c)
test p = first (arr p &&& arr id)

filterA :: Arrow a => (b -> Bool) -> a [b] [c]
filterA p = f >>> (g ||| (h >>> (j ||| (filterA p))))
   where f = arr listcase
         g = arr (const [])
         h = test p >>> (uncurry helper)
         j = (arr id *** (filterA p)) >>> (arr (uncurry (:)))

この無駄な試みの背後にある（ブルートフォース）理論的根拠は次のとおりです。次の2つの選択肢があります：filterAlikelistcaseとmap、述語を適用した結果p。mapそれは、リストをチェックし、を使用してEither値を返すように開始しますlistcase。空のリストgが適用される場合、それ以外の場合は、の右側のすべてが、およびをそれぞれ含む|||タイプの値に適用されます。関数が最初に適用されます。これは、を保持しながら述語を適用し、タイプの値を返します。これはに渡され、値に応じて保持するかどうかを決定します。結果を次のように返します(a,[a])headtailhhead((Bool, head),tail)(uncurry helper)headBoolEither選択方法を適用できるように値を設定します(|||)。この値は次の選択肢に渡されます。つまり、保持されて(j ||| (filterA p))いる述語が、とを含むペアに適用されるようにします。に適用されている間、を使用してフィルタリングされます。両方の結果がペアとして返されます。次に、このペアはlikeを使用して調整されます。それ以外の場合は、が単独で渡されます。Truejheadtailheadidfilter ptailarr (uncurry (:))maptailfilterA p

私がそれを実現するのと同じくらい難しいとは思えませんが、私はかなり明白な何かを見逃していると思います。

4

2 に答える 2

3

申し訳ありませんが、私はあなたのロジックに完全に従っていませんが、矢印以外のコードが何をするか見てみましょう. これ

  • リストが空かどうかを確認し、空である場合はそれを返します
  • それ以外の場合は、リストの先頭を取り除き、要素を呼び出しますx
  • リストの残りを再帰し、結果を呼び出しますys
  • ヘッドで述語pが true の場合、 に追加xしysます。
  • それ以外の場合は、戻りますys

[listcase最初の 2 つのタスクを実装する] 関数は良さそうですが、リストを返していることを思い出してunitくださいconst []。

最後の 2 つのケースでは 3 番目の箇条書きの再帰コードが埋もれていますが、私はそれを直接公開していますが、問題ありません。

最後のマージでは、 を使用して記述し|||ますが、ターゲット カテゴリで他の矢印を構成する必要がないため、関数を持ち上げてすべての作業を行うこともできます。以下の私のコードでは、それはrejoin.

filterA :: forall arr a. ArrowChoice arr => arr a Bool -> arr [a] [a]
filterA p = arr lstcase >>> (filterRest ||| id) where
    -- left if has a head, right otherwise
    lstcase :: [a] -> (Either (a, [a]) [a])
    lstcase (x:xs) = Left (x, xs)
    lstcase [] = Right []

    -- if we got a head, then
    --     for the head ("first" in code), map this to itself and p's result on it
    --     recurse on the rest of the list ("second" part)
    --     append the element to the recursion result if p's result is true
    filterRest :: arr (a, [a]) [a]
    filterRest = (first (id &&& p) >>> second (filterA p) >>> arr rejoin)

    rejoin :: ((a, Bool), [a]) -> [a]
    rejoin ((x, True), rest) = x:rest
    rejoin ((x, False), rest) = rest

確かに***、&&&、|||、first、 などで自分の考えを明確に表現するには時間がかかります。

ちょっと批評。

  • 彼らが求めている機能を実装していることを確認してください!! 生の関数だけを使用する場合pは、宣言することもできますfilterA = arr filter。あなたは本当に持ち上げられた矢を取りたいですp。とはいえ、変更は のp代わりに単純に入力することになるarr pため、コードは正しい考えを持っています。
  • (uncurry helper)は矢印空間にあるものではなく、単なる生の関数です。

このようなものを開発するとき、私は通常スケルトンを書き、型を宣言します。それは何が起こっているのかを理解するのに役立ちます。たとえば、私は

filterA :: ArrowChoice arr => arr a Bool -> arr [a] [a]
filterA p = arr lstcase >>> (filterRest ||| id) where
    -- left if has a head, right otherwise
    lstcase :: [a] -> (Either (a, [a]) [a])
    lstcase = undefined

    filterRest :: arr (a, [a]) [a]
    filterRest = undefined

faただし、宣言に追加するときは、 forが for (型変数スコープ)と同じfilterRestであることを伝える必要があるため、上記のように使用します。arrfilterRestfilterAforall arr a.

于 2011-07-19T02:09:26.460 に答える
2

ここに少し単純化があります：

test :: Arrow a => (b -> Bool) -> a b ([b] -> [b])
test p = arr $ \b -> if p b then (b:) else id
         
filterA :: Arrow a => (b -> Bool) -> a [b] [b]
filterA p = f >>> (g ||| h)
  where f = arr listcase
        g = arr id
        h = (test p *** filterA p) >>> (arr (uncurry ($)))

filterA' :: Arrow a => a b Bool -> a [b] [b]
filterA' p = f >>> (g ||| h)
  where f = arr listcase
        g = arr id
        h = (i *** filterA p) >>> (arr (uncurry ($)))
        i = proc x -> do 
              b <- p -< x
              returnA -< if b then (x:) else id
于 2011-07-19T02:20:24.237 に答える