递归方案概括了`tails`

Question

我有一个递归方案样式结构,我想获得所有子结构的列表,包括完整的结构 - 即相当于tails函数在a上的作用List.我认为可以通过调用para,在每一步映射回原始结构,然后将原始结构分别保留在前面来实现这一点,但这看起来非常麻烦:(未经测试,如果Haskell不正确,请写道歉;写的来讲Mu,因为我还没有真正理解Base结构尚)

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

(即在这种情况下,对于其他情况,f=Prim这是一个概括)tailsf

有更好的方法吗？我意识到这并不是那么糟糕,但是fmap fst a在那一步恢复"原始"结构感觉相当麻烦,并且foldMap snd a我发现自己在使用时会重复很多para(同样fold a在使用时cata再次感觉它应该是不必要的) .

Answer 1

我没有看到任何问题para.只需在每Cons一步都收回头部和尾部:

import Data.Functor.Foldable

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

为清楚起见,专门用于列表和没有recursion-schemes:

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以引入Unfoldable约束为代价保留第一个定义:

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应该有一个反函数embed的修饰点,所以这些Foldable和Unfoldable实例自然成对出现.