Search code examples
haskelllinked-listalgebraic-data-types

Haskell Linked List Algebraic Datatype

I was attempting to implement a Haskell algebraic datatype linked list (or perhaps more accurately something linked list-like since I don't know of any way to do memory addressing using Haskell) as well as helper functions for converting to and from Haskell's naive list type and wrote the following:

data LinkedList a = Nill | Node a (LinkedList a) deriving Show

hlistTolinkedList :: [a] -> LinkedList a
hlistToLinkedList [] = Nill
hlistToLinkedList x:[] = Node x Nill
hlistToLinkedList x:xs = Node (x) (stringToLinkedList xs)

linkedListToHlist :: LinkedList Char -> [Char]
linkedListToHlist (Node a b) = a ++ linkedListToString b
linkedListToHlist Nill = ''

I get the following compiler error:

@5:1-5:21 Parse error in pattern: hlistToLinkedList

I'm not sure what's wrong with my function. Would someone please explain?

Solution

  • The minimal change needed to make it compile is to simply add some parentheses to the patterns for non-empty lists; e.g.

    hlistToLinkedList (x:xs) = ...

    By requiring parentheses for complex patterns, the compiler need not know how many arguments each constructor takes; an important trick for reducing the context sensitivity and promoting separate compilation.