为什么包含列表构造函数的 `a` 的求和类型与 `a` 的列表不匹配？

Question

我正在尝试实施 primitive recursive functions。显然，在 Haskell 中使用可变参数函数并不常见，我使用类型

data PrimT a = Sgl a | Sqc [a]

所以我可以将原子值和值列表传递给函数。这适用于零函数、投影和后继函数：

zero k (Sqc args) = if length args == k then Right 0 else Left "invalid number of arguments"
zero 1 (Sgl arg)  = Right 0

pi i k (Sqc args) = if length args == k then Right $ args!!i else Left "invalid number of arguments"
pi 1 1 (Sgl arg) = Right arg

nu (Sgl i) = Sgl $ i + 1

但是我在构图方面遇到了问题（此处 o）。这个定义背后的想法是，组合可以发生在函数 f 和：1) 函数列表和参数列表，2) 函数列表和一个参数，3) 一个函数和参数列表，最后 4 ) 一个函数和一个参数。因此，我将函数和放在 PrimT 中，这样我就可以将 Sqc gs 用于函数列表，将 Sgl g 用于单个函数。参数相同：Sqc args 和 Sgl arg.

o :: PrimT (PrimT b -> PrimT c) -> PrimT (PrimT a -> PrimT b) -> PrimT a -> PrimT c
o (Sgl f) (Sqc gs) (Sqc args) = f [g args | g <- gs]
-- o (Sgl f) (Sqc gs) (Sgl arg) = f [g arg | g <- gs]
-- o (Sgl f) (Sgl g) (Sqc args) = f [g args]
-- o (Sgl f) (Sgl g) (Sgl arg) = f [g arg]

但是编译器对 f [g args | g <- gs] 部分不满意。它说：

primrec.hs:69:35: error:
    • Couldn't match expected type ‘PrimT b’
                  with actual type ‘[PrimT b]’
    • In the first argument of ‘f’, namely ‘[g args | g <- gs]’
      In the expression: f [g args | g <- gs]
      In an equation for ‘o’:
          o (Sgl f) (Sqc gs) (Sqc args) = f [g args | g <- gs]
    • Relevant bindings include
        gs :: [PrimT a -> PrimT b] (bound at primrec.hs:69:16)
        f :: PrimT b -> PrimT c (bound at primrec.hs:69:8)
        o :: PrimT (PrimT b -> PrimT c)
             -> PrimT (PrimT a -> PrimT b) -> PrimT a -> PrimT c
          (bound at primrec.hs:69:1)
   |
69 | o (Sgl f) (Sqc gs) (Sqc args) = f [g args | g <- gs]
   |                                   ^^^^^^^^^^^^^^^^^^

primrec.hs:69:38: error:
    • Couldn't match expected type ‘PrimT a’ with actual type ‘[a]’
    • In the first argument of ‘g’, namely ‘args’
      In the expression: g args
      In the first argument of ‘f’, namely ‘[g args | g <- gs]’
    • Relevant bindings include
        g :: PrimT a -> PrimT b (bound at primrec.hs:69:45)
        args :: [a] (bound at primrec.hs:69:25)
        gs :: [PrimT a -> PrimT b] (bound at primrec.hs:69:16)
        o :: PrimT (PrimT b -> PrimT c)
             -> PrimT (PrimT a -> PrimT b) -> PrimT a -> PrimT c
          (bound at primrec.hs:69:1)
   |
69 | o (Sgl f) (Sqc gs) (Sqc args) = f [g args | g <- gs]
   |

但我不明白为什么。根据其定义，PrimT a 可以是 a ([a]) 的列表。那么问题出在哪里呢？

Answer 1

PrimT a can be a list of a ([a]) according to its definition

不，PrimT a 可以是 Sgl 或 Sqc。因此，给定 [a] 类型的列表 xs，Sqc xs 将是 PrimT a，但 xs 不会。 xs 已经是一个列表 - 不能是其他列表。

按照同样的逻辑，Sqc args 是 PrimT a，Sqc [g (Sqc args) | g <- gs] 是 PrimT (PrimT b)，但没有 Sqc，它们只是列表。

我还应该指出 PrimT (PrimT b) 不是您想要的类型（您想要 PrimT b），因此您仍然需要展平结果以获得您想要的结果。

为什么包含列表构造函数的 `a` 的求和类型与 `a` 的列表不匹配？

Why does a sum-type of `a` containing a list constructor not match a list of `a`?

haskell

types

algebraic-data-types