表示有限（非遞歸）代數類型值的最有效方法是什麼？

序列化僅由構造函數構成的有限（非遞歸）代數數據類型的最有效方法是什麼？表示有限（非遞歸）代數類型值的最有效方法是什麼？

例如

p = A 
    | B q 

q = C 
    | D r 
    | E 

r = F 
    | G

手動枚舉所有有效組合爲這個平凡的小的定義是可能的：

A  0x00 
B C 0x01 
B D F 0x02 
B D G 0x03 
B E 0x04

是否有更廣泛的理論在這裏？
如果我們添加非構造函數類型（如int等），那麼該怎麼辦？如何在內存中表示這些（它允許遞歸，所以指針/引用可能是必要的）？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

來源

2013-03-22 fadedbee

沒有完全標準的類來做到這一點，但自己做一個很容易。我就勾勒這樣做的一種方法：

data P = A | B Q deriving Show 
data Q = C | D R | E deriving Show 
data R = F | G deriving Show 

class Finite a where 
    allValues :: [a] 

instance Finite P where 
    allValues = [A] ++ map B allValues 

instance Finite Q where 
    allValues = [C] ++ map D allValues ++ [E] 

instance Finite R where 
    allValues = [F] ++ [G]

我寫的情況下，這種方式表明，它很容易和機械，並且可以通過程序來實現（例如，使用泛型編程或模板哈斯克爾）。您還可以添加一個實例做一些跑腿的你，所提供的類型爲Bounded和Enum erable：

instance (Bounded a, Enum a) => Finite a where 
    allValues = [minBound..maxBound]

如果你現在添加deriving (Bounded, Show)到R，這是一個少寫實例！

不管怎樣，現在我們可以評估allValues :: [P]並取回[A,B C,B (D F),B (D G),B E] - 然後你就可以用zip[0..]讓你的編碼等。

但是這肯定是以前做過的！我沒有使用過多的序列化（如果有的話），但快速搜索顯示the binary package和the binary-derive package可以爲您做類似的事情，而無需親自編寫實例。我會看看那些人是否會先做你想做的事。

來源

2013-03-22 17:10:21 yatima2975

對於內存中的haskell表示，由於結構是懶惰的，所以我們無法完整地表示事物，這意味着我們需要每個級別的間接指向。也就是說，拆包可以讓你一起粉碎這些東西。但是，據我所知，它不會將嵌套構造函數的位打包到同一個單詞中。

有一個指針標記優化是猛推關於在指針的構造，引導到它的一些信息：http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/HaskellExecution/PointerTagging

更多關於拆包看到這一點：http://www.haskell.org/haskellwiki/Performance/Data_types#Unpacking_strict_fields

來源

2013-03-22 17:21:19 sclv

表示有限（非遞歸）代數類型值的最有效方法是什麼？

回答

相關問題