list - 在 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% 正确。

Answer 1

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

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

问题#2，以及更大的问题:你还没有理解 Maybe类型工作。我的印象是你认为它在更常见的语言中像空值一样工作，这让你失望。

在像 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 区分了这三件事:

必须存在的字符串:"hello" :: String

缺少可选字符串:Nothing :: Maybe String

可选字符串的存在: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在 x:xs ，尾部是 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))

“头”是 1 .但是 example 中定义的结构没有子部分包含 2和 3不含 1以及。您必须构建一个新的 CList使用与原始形状不同的形状来获得它。这是可能的，但坦率地说，我不认为它作为初学者练习的值(value)。

如果不清楚我所说的“子部分”是什么意思，请将示例视为一棵树:

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

子部分 = 子树。