Additional case for a recursive data type

user_14295274 0
Viewed 73

I'm currently learning Haskell and I want to define my own recursive data type for the currency Dollar (just bills, not coins).

My attempt looked like this:

data Dollar = One Dollar
             | Two Dollar
             | Five Dollar
             | Ten Dollar
             | Twenty Dollar
             | Fifty Dollar
             | Hundred Dollar

I showed this to a friend of mine and he said it looks fine BUT he also told me to put an | End at the end of the definition. He tried to explain why it is necessary but I couldn't follow his train of thought. Maybe someone in here has an explanation that I can follow. I would really appreciate it.

custom-data-type algebraic-data-types recursion haskell types
2 Answers

Your friend is probably indicating that at some point, you need a base case. Given the definition

data Dollar = One Dollar
            | Two Dollar
            | Five Dollar
            | Ten Dollar
            | Twenty Dollar
            | Fifty Dollar
            | Hundred Dollar
            | End

you can represent an arbitrary amount of money as a linked list of Dollar values, each one representing a single bill and the "rest" of the money. End would terminate the list. For example,

fortyTwoDollars :: Dollar
fortyTwoDollars = Twenty (Ten (Five (Five (Two End))))

However, I don't see a reason to mix the list into this; a single Dollar value can represent a bill alone, and you can use a [Dollar] value to indicate a collection.

data Dollar = One
            | Two
            | Five
            | Ten
            | Twenty
            | Fifty
            | Hundred
            
fortyTwoDollars :: [Dollar]
fortyTwoDollars = [Twenty, Ten, Five, Five, Two]
user_11268410

This doesn't need recursion

The problem of describing bills doesn't require a recursive type. Let's start with a list then talk about your "dollar".

Lists

Your bills are basically special list with more constructors and no termination. For example, a normal list is like this:

data List a = SomeElement a List | End

This means we can construct a linked list such as:

myList = SomeElement 1 (SomeElement 2 ( End ) )

But if we don't have End we have no way to stop the list. It must be SomeElement on and on forever.

otherList = SomeElement 1 (SomeElement 2 ( ... oh no, I have to keep going! ...))

Back to "dollar"

So you have this special list of dollars. Instead of using SomeElement 1 for one dollar and SomeElement 5 for a five dollar bill you have One and Five. This allows you to construct a "stack" of bills:

myMoney = One (Two (Five ( One ...

But you can't stop, unless you make the list cycle such as having ... be myMoney and thus get an infinite list of One Two Five One One Two Five One One ....

Questioning The Design

You might just want something simple:

data Dollar = One | Two | Five

And then you can make a list of dollars (type [Dollar]) with normal lists such as [One, Two, Five, One]. By claiming the One bill also contains another dollar (which is what Dollar = One Dollar means) you create not a single bill but a list of them, which doesn't seem useful.

user_2161640
Related