矢印のフィルタ関数を定義するにはどうすればよいですか？

Question

私は現在、ジョン・ヒューズ によって紙Programming with Arrowsを読んだし、私はすでに、セクション2.5で、最初の演習に困惑PG 20

に私達は私達の処分でArrowとArrowChoice型クラスを持っている、など関数のインスタンス、ストリーム関数[a] -> [b]、およびKleisli型を使用するモナディック関数a -> m bが含まれます。

mapA例が与えられた。

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つの選択肢があります

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

ここでの試みですfilterA：listcaseはmapのようになり、述語pを適用した結果。 mapのように開始し、リストをチェックしてlistcaseを使用してEither値を返します。空のリストgが適用されている場合は、|||の右側のすべてが(a,[a])タイプの値に適用され、それぞれheadとtailが含まれます。最初にh関数が適用され、headのまま述部が適用され、((Bool, head),tail)の値が戻されます。これは(uncurry helper)に渡され、は、Boolの値に応じてheadを保持するかどうかを決定します。結果はEitherという値で返され、選択方法(|||)が適用されます。この値は(j ||| (filterA p))に渡され、Trueの場合、jという語句がheadとtailを含むペアに適用されるようになります。 headは、idを使用してフィルタリングされ、filter pは、tailに適用されます。両方の結果はペアとして返されます。このペアは、arr (uncurry (:))（mapなど）を使用して調整されます。それ以外の場合はtailがfilterA pにのみ渡されます。

私はそれを作るようには難しいとは思っていませんが、私はかなり明白なものを欠いていると思います。

Answer 1

申し訳ありません申し訳ありませんが、あなたのロジックをよく守っているわけではありませんが、は、矢印以外のコードはです。これをチェックリストが空であるかどうかを確認するために、そう

は、そうでない場合は、リストオフの頭を引っ張ることを返す場合、リストの残りの部分にx

再帰的要素を呼び出すには、呼び出し

• 結果ys
• 述語pが頭に当てはまる場合は、xにysを追加します。あなたがリストを返しているので、同様にその代わりにunitとconst []を通じて再マッピング返すことがあります覚えているものの
• そうでなければ、我々は[最初の2つのタスクを実装する] listcase機能ys

を返すが、よさそうです。

最後の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を取りたいと思っています。つまり、変更はarr pの代わりにpと入力するだけで済みますので、コードには正しい考えがあります。
• (uncurry helper)は、矢印のスペースには何もないので、単なる未加工の機能です。

このようなものを開発するときには、通常、スケルトンを記述して型を宣言します。それは何が起こっているのか把握するのに役立ちます。あなたはfilterRestためarrがfilterA（タイプ変数のスコープ）のためのものと同じであることを伝える必要があり、しかしfilterRest宣言にfaを追加し、そうforall arr a.を使用する場合たとえば、私は

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 

で開始しました上記のように。ここで

Answer 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