递归类型不与自身统一

Question

以下代码编译失败并出现错误：

type must be Tuple(Thing::Ish, Slice(UInt8)), not Tuple(Array(Array(Thing::Ish) | UInt8) | UInt8, Slice(UInt8))

这两种类型对我来说似乎是等价的……在正确的地方添加一个 .as(Ish) 是可行的……我错过了什么？为什么这些类型不统一？

module Thing
    alias Ish = UInt8 | Array(Ish)

    def self.decode(bytes : Bytes) : {Ish, Bytes}
        case bytes[0]
            when 0x00..0x17
                {bytes[0], bytes + 1}
            when 0x18
                MultiItemDecoder.new(0x80, ->(x: Bytes) { Thing.decode(x) }).decode(bytes)
            else
                raise "unknown"
        end
    end

    class MultiItemDecoder(T)
        def initialize(@base : UInt8, @item_decoder : Bytes -> {T, Bytes})
        end

        def decode(bytes): {Array(T), Bytes}
            decode_some(bytes + 1, bytes[0])
        end

        def decode_some(bytes, n)
            items = n.times.map do
                item, bytes = @item_decoder.call(bytes)
                item
            end
            {items.to_a, bytes}
        end
    end
end

Answer 1

self.decode 想要 return 一个 {Ish, Bytes}，它在 when 0x00..0x17 中确实如此，但没有看到使它实际编译并得到错误的代码。但在 0x18 中，它会 return 一个 {Array(Ish), Bytes}。这将扩展为 {Array(UInt8 | Array(Ish)), Bytes}（递归）

Answer 2

这个有效：

module Thing
  alias Ish = UInt8 | Array(Ish)

  def self.decode(bytes : Bytes) : {Ish, Bytes}
    case bytes[0]
    when 0x00..0x17
      {bytes[0], bytes + 1}
    when 0x18
      MultiItemDecoder.new(0x80, ->(x : Bytes) { Thing.decode(x) }).decode(bytes)
    else
      raise "unknown"
    end
  end

  class MultiItemDecoder(T)
    def initialize(@base : UInt8, @item_decoder : Bytes -> {T, Bytes})
    end

    def decode(bytes) : {Ish, Bytes}
      decode_some(bytes + 1, bytes[0])
    end

    def decode_some(bytes, n)
      items = n.times.map do
        item, bytes = @item_decoder.call(bytes)
        item.as(Ish)
      end
      {items.to_a.as(Ish), bytes}
    end
  end
end

Thing.decode(Bytes[1, 2, 3])

问题是 Array(Array(Ish)) 不是 Array(Ish)，因为它必须是 Array(Array(Ish) | UInt8)（注意它是联合数组）。

这一切都归结为事物在内存中的表示方式。

我的建议是避免使用递归别名。它们不直观，我们最终可能会将它们从语言中删除。

递归类型不与自身统一

Recursive type not unifying with itself

crystal-lang