在Haskell中获取自定义列表类型的头部和尾部 [英] Getting the head and tail of a custom list type in Haskell

问题描述

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

  data NNList a = Sing a |附加（NNList a）（NNList a）派生（Eq）
数据CList a = Nil | NotNil（NNList a）派生（Eq）
  

我试图实现一个返回头的函数和列表的尾部：

cListGet :: CList a - > Maybe（a，CList a）

我的尝试：

  cListGet :: CList a  - >可能（a，CList a）
 cListGet Nil = Nothing 
 cListGet xs @（NotNil nxs）= 
 case $ x 
 Sing x  - > （x，Nil）
追加l r  - > （（fst $ cListGet（NotNil l）），（Append（snd $ cListGet（NotNil l）），r））
  

我意味着继续往左走，直到我找到一个。一旦我得到单个元素（头），返回元素和一个无列表。这个零列表然后在它作为最终结果返回之前与列表结合。

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

解决方案

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

问题＃1：Haskell是缩进敏感的，而且你的 case 表达式没有缩进。这导致了一个解析错误。

问题＃2和更大的问题：您还没有理解 Maybe 类型的作品呢。我的印象是，你认为它的工作原理类似于更常见的语言中的空值，并且这会让你失望。

在诸如Java之类的语言中， null 是大多数其他值都可以出现的值。如果我们有一个具有以下签名的方法：

$ p $ public Foo makeAFoo（Bar someBar）




  //方法＃1：传入实际值
 Bar theBar = getMeABar（）; 
 Foo结果= makeAFoo（theBar）; 
 
 //方式2：传入一个空
 Foo result2 = makeAFoo（空）
  

$ b $从某种意义上说，b


theBar 和 null 是平行的，或者更准确地说， 它们具有相同的类型 - 您可以在程序中将其替换为另一个，并且在两种情况下都会编译。

在Haskell中，另一方面，字符串hello和 Nothing do not 具有相同的类型，并且你不能在另一个地方使用一个。 Haskell区分了以下三件事：

1. 需要存在的字符串：hello:: String


2. 缺少可选字符串： Nothing :: Maybe String


3. 存在一个可选的字符串：只是hello:: Maybe字符串

＃1和＃3之间的区别就是你在函数中系统地缺少的东西。在可能是的情况下，如果您确实有一个值，您必须使用 Just ，它像一个包装来表示这不仅仅是一个 a ，它是一个也许一个。

你失踪的第一个地方 Just 是个案的右边 code>表达式，我们可以这样修复：



   - 这仍然无法编译！ 
 cListGet :: CList a  - >可能（a，CList a）
 cListGet Nil = Nothing 
 cListGet xs @（NotNil nxs）= 
 case $ x 
  - 我在这里和下一个'Just'行：
 Sing x  - > Just（x，Nil）
 Append l r  - > Just（fst $ cListGet（NotNil l），（Append（snd $ cListGet（NotNil l）），r））
  

但是这不是它的结束，因为你正在做 fst $ cListGet（NotNil l），它遭受了相反的问题： cListGet 返回可能（a，CList a），但 fst （a，b），而不是可能（a，b）。您需要对 cListGet 的结果进行模式匹配，以测试它是否为 Nothing 或 Just（ x，l'）。 （同样的问题也出现在你的 snd $ cListGet（NotNil l）。）





使用 Append 构造函数错误。你有它的形式为（Append foo，bar），它在 foo 和<$之间不应该有逗号C $ C>巴。在Haskell中，这样的事情会给你比大多数其他语言更令人困惑的错误消息，因为当Haskell看到这个时，它不会告诉你你犯了一个语法错误; Haskell与大多数语言相比更具有字面意义，因此它表示您试图与 Append foo 作为第一个元素， bar 作为第二个，所以它得出结论：（Append foo，bar）必须具有类型（NNList a - > NNList a，NNList a）。

第四个也是最后一个问题：你自己设定的问题没有明确说明，因此没有好答案。你说你想找到 CList a 的head和tail。那是什么意思？在Haskell [a] 类型的情况下，使用构造函数 [] 和：，这很清楚：头是 x：xs 中的 x ，尾部是 xs 。

据我所知，头的含义似乎是最左边的元素的递归结构。我们可以这样做：

  cListHead :: CList a  - >也许是
 cListHead Nil = Nothing 
  - 不需要将所有东西合并成一个定义;处理
  -  NNList在辅助函数中的情况，它更简单... 
 cListGet（NotNil nxs）= Just（nnListHead nxs）
 
  - 注意有多容易这个函数是写的，因为'NNList'
  - 没有'Nil'的情况下，没有必要在'Maybe'
