Haskell中的数组定义了类型(不是数据)

Question

type Array a = Int -> a

emptyArray :: Array a
emptyArray i =
  error ("Access to non-initialized index " ++ show i)

putIndex :: Array a -> Int -> a -> Array a
putIndex ar i v = ar'
 where ar' j | j==i      = v
             | otherwise = ar j

getIndex :: Array a -> Int -> a
getIndex a i = (a i)

我不明白emptyArray和putIndex功能.问题是:

• 什么是ar'的类型
• ar'模式何时匹配？
• 什么时候j==i？
  • v是类型a还是？在这种情况下,它不会返回一个数组.
• 在= = ar j中会发生什么
• 为什么会 getIndex (putIndex emptyArray 1 3) 2产生错误
  • getIndex (putIndex emptyArray 1 3) 1 回归3​​似乎很清楚.

Answer 1

我不会直接回答你所有的问题,而是试着解释一下这种Array a类型背后的基本原理.

数组可以被认为是具有特定属性的数据结构,即给定索引它可以返回与该索引相关联的值.这意味着我们可以通过描述与特定索引关联的值来表征数组,这听起来非常像将输入(索引)映射到输出(该索引处的值)的函数.因此,如果您不想知道长度或哪些索引有效,则可以认为数组与函数没有区别.这是一个相当有限的数组定义,但作为一个学习练习,重要的是要看看如何通过考虑最重要的操作是什么来将数据结构转换为函数.

是什么类型的 ar'

看一下类型签名:

putIndex :: Array a -> Int -> a -> Array a
putIndex    ar         i      v  = ar'

所以ar :: Array a,i :: Int,v::一, andAR" ::阵了`.

ar'模式何时匹配？

我假设你的意思是什么时候使用的定义ar'. ar'是一个Array a,这意味着它是一个功能Int -> a.这意味着无论何时getIndex调用它都会被使用.

什么时候j == i？ v是a什么类型的？在这种情况下,它不会返回一个数组

仔细看看的定义putIndex. ar'是返回值putIndex,而不是v. v是的返回值ar'时j == i. v有类型a,你可以从类型签名中看出putIndex. putIndex是一个增强现有功能的功能ar,首先添加一个检查i == j.

会发生什么 otherwise = ar j

如果j /= i,则不是返回v(新值与索引关联i),而是查找j原始索引处的值ar.这可能更明确地说明了

putIndex originalArray indexToSet newValue = newArray
    where
        newArray j
            | j == indexToSet = newValue
            | otherwise       = getIndex originalArray j

为什么会getIndex (putIndex emptyArray 1 3) 2产生错误？

实质上,您可以将索引查找转换为一堆嵌套的if语句:

putIndex emptyArray i0 x0  ==>  \i -> if i == i0
                                    then x0
                                    else emptyArray i

putIndex (
    putIndex emptyArray i0 x0
    ) i1 x1                ==>  \i -> if i == i1
                                    then x1
                                    else if i == i0
                                            then x0
                                            else emptyArray i

putIndex (
    putIndex (
        putIndex emptyArray i0 x0
        ) i1 x1
    ) i2 x2                ==>  \i -> if i == i2
                                    then x2
                                    else if i == i1
                                            then x1
                                            else if i == i0
                                                    then x0
                                                    else emptyArray i

等等,if-then-else为每个新增加一个新层putIndex.对于您的具体示例

putIndex emptyArray 1 3  ==>  \i -> if i == 1
                                    then 3
                                    else emptyArray i

然后

getIndex (putIndex emptyArray 1 3) 2

相当于表达式

if 2 == 1 then 3 else emptyArray 2