3

有用な議論と完全な実装を伴う再帰スキーム (RS) の使用法を説明するハイロモヒズムの例を探しているときに、@amalloy による SO に関する素敵な投稿に出くわしました。

{-# LANGUAGE DeriveFunctor #-}
import Control.Arrow ( (>>>), (<<<) )

newtype Term f = In {out :: f (Term f)}

type Algebra f a = f a -> a
type Coalgebra f a = a -> f a

cata :: (Functor f) => Algebra f a -> Term f -> a
cata fn = out >>> fmap (cata fn) >>> fn

ana :: (Functor f) => Coalgebra f a -> a -> Term f
ana f = In <<< fmap (ana f) <<< f

hylo :: Functor f => Algebra f b -> Coalgebra f a -> a -> b
hylo alg coalg = ana coalg >>> cata alg

data ChangePuzzle a = Solved Cent
                    | Pending {spend, forget :: a}
                    deriving Functor

type Cent = Int
type ChangePuzzleArgs = ([Cent], Cent)
coins :: [Cent]
coins = [50, 25, 10, 5, 1]

divide :: Coalgebra ChangePuzzle ChangePuzzleArgs
divide (_, 0) = Solved 1
divide ([], _) = Solved 0
divide (coins@(x:xs), n) | n < 0 = Solved 0
                         | otherwise = Pending (coins, n - x) (xs, n)

conquer :: Algebra ChangePuzzle Cent
conquer (Solved n) = n
conquer (Pending a b) = a + b

waysToMakeChange :: ChangePuzzleArgs -> Int
waysToMakeChange = hylo conquer divide

コードは期待どおりに機能します。RSの側面についてはすでに漠然とした直感を持っていますが、私はまだ疑問に思っています:

  1. これは組み合わせを数えることに関するものなので、なぜSolved CentですかSolved Int? (これは、たとえそれが妥当な質問であったとしても、つまらないことのように聞こえるかもしれませんが、それが以下の残りの不確実性の根源である可能性があることを願っていますが、もっと基本的なことを見逃していると思います!)。
  2. 後で合計するので、divideでSolved0/1 はおそらく失敗/成功を意味しますか?
  3. に、およびをconquer追加するとはどういう意味ですか? これらの 2 つの値 ( s として) は何を意味し、このコンテキストでそれらの合計は何を意味するのでしょうか?abPendingCent
  4. ではconquer、単に s を合計する必要があると予想していましたがSolved、著者はこれに触れていますが、ケースがどのように寄与しているかはまだ明らかではありません(Pendingたとえば、修正は機能に悪影響を及ぼし、おそらく手がかりです)を返す、またはそのケースが固定されている定数)。conquer (Pending a b) = 11 waysToMakeChange11
  5. in conquer、aおよびbはCentsですが、 individeはChangePuzzleArgs(別名([Cent], Cent)) です。その変換はどこで発生しますか?

注：SOが初めてなので、元の回答の下にコメントできませんでした。これはより適切だったかもしれませんが、これがそのまま役立つことを願っています。

4

1 に答える 1