访问节点列表

Question

我正在为即将到来的考试学习。

我们获得了一些用于准备和培训的功能。

我想要一个函数，如果恰好有 2 个节点具有相同的值，则返回 True。

鉴于：

data Tree a = Node a [Tree a] | Leaf a

exercise62 :: Eq a => Tree62 a -> Bool
exercise62 = undefined

exercise62 (Node 5 [Node 6 [Leaf 4], Node 4 [Leaf 3]]) ~> True
exercise62 (Node 5 [(Node 5 [Leaf 4])]) ~~> True
exercise62 (Node 5 [Node 6 [Leaf 4], Node 3 [Leaf 2]]) ~~> False

我的想法是：

1.) 创建一个函数，它将给出一个包含所有值的列表。

2.) 检查是否有值出现两次

我的问题是 1.)

到目前为止我尝试了什么：

exercise62Helper :: Eq a => Tree a -> [a]
exercise62Helper (Leaf a) = [a]
exercise62Helper (Node a b) = [a] ++ exercise62Helper (head b)

我认为我的问题是 exercise62Helper (head b) 因为我只检查列表的第一个元素而不是 [Tree a] 中的所有元素。

但我不明白如何准确地访问它们，通常我会通过 tail 访问它们，但这是不可能的（或者我不知道），因为函数的参数是 Tree 而不是 [Tree]

Answer 1

您可以使用 concatMap :: Foldable f => (a -> [b]) -> f a -> [b] 将 b 的所有元素映射到 exercise62Helper，并连接结果。您的函数还 not 需要 Eq a 类型约束，因为无论您是否可以检查两个项目是否相等，您都可以列出这些项目：

exercise62Helper :: Tree a -> [a]
exercise62Helper (Leaf a) = [a]
exercise62Helper (Node a b) = a : <strong>concatMap</strong> exercise62Helper b

您还可以使用 DeriveFoldable extension，让 Haskell 为您的类型生成一个 Foldable 的普通实例：

{-# LANGUAGE <strong>DeriveFoldable</strong> #-}

data Tree a = Node a [Tree a] | Leaf a deriving <strong>Foldable</strong>

exercise62Helper 是 toList :: Foldable f => f a -> [a] 的特殊版本：

import Data.Foldable(<strong>toList</strong>)

exercise62Helper :: Tree a -> [a]
exercise62Helper = <strong>toList</strong>

访问节点列表

accessing a list of nodes

tree

haskell