38

私はそれを理解することになりました。私が行った講演のビデオとスライドをご覧ください。

元の質問:

一般的な再帰スキーム (つまり、 の使用Fix) を理解するための努力の中で、さまざまなスキームのリストのみのバージョンを作成すると便利であることがわかりました。実際のスキームを理解するのがはるかに簡単になります (追加のオーバーヘッドなしでFix)。

zygoただし、 と のリストのみのバージョンを定義する方法はまだわかりませんfutu。

これまでの私の専門的な定義は次のとおりです。

cataL :: (a ->        b -> b) -> b -> [a] -> b
cataL f b (a : as) = f a    (cataL f b as)
cataL _ b []       = b

paraL :: (a -> [a] -> b -> b) -> b -> [a] -> b
paraL f b (a : as) = f a as (paraL f b as)
paraL _ b []       = b

-- TODO: histo

-- DONE: zygo (see below)

anaL  :: (b ->       (a, b))               -> b -> [a]
anaL  f b = let (a, b') = f b in a : anaL f b'

anaL' :: (b -> Maybe (a, b))               -> b -> [a]
anaL' f b = case f b of
    Just (a, b') -> a : anaL' f b'
    Nothing      -> []

apoL :: ([b] -> Maybe (a, Either [b] [a])) -> [b] -> [a]
apoL f b = case f b of
    Nothing -> []
    Just (x, Left c)  -> x : apoL f c
    Just (x, Right e) -> x : e

-- DONE: futu (see below)

hyloL  :: (a -> c -> c) -> c -> (b -> Maybe (a, b)) -> b -> c
hyloL f z g = cataL f z . anaL' g

hyloL' :: (a -> c -> c) -> c -> (c -> Maybe (a, c))      -> c
hyloL' f z g = case g z of
    Nothing     -> z
    Just (x,z') -> f x (hyloL' f z' g)

histoリストに対してzygoとをどのように定義futuしますか?

4

3 に答える 3

13

まだ誰も答えてfutuいないので、つまずいてやってみようと思います。私は使用するつもりですListF a b = Base [a] = ConsF a b | NilF

型を取るrecursion-schemes: futu :: Unfoldable t => (a -> Base t (Free (Base t) a)) -> a -> t.

制約を無視して for にUnfoldable置き換えます。[b]t

(a -> Base [b] (Free (Base [b]) a)) -> a -> [b]
(a -> ListF b (Free (ListF b) a)) -> a -> [b]

Free (ListF b) a)リストであり、a末尾に - 型の穴がある可能性があります。これは に同型であることを意味し([b], Maybe a)ます。これで、次のようになりました。

(a -> ListF b ([b], Maybe a)) -> a -> [b]

最後の を削除すると、が に同形であるListFことがわかります。ListF a bMaybe (a, b)

(a -> Maybe (b, ([b], Maybe a))) -> a -> [b]

さて、タイプテトリスをプレイすることが唯一の賢明な実装につながると確信しています。

futuL f x = case f x of
  Nothing -> []
  Just (y, (ys, mz)) -> y : (ys ++ fz)
    where fz = case mz of
      Nothing -> []
      Just z -> futuL f z

結果の関数を要約するfutuLと、シード値と、少なくとも 1 つの結果を生成する可能性のある関数、および結果が生成された場合は新しいシード値が必要になる可能性があります。

最初はこれと同等だと思った

notFutuL :: (a -> ([b], Maybe a)) -> a -> [b]
notFutuL f x = case f x of
  (ys, mx) -> ys ++ case mx of
    Nothing -> []
    Just x' -> notFutuL f x'

実際には多かれ少なかれそうかもしれませんが、重要な違いの 1 つは、実数futuが生産性を保証することです (つまり、f常に返される場合、次のリスト要素を永遠に待つことはありません)。

于 2016-04-28T19:14:07.873 に答える