派生类型的折叠(!!)

Question

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

从那我们得到a->b->b=[c]->Int->c 或a=[c],b=Int,b=c.
我们得出结论,foldr(!!)的类型是Int->[[Int]]->Int.
这是对的吗？
WinGHCi告诉我一些不同的东西:

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

Answer 1

该foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b确实在初期有签名(a -> b -> b) -> b -> [a] -> b,但他们普遍的功能,使得它不仅具有列表(其中工作t ~ []),但与其他Foldable类型(如Maybe,Sum等为好).但是对于列表情况,没有任何变化,该功能仅适用于更多Foldable类型.

导出"旧"的类型 foldr

在这种情况下,我们将其作为成分:

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

或者更详细:

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

由于(!!)是带有foldras函数的调用的参数,我们知道函数的类型(!!) :: [c] -> (Int -> c)应该与参数的类型匹配foldr,所以(a -> b -> b).这意味着:

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

因此,我们知道a的是同一类型[c],并且这两个b和c实际上Int.因此我们知道a ~ [Int].

所以现在的类型foldr (!!)是输出类型foldr,但是我们派生的是专门的,所以:

b -> ([a] -> b)

等于:

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

或者更简洁:

Int -> [[Int]] -> Int

推导出" 新 " 的类型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(一个索引)和一个s Foldable列表作为输入Int.如果是列表,它将 - 从右到左 - 获取具有该索引的元素,最右侧列表,并使用该元素作为最后一个列表的索引.我们一直这样做直到第一个列表,并返回元素.

例如:

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

对于这种t ~ Maybe情况,我们将在a的情况下返回原始索引Nothing,或者我们将返回该索引处的元素,以防它是a Just [1, 4, 2, 5](Just携带[Int]对象的a ).例如:

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