时间戳

首页 > 解决方案 > Deriving type of foldr (!!)

haskell - Deriving type of foldr (!!)

问题描述

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

From that we get a->b->b=[c]->Int->c or a=[c],b=Int,b=c.
We conclude that type of foldr (!!) is Int->[[Int]]->Int.
Is it correct?
WinGHCi tells me something different:

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

标签： haskelltypesghciunification

解决方案

确实在foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b早期有签名(a -> b -> b) -> b -> [a] -> b，但他们已经推广了这个函数，这样它不仅适用于列表（where 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]，并且两者实际上都是。因此我们知道。bcInta ~ [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将一个（一个索引）和一个sFoldable列表作为输入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]（aJust携带一个[Int]对象）。例如：

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

推荐阅读