如何在Haskell中实现递归列表以及对其进行操作的方法

Question

我正在尝试在Haskell中创建一个我认为非常直观的方法.我有一个列表[列表]*列表,任意深入.无论递归的深度如何,我都想在列表中提取一个特定的原子.这是我的努力:

type List = [Array]
data Array = Int | List

drill :: Array -> [Int] -> Array
drill xs (index:[]) = xs !! index
drill xs (index:is) = drill (xs !! index) is

但是在ghci中加载时收到以下内容:

drill.hs:5:23:
Couldn't match expected type `[Array]' with actual type `Array'
In the first argument of `(!!)', namely `xs'
In the expression: xs !! index
In an equation for `drill': drill xs (index : []) = xs !! index

我写的内容对我来说似乎很直观,但显然Haskell有类型问题.作为一个Haskell新手,我不是最好的解释类型错误.我认为函数的返回类型可以是atom:Int或list : [Int]. 任何人都可以帮我解读这个并提出解决方案吗？

Answer 1

当你说

data Array = Int | List

这并不意味着"任何Int是一个Array,任何List都是Array".相反,它意味着Array有两个构造函数,Int并且List两者都不带参数.混淆源于它们与类型同名的事实; 它们与共享名称之外的类型无关.也就是说,你的声明基本上是相同的

data Array = Foo | Bar

相反,我们需要为每个替代方案提供显式的构造函数名称:

type List = [Array]
data Array = Elem Int | Nest List

drill :: Array -> [Int] -> Array
drill xs [] = xs
drill (Nest xs) (index:is) = drill (xs !! index) is

这意味着Elem取一个Int并返回一个Array,然后Nest取一个List并返回一个Array.我们不得不调整drill功能明确把名单Arrays出来的Nest情况.

你得到的错误基本上是说你试图xs用作列表,但它是一个Array.这是因为你根本没有模式匹配:只是试图直接将你的参数(an Array)用作列表.

请注意,您仍然必须对结果进行显式模式匹配,drill以判断它是单个元素还是嵌套列表.没有办法创建一个类型,其值可以在Haskell中字面上是整数或嵌套列表; Haskell的联合被标记(即构造函数是显式的),并且它没有子类型.

有关更多信息,我建议您阅读来自Learn You a Haskell的代数数据类型的介绍.