派生文件夹类型(!!)

Deriving type of foldr (!!)

foldr :: (a->b->b)->b->[a]->b
(!!)::[c]->Int->c

由此我们得到 a->b->b=[c]->Int->ca=[c],b=Int,b=c.
我们得出结论,foldr (!!) 的类型是 Int->[[Int]]->Int.
正确吗?
WinGHCi 告诉我一些不同的事情:

Prelude> :t foldr (!!)
foldr (!!) :: Foldable t => Int -> t [Int] -> Int

如评论中所述,在最近的 GHC 中,foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b。当t ~ []时,Foldable t => Int -> t [Int] -> Int简化为Int->[[Int]]->Int,如你所料。

有几种方法可以让 GHCi 打印更具体的类型。一种是添加您期望的类型签名,并让 GHCi 验证。

> :t foldr (!!) :: Int->[[Int]]->Int
foldr (!!) :: Int->[[Int]]->Int :: Int -> [[Int]] -> Int

另一种方法是在 foldr 的正常(术语)参数之前为 t 提供显式类型:

> :t foldr @[] (!!)
foldr @[] (!!) :: Int -> [[Int]] -> Int

这使用 TypeApplications。语法是 @ 后跟类型名称。

早期的foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b确实有签名(a -> b -> b) -> b -> [a] -> b,但是他们有泛化的功能,所以 不仅适用于列表(其中 t ~ []),而且适用于其他 Foldable 类型(如 MaybeSum 等)。但是对于列表的情况,没有任何变化,该功能只是适用于更多Foldable类型。

正在导出 "old" foldr

的类型

那样的话,我们将原料取为:

foldr :: (a -> b -> b) -> b -> [a] -> b
(!!) :: [c] -> Int -> c

或更详细:

foldr :: (a -> (b -> b)) -> (b -> ([a] -> b))
(!!) :: [c] -> (Int -> c)

由于(!!)是调用foldr作为函数的参数,我们知道(!!) :: [c] -> (Int -> c)函数的类型应该和[=的参数类型匹配30=],所以 (a -> b -> b)。所以这意味着:

  a -> (b -> b)
~ [c] -> (Int -> c)
--------------------
a ~ [c], b ~ c ~ Int

所以我们知道a[c]是同一个类型,bc其实都是Int。因此我们知道 a ~ [Int].

所以现在 foldr (!!) 的类型是 foldr 的输出类型,但专门针对我们导出的内容,所以:

b -> ([a] -> b)

等于:

Int -> ([[Int]] -> Int)

或更简洁:

Int -> [[Int]] -> Int

导出“new”的类型folr

那样的话,我们将原料取为:

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
(!!) :: [c] -> Int -> c

我们对foldr的第一个参数遵循相同的推理:

  a -> (b -> b)
~ [c] -> (Int -> c)
--------------------
a ~ [c], b ~ c ~ Int

所以foldr的输出类型是:

Foldable t => b -> (t a -> b)

或用我们所知道的指定:

Foldable t => Int -> t [Int] -> Int

这是ghci派生出来的。

函数的语义

至于语义,函数:

f = foldr (!!)

Int(索引)和 Int 列表的 Foldable 作为输入。在列表的情况下,它将 - 从右到左 - 获取最右边列表中具有该索引的元素,并将该元素用作最后一个列表的索引。我们一直这样做,直到第一个列表和 return 元素。

例如:

foldr (!!) 1 [] -> 1
foldr (!!) 1 [[2, 0]] -> 0
foldr (!!) 1 [[3, 5], [2, 0]] -> 3

对于 t ~ Maybe 的情况,我们将 return 原始索引(如果是 Nothing),或者我们将 return 该索引处的元素它是一个 Just [1, 4, 2, 5](一个带有 [Int] 对象的 Just)。例如:

foldr (!!) 1 Nothing -> 1
foldr (!!) 3 Nothing -> 3
foldr (!!) 1 (Just [1, 4, 2, 5])-> 4
foldr (!!) 3 (Just [1, 4, 2, 5])-> 5