如何在 Haskell 中使空数据构造函数返回 True 表示空

Question

我有一个代数数据类型，比如

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

我希望null返回Empty节点的True; False否则。

例如

> tree = Empty
> null tree 

现在，这给出了以下错误。

<interactive>:261:1: error:
    • No instance for (Foldable Tree) arising from a use of ‘null’
    • In the expression: null tree
      In an equation for ‘it’: it = null tree

请注意，null 确实会返回Nothing的True。

> null Nothing
True

Answer 1

null需要一个Foldable的实例：null :: Foldable t => t a -> Bool

为Tree a创建Foldable实例的最简单方法是：

{-# LANGUAGE DeriveFoldable #-}
data Tree a = Node a (Tree a) (Tree a) | Empty deriving Foldable

或GHCi：

λ > :set -XDeriveFoldable
λ > data Tree a = Node a (Tree a) (Tree a) | Empty deriving Foldable
λ > null Empty
True
λ > null (Node 1 Empty Empty)
False

注意：null将True返回到Nothing的原因是Maybe具有Foldable的实例。

路漫漫其修远兮：

与其使用 Haskell 的神奇扩展使用快捷方式，不如按照此处的说明手动编写Foldable实例，它归结为：

data Tree a = Node a (Tree a) (Tree a) | Empty
instance Foldable Tree where
  -- The minimal definition is "foldMap" or "foldr", I'm choosing "foldr"
  -- foldr :: (a -> b -> b) -> b -> Tree a -> b
  foldr _ b Empty               = b
  foldr f b (Node a left right) = f a (foldr f (foldr f b right) left)