在Haskell中获取自定义列表类型的头和尾

Question

我有一个自定义的列表类型：

data NNList a = Sing a | Append ( NNList a) ( NNList a) deriving (Eq)
data CList a = Nil | NotNil ( NNList a) deriving (Eq)

我将尝试实现一个函数，该函数返回列表的头部和尾部：

cListGet :: CList a -> Maybe (a, CList a)

下面是我的尝试：

cListGet :: CList a -> Maybe (a, CList a)
cListGet Nil             = Nothing
cListGet xs@(NotNil nxs) =
case nxs of
  Sing x        -> (x, Nil)
  Append l r    -> ((fst $ cListGet (NotNil l)), (Append (snd $ cListGet (NotNil l)), r))

对我来说，这意味着继续向左走，直到我得到一个单一的元素。一旦我得到单一的元素（头部），返回该元素和一个Nil列表。然后将此Nil列表与列表组合，最后将其作为最终结果返回。

我甚至不确定逻辑是否100％正确。

- rlhh

Answer 1

嗯，人们通常会将您拥有的数据结构称为树形结构，而不是列表。但无论如何...

问题＃1：Haskell对缩进很敏感，而您的case表达式没有缩进。这会导致解析错误。

问题＃2，也是更大的问题：您还没有理解Maybe类型的工作原理。我得到的印象是，您认为它的工作方式类似于更常见的语言中的null值，这使您困惑了。

在像Java这样的语言中，null是一个可以出现在几乎任何其他值的值。如果我们有以下签名的方法：

public Foo makeAFoo(Bar someBar)

如果它是这两种方式之一，那么将其称为任何一种都是合法的：

// Way #1: pass in an actual value
Bar theBar = getMeABar();
Foo result = makeAFoo(theBar);

// Way #2: pass in a null
Foo result2 = makeAFoo(null)

theBar和null在某种意义上是"并列的"，或者更准确地说，它们具有相同的类型——您可以在程序中用一个替换另一个，在这两种情况下都能编译。

另一方面，在Haskell中，字符串"hello"和Nothing 没有相同的类型，您不能在一个位置使用另一个。Haskell区分这三件事：

1. 必须存在的字符串："hello" :: String
2. 可选字符串的缺失：Nothing :: Maybe String
3. 可选字符串的存在：Just "hello" :: Maybe String

#1和#3之间的区别是您的函数中系统性遗漏的东西。对于Maybe a，在您有值的情况下，您必须使用Just，它充当一个包装器来表示"这不仅仅是一个a，而是一个Maybe a。"

您错过Just的第一个位置是case表达式的右侧，我们可以像这样修复它：

-- This still fails to compile!
cListGet :: CList a -> Maybe (a, CList a)
cListGet Nil             = Nothing
cListGet xs@(NotNil nxs) =
    case nxs of
                       -- I added 'Just' here and in the next line:
      Sing x        -> Just (x, Nil)
      Append l r    -> Just (fst $ cListGet (NotNil l), (Append (snd $ cListGet (NotNil l)), r))

