Getting the head and tail of a custom list type in Haskell

Question

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.

Answer 1

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.

Answer 2

Hint: try to rewrite this using only pattern matching and not equality-checking (==).

Edit:

First off, it's crucial that you understand what pattern matching is and how it works. I'd recommend going here and reading up; there are also plenty of other resources about this on the web (Google is your friend).

Once you've done that, here's another hint: First write a function nnListGet :: NNList a -> (a, CList a), then use it to implement cListGet.