Haskell 数据类型

Question

哪个不是下面定义的 Bin 数据类型的值？

data Bin = B Bin | C [ Int]

a) C [ ]

b) B ( B C [ 2])

c) B ( C [ 1..5])

d) B (B (B (C[2,3])))

Answer 1

通过使用 ghci 并简单地输入代码片段，您将看到接受了哪些值：

Prelude> data Bin = B Bin | C [ Int]
Prelude> a = C [ ]
Prelude> b = B ( B C [ 2])

<interactive>:3:9: error:
    • Couldn't match expected type ‘[Integer] -> Bin’
                  with actual type ‘Bin’
    • The function ‘B’ is applied to two arguments,
      but its type ‘Bin -> Bin’ has only one
      In the first argument of ‘B’, namely ‘(B C [2])’
      In the expression: B (B C [2])

<interactive>:3:11: error:
    • Couldn't match expected type ‘Bin’
                  with actual type ‘[Int] -> Bin’
    • Probable cause: ‘C’ is applied to too few arguments
      In the first argument of ‘B’, namely ‘C’
      In the first argument of ‘B’, namely ‘(B C [2])’
      In the expression: B (B C [2])
Prelude> c = B ( C [ 1..5])
Prelude> d = B (B (B (C[2,3])))

Answer 2

要自己轻松回答此类问题，您需要轻松理解 Haskell 的代数数据类型定义：

  -- v  a type being defined
data Bin = 
           B  Bin 
        -- ^  ^ the type of the argument to the data constructor `B`
        -- ^ the name of the data constructor function `B`:  B :: Bin -> Bin
        --          (read: B is of type Bin -> Bin, i.e. a function
        --                 taking a Bin type value and producing a Bin type value)
         | C  [Int]
        -- ^  ^ the type of the argument to the data constructor `C`
        -- ^ the name of the data constructor function `C`:  C :: [Int] -> Bin
        --          (read: C is of type [Int] -> Bin, i.e. a function
        --                 taking a list of Int values and producing a Bin type value)

这意味着，我们可以通过以下两种方式中的任何一种来创建Bin类型的数据：

首先，我们可以用一个参数调用一个名为 B 的函数，一个类型为 Bin.
其次，我们可以用一个参数调用一个名为 C 的函数，一个 [Int] 类型的值，一个整数列表。

第二种方法简单明了：只需使用任何整数列表，如 C [1] 或 C [4,3,2]

x1 :: Bin        -- read: `x1` is of type `Bin`
x1 = C [1]       -- or,

但是第一个呢？我们需要使用 Bin 类型的值作为参数：

x1 = B x2

但是我们在哪里可以得到x2？我们正在创建一个Bin，它要我们给它一个Bin？这是恶性循环吗？

没有！因为我们有第二种创建 Bin 值的方法：

x2 = C [2]    -- x1 = B (C [2])

但我们也可以在这里使用第一个：

x2 = B x3     -- x1 = B (B x3)

那x3呢？同样的道理，

x3 = C [3]    -- x1 = B (B (C [3]))   -- or,
x3 = B x4     -- x1 = B (B (B x4))

和

x4 = C [4]    -- x1 = B (B (B (C [4])))   -- or,
x4 = B x5     -- x1 = B (B (B (B x5)))

看到了吗？ Bin 类型的有效值由 B 构造函数的嵌套链组成，在链的最底部带有 C [...] 。正确的？数据类型定义用作生成该类型的有效术语的语法。

现在可以轻松回答您的问题了：

C [ ] : - 这是嵌套的 B 链，底部有 C 吗？ : __
B (B C [2]) : - 这是嵌套的 B 链，底部有 C 吗？ : __
B (C [1..5]) : - 这是嵌套的 B 链，底部有 C 吗？ : __
B (B (B (C [2,3]))) : - 这是嵌套的 B 链，底部有 C 吗？ : __

这种对同一规则的重复应用被称为递归，因此这种数据类型Bin是递归数据类型，其定义中有两个子句：递归子句和基本子句。

哪个是哪个？

Haskell 数据类型

Haskell Data Types

haskell

recursion

grammar

algebraic-data-types

recursive-datastructures