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

functional-programming, haskell, list

Solution

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:

- A string that's required to be there: `"hello" :: String`

- The absence of an optional string: `Nothing :: Maybe String`

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

Problem

Original source