Generic Haskell：確定構造函數是否遞歸

Question

我想編寫一些可以處理Haskell中的所有數據類型的函數（至少Data.Data中的所有Data實例）。我遇到的一個普遍問題是根據構造函數是否遞歸來選擇做什麼 - 通過遞歸構造函數我的意思是數據類型是D，並且存在構造函數C，其中一個參數是D.

我可以通過解決一個更簡單的問題來解決上述問題：給定一個數據，確定最外層的構造函數是否是遞歸的。

這裏是嘗試數1：

data B a = T | F 
gIsLeafCons :: (Data a) => a -> B a 
gIsLeafCons m = gfoldl (\x y -> F) (\x -> T) m 

的想法是，如果構造是遞歸的，那麼我們回到˚F否則我們返回T.這第一眼的偉大工程：

gIsLeafCons 1 ==> T 
gIsLeafCons ([] :: [Int]) ==> T 

然而，gfoldl是多態的，所以給定樹數據類型如

data Tree a = Leaf a | Node (Tree a) (Tree a) 

我們失敗了。

gIsLeafCons (Leaf 1) ==> F 

其原因是（1葉）不是一個真正空構造：它有參數1，依此構造函數（\ X Y - > F）被施加。

嘗試數2：

我們可以用「葉子構造」走的是一個所有兒童評估爲F.這是一個略有改善：

gIsLeafByChild (Leaf 1) ==> T 

但是，如果葉子舉行不同的遞歸結構;這將再次失敗。

gIsLeafByChild (Leaf (Leaf 1)) ==> F 

我真的想停在第一個「葉構造」，但gfoldl的多態特性使得它似乎很難做到這一點，因爲上面看到的。

最後，有沒有辦法來指出構造函數是否是「葉構造函數」。我目前的解決方案是讓用戶傳入一個葉構造函數列表（[Constr]），然後檢查構造函數是否是其中之一。但是，如果能夠自動推斷出該列表中是否有東西，那就太好了。

Answer 1

使用gfoldl您有一個很好的開始。我們需要做兩個改變。首先，當我們遍歷結構時，我們需要跟蹤每個遇到的類型，看看它們是否遞歸發生。其次，我們需要遞歸地使用gfoldl來查看我們在構造函數中發現的類型。

讓我們來看看一些實用工具。當我們完成時，bool將得到Bool結果，而bId將把B從一種類型轉換爲另一種類型。

{-# LANGUAGE DeriveDataTypeable #-} 
{-# LANGUAGE RankNTypes #-} 

import Data.Data 

data Tree a = Leaf a | Node (Tree a) (Tree a) 
    deriving (Data, Typeable) 

data B a = T | F 

bool :: B a -> Bool 
bool T = True 
bool F = False 

bId :: B a -> B b 
bId T = T 
bId F = F 

我們可以得到該類型的代表性，或TypeRep，從Typeable類。 Typeable是Data的超類，所以無論何時我們對某個a有一個Data a實例，我們也將有一個Typeable a實例。我們將通過在[TypeRep]中攜帶包含類型表示的列表來跟蹤這些內容。

recursivelyConstructed :: Data a => a -> Bool 
recursivelyConstructed = bool . rc [] 
    where 
     cf :: forall d. d -> B d 
     cf = const F   
     rc :: forall d. Data d => [TypeRep] -> d -> B d 
     rc ts d = gfoldl (rc' (typeOf d:ts)) cf d 
     rc' :: forall d b. Data d => [TypeRep] -> B (d -> b) -> d -> B b 
     rc' _ T _ = T 
     rc' ts F d = 
      if elem (typeOf d) ts 
      then T 
      else bId . rc ts $ d 

讓我們嘗試一些例子

infiniteTree = Node infiniteTree infiniteTree 

recursivelyConstructed (Leaf 1      :: Tree Int) = False 
recursivelyConstructed (Node (Leaf 1) (Leaf 2)  :: Tree Int) = True 
recursivelyConstructed (infiniteTree     :: Tree Int) = True 
recursivelyConstructed (Leaf (Leaf 1)     :: Tree (Tree (Int))) = False 
recursivelyConstructed (Just (Leaf 1)     :: Maybe (Tree Int)) = False 
recursivelyConstructed (Just (Node (Leaf 1) (Leaf 2)) :: Maybe (Tree Int)) = True 
recursivelyConstructed (Just infiniteTree    :: Maybe (Tree Int)) = True 
recursivelyConstructed (Just (Leaf (Leaf 1))   :: Maybe (Tree (Tree Int))) = False