如何在Haskell中创建一个nullary数据构造函数返回True为null

Question

我说有一个代数数据类型

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

我想null返回True的Empty节点; 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不会返回True的Nothing.

> null Nothing
True

Answer 1

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

创建Foldablefor 的实例的最简单方法Tree a是:

{-# 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)