使用代数数据类型构造Chain链的正确性咨询

首先看你定义的Haskell数据类型：

data Link = G | S | P deriving (Eq, Show)
data Chain = Empty | Join Chain Link Chain

Join Chain Link Chain的语义是把一个Link拼接在两个Chain中间，整个Chain的元素顺序是：左边Chain的所有元素 → 当前Link → 右边Chain的所有元素。

你当前写的构造代码：

chain1 = (Join Empty G (Join Empty G (Join Empty P (Empty))))

实际生成的链元素顺序是 G → G → P，和你想要的「Platinum、Gold、Gold」（即P → G → G）完全相反——因为你把最想要的第一个元素P放在了最内层的Join里，而外层的Join会把自己的Link放在更靠前的位置。

正确的构造方式 #

要得到P → G → G的链，需要把P放在最左侧的拼接位置，依次向右添加G：

-- 直接一行构造
chain1 = Join (Join (Join Empty P Empty) G Empty) G Empty

如果你觉得嵌套写法不够直观，可以分步构建：

-- 先创建仅含P的链
onlyP = Join Empty P Empty
-- 给onlyP拼接一个G，得到P→G的链
pThenG = Join onlyP G Empty
-- 再给pThenG拼接一个G，得到P→G→G的链
chain1 = Join pThenG G Empty

验证方法 #

你可以写一个辅助函数把Chain转换成列表，直观查看元素顺序：

chainToList :: Chain -> [Link]
chainToList Empty = []
chainToList (Join left link right) = chainToList left ++ [link] ++ chainToList right

调用chainToList chain1，如果返回[P, G, G]，就说明构造正确。

内容的提问来源于stack exchange，提问作者Daniel12