haskell - 如何使用 Scott 编码表示嵌套类型？

Question

ADT 可以使用 Scott 编码来表示，将乘积替换为元组，将求和替换为匹配器。例如:

data List a = Cons a (List a) | Nil

可以使用 Scott 编码进行编码:

cons = (λ h t c n . c h t)
nil  = (λ c n . n)

但我找不到如何使用 SE 编码嵌套类型:

data Tree a = Node (List (Tree a)) | Leaf a

如何做到这一点？

Answer 1

如果Wikipedia article是正确的，那么

data Tree a = Node (List (Tree a)) | Leaf a

有 Scott 编码

node = λ a . λ node leaf . node a
leaf = λ a . λ node leaf . leaf a

看起来 Scott 编码对(嵌套)类型无关。它所关心的只是向构造函数传递正确数量的参数。