`tails`の再帰スキームの一般化

Question

私は再帰スキームスタイルの構造を持っています。完全構造を含むすべての部分構造のリストを取得したいと思います - List 。 paraを呼び出すことでこれを実装し、各ステップで元の構造にマッピングしてから別のものを前面に貼り付けることは可能だと思いますが、それは非常に扱いにくいようです。（Haskellが間違っていれば、私は本当にまだBase構造を理解していないようMuの用語で書かれた）

gtails :: Functor f => Mu f -> [Mu f] 
gtails = para (\a -> (fmap fst a) : (foldMap snd a)) 

（すなわち場合f=Primには、これはtailsで、他のfことが一般化だ）

よりよい方法はあります？これはあまり悪くはないが、fmap fst aはその段階で元の構造を回復するのがかなり面倒だと感じている.はparaを使ったときに自分自身がたくさん繰り返していることが分かっている（fold aの場合はcataそれは不要です）。

Answer 1

paraとは何の問題もありません。リストにしてrecursion-schemesせずに専門の明確化のために

import Data.Functor.Foldable 

tails :: [a] -> [[a]] 
tails = para (\case Nil -> [[]]; Cons a (as, res) -> (a : as) : res) 

、：：ちょうど頭と各Cons段階で尾をバックCONS

para :: (a -> [a] -> b -> b) -> b -> [a] -> b 
para f z []  = z 
para f z (a:as) = f a as (para f z as) 

tails :: [a] -> [[a]] 
tails = para (\a as res -> (a : as) : res) [[]] 

をしかし、あなたは、より一般的になりたい場合は、それほど素敵para製剤は便利来る：

import qualified Data.Functor.Foldable as Rec (Foldable) 

tails :: (Rec.Foldable t, Base t ~ Prim [a]) => t -> [t] 
tails as = as : para (\case Nil -> []; Cons a (as, res) -> as : res) as 

これはいつものようにリストのために働くが、あなたはまた、type instance Base t = Prim [a]を与えることができます他のt -sとFoldableインスタンスと一緒に使用し、同様に使用します。

代わりに、我々は制約を導入する費用で最初のtailsの定義を維持することができます：

tails' :: (Unfoldable t, Rec.Foldable t, Base t ~ Prim [a]) => t -> [t] 
tails' = para (\case Nil -> [embed Nil]; Cons a (as, res) -> embed (Cons a as) : res) 

各projectためにファンクタのfixpointsのための逆embedがあるはずですので、これは、あまりにも悪いことではありませんとにかく、Foldableとインスタンスは自然にペアになります。

Answer 2

paraが実際にここで使用する機能です。私はself-contained gistにすべてを入れて、それを試してみたいと思ったら例を追加しました。

固定点Muと通常のfoldとparaの定義から始めます。

module Tails where 

import Data.Function 

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

fold :: Functor f => (f a -> a) -> Mu f -> a 
fold alg = alg . fmap (fold alg) . out 

para :: Functor f => (f (a, Mu f) -> a) -> Mu f -> a 
para alg = alg . fmap (\m -> (para alg m, m)). out 

私たちは、その後paraと私たちは、リストモノイドに中間結果を収集するためにfoldMapを使用することができ、追加のFoldable制約を使用してtailsを実装することができます

tails :: (Functor f, Foldable f) => Mu f -> [Mu f] 
tails m = m : para (foldMap $ uncurry $ flip (:)) m