但问题并没有结束，因为你使用了 fst $ cListGet (NotNil l)，它存在相反的问题：cListGet 返回的是 Maybe (a, CList a)，但 fst 作用于 (a, b) 而不是 Maybe (a, b)。你需要对 cListGet 的结果进行模式匹配，以测试它是 Nothing 还是 Just (x, l')。（同样的问题也出现在你的 snd $ cListGet (NotNil l) 中。）

第三，你错误地使用了 Append 构造器。你把它写成了 (Append foo, bar) 的形式，foo 和 bar 之间不应该有逗号。在 Haskell 中，这种情况会给你带来比大多数其他语言更令人困惑的错误消息，因为当 Haskell 看到这个时，它不会告诉你“你犯了一个语法错误”；Haskell 比大多数语言更字面，所以它认为你正在尝试构建一个以 Append foo 为第一个元素，以 bar 为第二个元素的对，因此它得出结论 (Append foo, bar) 必须具有类型 (NNList a -> NNList a, NNList a)。

第四个问题，也是最后一个问题：你设定的问题没有明确定义，因此没有好的答案。你说想要找到 CList a 的“头”和“尾”。这是什么意思？对于 Haskell 中的 [a] 类型，其构造器为 [] 和 :，这是很清楚的：头是 x:xs 中的 x，而尾是 xs。

就我理解的来说，你所说的“头”的意思似乎是递归结构的最左边的元素。我们可以这样得到它：

cListHead :: CList a -> Maybe a
cListHead Nil = Nothing
-- No need to cram everything together into one definition; deal with
-- the NNList case in an auxiliary function, it's easier...
cListGet (NotNil nxs) = Just (nnListHead nxs)

-- Note how much easier this function is to write, because since 'NNList'
-- doesn't have a 'Nil' case, there's no need to mess around with 'Maybe'
-- here.  Basically, by splitting the problem into two functions, only
-- 'cListHead' needs to care about 'Maybe' and 'Just'.
nnListHead :: NNList a -> a
nnListHead (Sing a) = a
nnListHead (Append l _) = nnListHead l

因此，您可能认为“尾部”是其他所有内容。 问题在于，“其他所有内容”不是您的CList或NNList的子部分。 看这个例子：

example :: CList Int
example = NotNil (Append (Append (Sing 1) (Sing 2)) (Sing 3))

“head”是1。但在“example”中没有定义包含2和3而不包含1的结构的子部分。要实现这一点，您必须构建一个与原始形状不同的新“CList”。虽然这是可能的，但老实说，我不认为这对初学者来说有什么价值。

如果“subpart”不清楚是什么意思，请将示例视为树：

        NotNil
          |
          v
        Append
         / \
        v   v
     Sing   Append
      |      / \
      v     v   v
      1  Sing   Sing
          |      |
          v      v
          2      3

Subpart表示子树。

- Luis Casillas

---

这里的问题可能表述不够清晰，但是很明显这个数据结构是用来表示列表的。非空列表要么是单个元素，要么是两个非空列表连接在一起。通常情况下，列表可以为空，也可以是非空列表。 - Tom Crockett

Answer 2

提示：尝试使用模式匹配而不是等值检查（==）来重写此内容。

编辑：

首先，你需要了解什么是模式匹配以及它的工作原理。我建议你去这里阅读：http://en.wikibooks.org/wiki/Haskell/Pattern_matching，网络上也有许多其他资源可供参考（Google是你的朋友）。

完成后，这里有另一个提示：首先编写一个函数nnListGet :: NNList a -> (a，CList a)，然后使用它来实现cListGet。

- Tom Crockett

---

我还是有点新手，不完全理解数据类型背后的语法。我尝试了按照你的建议做，但不确定如何修复它。（更新了原始帖子） - rlhh

Answer 3

补充之前非常详细的回答：你需要意识到自定义列表是可折叠的结构。这意味着它表示可以组合在一起的值序列。这种数据类型可以实现Foldable类型类。在你的情况下，应该是：

import Prelude hiding (foldr)
import Data.Foldable

data NNList a = Sing a | Append (NNList a) (NNList a) deriving (Eq)
data CList a = Nil | NotNil (NNList a) deriving (Eq)

instance Foldable NNList where
    foldr f z (Sing x)          = f x z
    foldr f z (Append xs ys)    = foldr f (foldr f z ys) xs
instance Foldable CList where
    foldr _ z Nil               = z
    foldr f z (NotNil xs)       = foldr f z xs

从中，你将免费获得所有在Data.Foldable中定义的函数，例如maximum / minimum，查找元素等。

对于任何Foldable，您都可以实现headMaybe，它使用First monoid返回其第一个元素。它是一个非常简单的monoid，返回最左边的非空元素。因此，如果您使用此monoid折叠Foldable的所有元素，则会获得其第一个元素：

import Data.Monoid

headMaybe :: (Foldable f) => f a -> Maybe a
headMaybe = getFirst . foldMap (First . Just)

另外，您还可以直接使用foldr，使用Maybe的Alternative实例，该实例再次返回最左侧的非空元素：

import Control.Applicative

headMaybe = foldr (\x y -> pure x <|> y) Nothing

然而，这并不能解决你问题的第二部分 - 计算tailMaybe。这无法像headMaybe一样以通用方式定义，你需要自己编写一个定制函数来实现。

另请参见：

• 维基百科上的Fold。
• Haskell wiki 上的Foldable and Traversable。
• Haskell wiki 上的Fold。
• Haskell wikibook 上的List processing。

- Petr

Answer 4

你为什么要用两种类型来声明？这里有一个看起来更合适的类型声明和正确的函数：

data CList a
  = Nil
  | Sing a
  | Append (CList a) (CList a)
  deriving (Eq)

headAndTail :: CList a -> Maybe (a, CList a)
headAndTail Nil = Nothing
headAndTail (Sing a) = Just (a, Nil)
headAndTail (Append a b) = 
  case headAndTail a of
    Nothing -> headAndTail b
    Just (head, tail) -> Just (head, Append tail b)

- Nikita Volkov

---

拥有两种类型可以确保Nil节点只出现在顶部，因此您不必担心仅由Append和Nil组成的大型子树在数据结构中累积。 - hammar

@hammar 是的，但是这样你就必须让外部API来管理这两种类型的一堆模式匹配。而且这将导致立即计算结果，而不是懒惰地累积操作，这似乎是该数据结构的整个目的所在。 - Nikita Volkov

@NikitaVolkov 另一方面，追加可以在常数时间内完成。但我相信这是一个家庭作业任务，而不是旨在作为实际列表实现的。 - Tom Crockett