5

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

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

4

4 回答 4

13

好吧，人们通常会将您拥有的数据结构称为一种树，而不是列表。但不管怎么说...

问题#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 区分这三件事：

  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)之间没有逗号。在 Haskell 中，这种事情会给你比大多数其他语言更令人困惑的错误消息，因为当 Haskell 看到这个时，它不会告诉你“你犯了语法错误”；Haskell 比大多数语言更文字化，因此它认为您正在尝试将 with作为第一个元素，作为第二个元素，因此它得出的结论是必须具有 type 。foobarAppend foobar(Append foo, bar)(NNList a -> NNList a, NNList a)

第四个也是最后一个问题：你给自己设置的问题没有明确说明，因此没有好的答案。你说你想找到 a 的“头”和“尾” CList a。这意味着什么？在 Haskell[a]类型的情况下，带有构造函数[]and :，这很清楚：头部是xin 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

所以你可能认为“尾巴”就是其他一切。好吧，问题在于“其他所有内容”不是您的子部分CListor NNList。举个例子：

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

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

如果不清楚我所说的“子部分”是什么意思，可以把这个例子想象成一棵树：

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

子部分 = 子树。

于 2013-03-27T05:37:01.463 回答
3

提示：尝试仅使用模式匹配而不是相等检查 ( ==) 来重写它。

编辑：

首先，了解什么是模式匹配以及它是如何工作的至关重要。我建议去这里阅读；网络上也有很多关于此的其他资源（谷歌是你的朋友）。

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

于 2013-03-27T04:19:15.420 回答
1

只是添加到其他（非常彻底的）答案：很高兴意识到您的自定义列表是可折叠的结构。这意味着，它表示可以组合在一起的一系列值。这样的数据类型可以实现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免费获得所有定义的功能，例如最大值/最小值，搜索元素等。

对于 any Foldable，您可以headMaybe使用Firstmonoid实现返回其第一个元素。这是一个非常简单的幺半群，它返回最左边的非空元素。所以如果你Foldable使用这个幺半群折叠 a 的所有元素，你会得到它的第一个：

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，您需要自定义函数，就像您所做的那样。

也可以看看：

于 2013-03-30T08:44:21.463 回答
0

你为什么用两种类型来声明？这是一个看似更合适的类型声明，具有正确的功能：

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)
于 2013-03-27T09:27:03.653 回答