Algebraic data type list into an actual list

Question

I am tying to create a function where I enter an Algebraic data type list, and it should output an actual list.

For example, we have a list1 = P `Cons` (G `Cons` Empty)

The Output should be: [G,P]

I created the following Algebraic data types:

data Elements = G | S | P deriving (Eq, Show)
data List a = Empty | Cons Elements (List Elements) 

and my current function is:

list:: Elements -> [List]
list Empty = []
list Cons a (List b) = [a] ++ list (List b)

I am having trouble solving this, and would appreciate if I get some help!

Thanks in advance!

Answer 1

Let's start with your data types:

data Elements = G | S | P deriving (Eq, Show)
data List a = Empty | Cons Elements (List Elements)

From a technical standpoint, there's nothing wrong with Elements, but it's a very poor choice of name. As others have noted, it's more usual to name the type Element. The reason is that the English translation of your data type declaration is:

"Elements" is either gold or silver or platinum.

when it would make more sense to say:

An "Element" is either gold or silver or platinum

Also, when you start writing code with this type, it starts to get confusing. If you define a value of type Elements:

e :: Elements
e = P

this represents a single element "platinum", and not a collection elements. This confusion might lead you to write a list function with the wrong type signature because you think you're saying list takes a bunch of Elements but the type signature actually says that list takes only one element.

For this reason, I'm going to do a search and replace of all your code, and the rest of my answer will talk about this version using "Element" instead:

data Element = G | S | P deriving (Eq, Show)
data List a = Empty | Cons Element (List Element)

list:: Element -> [List]
list Empty = []
list Cons a (List b) = [a] ++ list (List b)

list1 = P `Cons` (G `Cons` Empty)

Moving on, there is a problem with your List type:

data List a = Empty | Cons Element (List Element)

You've defined a parameterized type List a, but then you haven't used the parameter a in its definition. In other cases where you've seen a List a defined it was because the a parameter was supposed to represent the type of list items, so the same list could be used to hold Elements or Ints or whatever. Since you want a special list data type that only holds Elements, you should write List without a parameter (on both the left-hand side and the right-hand side of this declaration):

data List = Empty | Cons Element List
        ^^- no "a"                  ^^- no "Element" argument

Now, consider the type signature for list:

list :: Element -> [List]

What list is supposed to do is take a list of elements like:

list1 = P `Cons` (G `Cons` Empty)

and produce a Haskell list as a result:

result1 = [G,P]

but this type signature says that list is going to take a single Element and produce a Haskell list whose items are of type List (i.e., a custom List of Elements), in other words, it'll produce a list of Lists of elements. This certainly isn't right.

In fact, list should take a List of Elements and return a (Haskell) list of Elements, so the type signature should read:

list :: List -> [Element]

Note that if you loaded up just the type declarations into GHCi and checked the types of your example argument and result:

ghci> data Element = G | S | P deriving (Eq, Show)
ghci> data List = Empty | Cons Element List
ghci> :type  P `Cons` (G `Cons` Empty)
P `Cons` (G `Cons` Empty) :: List     -- input is of type `List`
ghci> :type  [G,P]
[G,P] :: [Element]                    -- output is of type `[Element]`

this would confirm that you want a function List -> [Element].

Now, your definition has two more errors:

list Cons a (List b) = [a] ++ list (List b)

Patterns like Cons a (List b) need to be surrounded by parentheses to match a single argument, so this should read:

list (Cons a (List b)) = [a] ++ list (List b)

There's still another problem here. The use of List doesn't make sense here. List is a type, and it belongs in type signatures, not in patterns or expressions, at least not like this. Haskell already knows that the second field of Cons is a List, so you don't need to tell it that. You just need to assign that field to a variable. If you eliminate the List from both sides:

list (Cons a b) = [a] ++ list b

the final definition should type check:

list :: List -> [Element]
list Empty = []
list (Cons a b) = [a] ++ list b

If you want the result in reverse order, just flip the concatenation around:

list :: List -> [Element]
list Empty = []
list (Cons a b) = list b ++ [a]

The final code:

data Element = G | S | P deriving (Eq, Show)
data List = Empty | Cons Element List deriving (Show)

list:: List -> [Element]
list Empty = []
list (Cons a b) = list b ++ [a]

list1 = P `Cons` (G `Cons` Empty)

main = print $ list list1  -- output [G,P]