Cấu trúc kiểu đệ quy của `tails`

Question

Tôi có cấu trúc kiểu đệ quy và tôi muốn lấy danh sách tất cả các cấu trúc con bao gồm toàn bộ cấu trúc - tức là tương đương với chức năng tails trên List . Tôi nghĩ rằng nó có thể thực hiện điều này bằng cách gọi para, ánh xạ trở lại cấu trúc ban đầu ở mỗi bước, và sau đó gắn kết cấu trúc ban đầu ở phía trước một cách riêng biệt, nhưng điều đó có vẻ rất cồng kềnh: (chưa được kiểm chứng, xin lỗi nếu Haskell không chính xác; bằng văn bản về Mu như tôi đã không thực sự hiểu được Base xây dựng chưa)

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

(tức là trong trường hợp f=Prim đây là tails, cho f khác, nó là một sự tổng quát)

có cách nào đẹp hơn ? Tôi nhận thấy điều này không quá tệ, nhưng fmap fst a để khôi phục cấu trúc "ban đầu" ở bước đó cảm thấy khá cồng kềnh và foldMap snd a là thứ tôi thấy mình lặp lại rất nhiều khi sử dụng para (tương tự fold a khi sử dụng cata nó không cần thiết).

Answer 1

Tôi không thấy bất kỳ vấn đề nào với para. Chỉ cần Nhược điểm phía sau đầu và đuôi ở mỗi Cons bước:

import Data.Functor.Foldable 

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

Để rõ ràng, đặc biệt vào các danh sách và không có 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) [[]] 

Tuy nhiên, nếu bạn muốn trở thành tổng quát hơn, các ít đẹp para xây dựng đi kèm tiện dụng:

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 

này hoạt động cho các danh sách như thường lệ, nhưng bạn cũng có thể cung cấp cho type instance Base t = Prim [a] cho t -s khác, cùng với cá thể Foldable và sử dụng chúng.

Ngoài ra, chúng ta có thể giữ cho tails định nghĩa đầu tiên với chi phí giới thiệu một chế:

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) 

Đây không phải là quá xấu, vì đối với mỗi project có phải là một nghịch đảo embed cho fixpoints của functors dù sao, vì vậy các trường hợp Foldable và tự nhiên theo cặp.

Answer 2

para thực sự là chức năng phù hợp để sử dụng tại đây. Tôi đã đặt mọi thứ vào một số self-contained gist được tăng cường với các ví dụ nếu bạn muốn chơi với nó.

Chúng tôi bắt đầu với định nghĩa của fixpoint Mu và thông thường fold và 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 

Chúng ta có thể sau đó thực hiện tails sử dụng para và thêm Foldable hạn chế cho phép chúng ta sử dụng foldMap để thu thập các kết quả trung gian trong danh sách monoid:

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