固定點上的Monoidal褶皺

給定具有固定點的任意數據結構，我們可以構造一個monoidal代數而無需手動指定所有情況嗎？固定點上的Monoidal褶皺

假設我們得到如下的數據類型Expr。使用庫，我們可以派生出一個基函數ExprF，它自動也有Functor,Foldable和Traversable實例。

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-} 
{-# LANGUAGE TypeFamilies #-} 
{-# LANGUAGE TemplateHaskell #-} 

import Data.Semigroup (Sum(..)) 
import Data.Functor.Foldable 
import Data.Functor.Foldable.TH 

import Prelude hiding (fail) 

data Expr = Var String 
      | Const Int 
      | Add [Expr] 
      | Mult [Expr] 
      deriving Show 

$(makeBaseFunctor ''Expr) 

expr :: Fix ExprF 
expr = ana project $ Add [Const 1, Const 2, Mult [Const 3, Const 4], Var "hello"]

現在，讓我們說，我們希望計算expr葉片數。我們可以很容易地編寫一個代數這樣一個小數據結構：現在

alg (ConstF _) = 1 
alg (VarF _) = 1 
alg (AddF xs) = sum xs 
alg (MulF xs) = sum xs

，我們可以稱之爲cata alg expr，它返回5，正確的結果。

讓我們假設Expr增長真的很大，也很複雜，我們不想爲所有數據構造函數手動編寫案例。 cata如何知道如何結合所有案例的結果？我懷疑這是可能的，使用Monoid s，可能與Const仿函數（雖然不完全確定最後一部分）。

fail = getSum $ foldMap (const (Sum 1) . unfix) $ unfix expr

fail回報4，而我們實際上有5葉子。我認爲問題在於固定點，因爲我們只能剝離一層Fix ing，因此Mult [..]只計爲一片葉子。

是否有可能以某種方式摺疊一般在整個固定點和不手動指定所有實例Monoid樣結構收集結果嗎？我想要的是一種foldMap，但採用更通用的方式。

我有一種感覺，我失去了一些真正明顯的東西。

來源

2017-06-07 ThreeFx

'fail'計算'expr'頂部節點的子節點。一般來說，它離樹葉不遠。這不是合適的'cata'的'alg'。 – pigworker

@pigworker我有同樣的懷疑。現在我所尋找的是一個積累的變形，我不必爲60個案例（每個構造函數一個）編寫，而是在遞歸案例中使用monoid屬性。我覺得這應該是可能的，但我不知道如何去解決這個問題。 – ThreeFx

葉的特徵是其子女的葉計數總和爲零，因爲沒有孩子。現在，考慮到孩子的葉子數（總和），你能計算父親的葉子數嗎？ – pigworker

以下是解決方案的精髓。我接通了

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable, PatternSynonyms #-}

讓我們回顧一下固定點和變形。

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

cata :: Functor f => (f t -> t) -> Fix f -> t 
cata alg = alg . fmap (cata alg) . out

代數，alg :: f t -> t，花費在孩子已經被換成了t值的節點，然後返回t父。 cata運算符通過解包父節點，遞歸處理所有子節點，然後應用alg來完成作業。

所以，如果我們要算在這種結構的葉子，我們就可以這樣開始：

leaves :: (Foldable f, Functor f) => Fix f -> Integer 
leaves = cata sumOrOne where 
    -- sumOrOne :: f Integer -> Integer

代數，sumOrOne可以看到在父節點的每個子葉片數。我們可以使用cata，因爲f是Functor。而且因爲f是Foldable，我們可以計算孩子的葉子總數。

sumOrOne fl = case sum fl of 
    ...

有那麼兩種可能性：如果父母沒有子女，其葉總和將0，我們可以檢測，但是這意味着母公司本身就是一個葉子，所以1應返回。否則，葉子總和將是非零的，在這種情況下，父親不是葉子，因此它的葉子總和實際上是其子葉子的總葉子總數。這給了我們

leaves :: (Foldable f, Functor f) => Fix f -> Integer 
leaves = cata sumOrOne where 
    sumOrOne fl{- number of leaves in each child-} = case sum fl of 
    0 -> 1 -- no leaves in my children means I am a leaf 
    l -> l -- otherwise, pass on the total

一個簡單的例子，基於赫頓的剃刀（有整數和另外的表達語言，它往往是說明了這一點最簡單的事情）。表達式由Hutton的函數生成。

data HF h = Val Int | h :+: h deriving (Functor, Foldable, Traversable)

我引入了一些模式同義詞來恢復定製類型的外觀和感覺。

pattern V x = In (Val x) 
pattern s :+ t = In (s :+: t)

我煮了一個簡單的例子表達，有些樹葉是三個層次的深度。

example :: Fix HF 
example = (V 1 :+ V 2) :+ ((V 3 :+ V 4) :+ V 5)

果然

Ok, modules loaded: Leaves. 
*Leaves> leaves example 
5

另一種方法是將函子和感興趣子可摺疊的，在這種情況下，在東西樹葉。（我們得到完全免費的單子。）

data Tree f x = Leaf x | Node (f (Tree f x)) deriving (Functor, Foldable)

一旦您完成了您的基礎設施建設的葉/節點分離部分，您可以直接與foldMap參觀的葉子。在有點Control.Newtype投擲，我們得到

ala' Sum foldMap (const 1) :: Foldable f => f x -> Integer

這是費爾貝恩閾值以下（即足夠短，不會需要沒有一個名字和所有的更清晰）。

當然，麻煩在於數據結構通常在多個有趣但相互衝突的方式中是「感興趣的子結構」中的函數。 Haskell並不總是讓我們訪問「找到的函數性」的最佳方式：當我們在聲明時參數化數據類型時，我們必須預測我們需要的函數性。但是仍然有時間來改變所有這些...

來源

2017-06-07 09:31:32 pigworker

固定點上的Monoidal褶皺

回答

相關問題