I am trying to learn to work with algebraic data type, but i have some trouble.
So I want to create a Chain that has Gold, Silver or Platinum Links.
Currently i have the following dataTypes:
data Link = G | S | P deriving (Eq, Show)
data Chain = Empty | Join Chain Link Chain
But now I am unsure how to construct the chain
I tried to construnct a chain that has the following Links in this order: Platinum, Gold, Gold
This is how i constructed it:
chain1 = (Join Empty G (Join Empty G (Join Empty P (Empty))))
But i am unsure if it is correct.
Thanks in advance!
CodePudding user response:
Your Chain
type allows for an arbitrary tree structure (indeed, it's isomorphic to the common definition of a binary tree,
data Tree a = Empty | Node a (Tree a) (Tree a)
data Chain' = Empty | Join Link Chain' Chain'
Instead, I would represent a chain as being implicitly joined using the adjacent ends of two smaller chains (and for simplicity, disallowing empty chains).
data LinkType = G | S | P
data Chain = Link LinkType | Join Chain Chain
-- two isomorphic representations of PGG: P(GG) and (PG)G
chain1a = Join (Link P) (Join (Link G) (Link G))
chain1b = Join (Join (Link P) (Link G)) (Link G)
If you want to join two chains with a given link, use a regular function.
joinWith :: Link -> Chain -> Chain
joinWith l c1 c2 = Join (Join c1 (Link l)) c2
-- or
-- joinWith l c1 c2 = Join c1 (Join c2 (Link l))
c1 = joinWith P (Link S) (Link G) -- SPG
CodePudding user response:
If you want your chain elements to point to each other, you need to make a mutually recursive definition like this one:
chain1 = Join Empty G chain2
chain2 = Join chain1 G chain3
chain3 = Join chain2 P Empty
This technique is sometimes called "tying the knot", and you can find more examples around the 'net.