Basic operations for linked lists in Haskell

Question

I am trying to write some basic list operations for a linked list in Haskell but I could use a hand with this one. I want to append a list to another but it doesn't work at all, here is my code:

data ML a = E | L a (ML a) deriving (Show)

myList = (L 1 (L 2 (L 3 (L 4 E))))

myHead :: ML a -> a
myHead E = error "empty list"
myHead (L a _) = a

myTail :: ML a -> ML a
myTail E = error "empty list"
myTail (L _ a) = a

myAppend :: ML a -> ML a -> ML a
myAppend E a = a
myAppend (x L xs) ys = x L (xs myAppend ys)

I also got a question on how to show this list as a String like "1,2,3". I got a function that shows it as a list like this [1,2,3] but not as a String.

toString :: ML a -> [a]
toString E = []
toString (L a l) = a:(toString l)

Answer 1

I think the basic problem is on the last line:

myAppend :: ML a -> ML a -> ML a
myAppend E a = a
myAppend (x L xs) ys = x L (xs myAppend ys)

The constructor is L and in Haskell, one usually writes the constructor before its arguments, like:

myAppend :: ML a -> ML a -> ML a
myAppend E a = a
myAppend (L x xs) ys = L x (myAppend xs ys)

Now it should work.

About your second question: toString ML a -> [a]. Actually an [a] is a list, not a String (well, a String is a list of Chars: type String = [Char]), and guess what: a list in Haskell is a linked list. So that means that your toString :: ML a -> [a] is actually more a toList.

If you want to write something as a String, it means the elements should be have a textual representation. You can write that by using a type constraint, like Show a =>. So now the signature is: toString :: Show a => ML a -> [String].

We can convert a list of as into a textual representation, by mapping all the elements to their textual representation, and intercalate :: [a] -> [[a]] -> [a] for instance with a comma, like:

import Data.List(intercalate)

toList :: ML a -> [a]
toList E = []
toList (L x xs) = x : toList xs

toString :: Show a => ML a -> String
toString = intercalate "," . map show . toList

Or we can "implement the function by ourselves":

toString :: Show a => ML a -> String
toString E = ""
toString (L x E) = show x
toString (L x xs) = show x++',' : toString xs