如何为带数据构造器的Haskell LST类型编写Functor实例？

首先回顾给定的类型定义：

type ID = Int
data LST a
  = Leaf ID a
  | Node ID [LST a]
    deriving (Show, Eq)

要实现Functor实例，我们需要遵循fmap :: (a -> b) -> LST a -> LST b的类型签名，递归处理每个构造器：

instance Functor LST where
  fmap f (Leaf id val) = Leaf id (f val)
  fmap f (Node id children) = Node id (map (fmap f) children)

实现说明： #

• 对于Leaf构造器：仅对a类型的val字段应用函数f，ID类型的标识字段保持不变，因为它与类型参数a无关。
• 对于Node构造器：同样保留ID字段不变，对子节点列表中的每个LST a元素递归应用fmap f，通过map函数遍历列表完成批量转换。

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