哈斯克爾幺折一朵

我需要做出一個可摺疊實例玫瑰樹數據結構：哈斯克爾幺折一朵

data Rose a = a :> [Rose a] 
    deriving (Eq, Show)

用下面的獨異與玫瑰有關的類/實例：

instance Functor Rose where 
    fmap f (a :> bs) = (f a) :> (map (fmap f) bs) 

class Monoid a where 
    mempty ::   a 
    (<>) :: a -> a -> a 

instance Monoid [a] where 
    mempty = [] 
    (<>) = (++)

我嘗試：

instance Foldable Rose where 
    fold (a:>b) = a <> (foldMap fold b)

但是，這不能正常工作，系統檢查我得到的錯誤：

*** Failed! Exception: 'Prelude.undefined': 
[] :> []

但我不知道爲什麼它不起作用，有人能幫我嗎？

在此先感謝！

最好的問候， Skyfe。

來源

2014-10-08 user2999349

而不是更新您的問題的解決方案，爲什麼不把它寫在這裏作爲答案？ – Sibi 2014-10-08 13:21:02

好的，沒有想到這種可能性！ – user2999349 2014-10-08 15:32:12

如何用'{--LANGUAGE DeriveFoldable - }'派生（可摺疊）'？ – viorior 2014-10-08 16:19:14

這似乎是我找到了我自己的問題的答案。

解決方案：

instance Foldable Rose where 
    fold (a:>b) = a <> (foldr (<>) mempty (map fold b))

不得不先附加每個元件與所述頭元件的列表（和做同樣爲每個結合元件的那些的玫瑰樹），則列表一起摺疊與一個非調整元素mempty。

來源

2014-10-08 15:31:06 user2999349

您的實施fold是正確的，沒有理由改變它。

問題是fold不足以定義Foldable。從the documentation：

class Foldable t where Source

Data structures that can be folded.

Minimal complete definition: foldMap or foldr .

所以，你必須定義foldMap或foldr（或兩者）。定義foldMap更簡單，更自然（在很多情況下也更加有效）。所以，你應該寫類似：

import Data.Foldable 
import Data.Monoid 

data Rose a = a :> [Rose a] 
    deriving (Eq, Show) 

instance Foldable Rose where 
    foldMap f (x :> xs) = f x <> foldMap (foldMap f) xs

來源

2014-10-08 18:31:56

這僅僅是切向相關，但如果你認識到玫瑰樹是一樣Cofree []從Control.Comonad.Cofree，那麼你可以從摺疊實例獲得Foldable例如「免費」的[]像這樣：

import Control.Comonad.Cofree 
import Data.Foldable as F 

type RoseTree = Cofree []

加載它到GHCI：

λ> let tree = 1 :< [1 :< [], 2 :< [], 3 :< []] :: RoseTree Int 
λ> :t F.foldr (+) 0 tree 
F.foldr (+) 0 tree :: Int 
λ> F.foldr (+) 0 tree 
7

您還可以舉st派生出Foldable，或編寫自己的實現（就像你已經完成的那樣）。

來源

2014-10-08 20:42:26

雖然OP說，他/她已經找到了答案，該解決方案缺乏基本情況：

instance Foldable Rose where 
    fold (a:>[]) = a <> mempty 
    fold (a:>b) = a <> (foldr (<>) mempty (map fold b))

否則關於非詳盡模式在功能倍的厚望將被拋出。

來源

2015-12-11 15:05:31 vrs

哈斯克爾幺折一朵

回答

相關問題