这边搞乱。基本上，通过将问题分成两个函数，只有
  - 'cListHead'需要关心'Maybe'和'Just'。 
 nnListHead :: NNList a  - > a 
 nnListHead（Sing a）= a 
nnListHead（Append l_）= nnListHead l 
  


$ b $所以你可能会认为尾巴是其他的一切。那么，问题在于所有其他不是 CList 或 NNList 子部分 C>。以这个例子为例：



 例子:: CList Int 
 example = NotNil（Append（Append（Sing 1）（Sing 2））（Sing 3））
  

head是 1 。但在例子中定义的结构没有包含 2 和 3 >而不包含 1 。你必须用不同的形状构造一个新的 CList 来获得它。这是可以做到的，但坦率地说，我没有看到它作为初学者的练习的价值。



如果我不清楚我的意思是什么， 把这个例子看作一棵树：



  NotNil 
 | 
 v 
追加
 / \ 
 v v 
 Sing追加
 | / \ 
 v v v 
 1唱歌
 | | 
vv 
 2 3 
  

子部分=子树

I have a custom list type:

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

I'm trying to implement a function that returns the head and tail of a list:

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

My attempt:

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

Which to me means keep going leftwards until I get a single. Once I get the single element (head), return the element and a Nil list. This Nil list is then combined with the list before it's returned as the final result.

I'm not even sure if the logic is 100% correct.

解决方案

Well, people would normally refer to the data structure you have as a kind of tree, not as a list. But anyway...

Problem #1: Haskell is indentation sensitive, and your case expression is not indented. This leads to a parse error.

Problem #2, and the bigger one: you haven't understood how the Maybe type works yet. I get the impression that you think it works like nulls in more common languages, and this is throwing you off.

In a language like, say, Java, null is a value that can occur where most any other value can. If we have a method with the following signature:

public Foo makeAFoo(Bar someBar)

...then it is legal to call it either of these ways:

// 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 and null are "parallel" in a sense, or said more precisely, they have the same type—you can replace one with the other in a program and it will compile in both cases.

In Haskell, on the other hand, the string "hello" and Nothing do not have the same type, and you cannot use one where the other goes. Haskell distinguishes between these three things:

1. A string that's required to be there: "hello" :: String
2. The absence of an optional string: Nothing :: Maybe String
3. The presence of an optional string: Just "hello" :: Maybe String

The difference between #1 and #3 is what you're systematically missing in your function. With Maybe a, in the cases where you do have a value you must use Just, which acts like a wrapper to signify "this isn't just an a, it's a Maybe a."

First place you're missing Just is the right hand sides of the case expressions, which we can fix like this:

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

But this isn't the end of it, because you're doing fst $ cListGet (NotNil l), which suffers from the converse problem: cListGet returns Maybe (a, CList a), but fst works on (a, b), not on Maybe (a, b). You need to pattern match on the result of cListGet to test whether it's Nothing or Just (x, l'). (This same problem occurs also in your snd $ cListGet (NotNil l).)

Third, you're using your Append constructor wrong. You have it in the form of (Append foo, bar), which should have no comma between foo and bar. In Haskell this sort of thing will give you more confusing error messages than most other languages, because when Haskell sees this, it doesn't tell you "you made a syntax error"; Haskell is rather more literal than most languages, so it figures you're trying to make a pair with Append foo as the first element, and bar as the second one, so it concludes that (Append foo, bar) must have type (NNList a -> NNList a, NNList a).

The fourth and final problem: the problem you've set yourself is not clearly stated, and thus has no good answer. You say you want to find the "head" and "tail" of a CList a. What does that mean? In the case of the Haskell [a] type, with constructors [] and :, this is clear: the head is the x in x:xs, and the tail is the xs.

As I understand you, what you mean by "head" seems to be the leftmost element of the recursive structure. We could get that this way:

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

So you might think that "the tail" is everything else. Well, the problem is that "everything else" is not a subpart of your CList or NNList. Take this example:

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

The "head" is 1. But there is no subpart of the structure defined in example that contains 2 and 3 without containing 1 as well. You'd have to construct a new CList with a different shape than the original to get that. That's possible to do, but I don't see the value of it as a beginner's exercise, frankly.

In case it's not clear what I mean by a "subpart," think of the example as a tree:

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

Subpart = subtree.

这篇关于在Haskell中获取自定义列表类型的头部和尾部的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！