haskell - 使用 Applicative 和 Functor 的 Haskell 函数

Question

我有一个练习题，给了我一个函数：

sequence :: Applicative f => [f a] -> f[a]
sequence = foldr (_hole (:)) (pure [])

问题是：

"What type is required for the function that needs to be placed at 
_hole in the following expression? Also give a definition for the 
expression using  and <$> and <*>".

我在理解问题所在时遇到问题。因此，对于我所尝试的，我假设我需要指定运算符，因为它使用的是 foldr，所以我假设它类似于 sequence = foldr((+) (:)) (pure[])。

然后对于表达式的定义，我写了如下内容：

sequence :: <*> f => [f a] -> f[a]
sequence = foldr <$> pure []

我很确定我不是 100% 正确的，所以如果有任何更正，我将不胜感激。

标签： haskell

Answer 1

该练习希望您假设在_hole某处定义了某个值，并且上面的代码进行了类型检查。然后，目标是确定 that 的类型是什么_hole。然后，它会询问 的可能定义_hole。

例如，如果给我们

foo :: Int
foo = 3 + _hole

答案应该是_hole :: Int，因为这是我们使上面的代码工作所需要的。因为定义_hole = 2没问题。

相反，在

foo :: Int -> Bool
foo = const _hole "hello" True

然后我们需要_hole :: Bool -> Int -> Bool和例如_hole = \b i -> b。

你自己的代码比较复杂，所以最好把所有的步骤都写下来：

sequence :: Applicative f => [f a] -> f[a]
sequence = foldr (_hole (:)) (pure [])

这里foldr使用，它（在列表上）有类型

foldr :: (b -> c -> c) -> c -> [b] -> c

要进行类型检查，参数必须具有类型

_hole (:) :: b -> c -> c
pure [] :: c

, 仅用两个参数调用的结果foldr是

sequence :: [b] -> c

因为这必须与sequence上面的类型匹配，所以我们得到

[b] = [f a]
c = f [a]

因此，b = f a和

_hole (:) :: f a -> f [a] -> f [a]
pure [] :: f [a]

pure []零件类型按原样检查。另一方面，我们需要

_hole :: (type of (:)) -> f a -> f [a] -> f [a]

即因为(:) :: d -> [d] -> [d]对于任何d，我们得到

_hole :: (d -> [d] -> [d]) -> f a -> f [a] -> f [a]

哪里d可以随便挑。但是，选择 是“自然的”，d=a因此我们得到

_hole :: (a -> [a] -> [a]) -> f a -> f [a] -> f [a]

现在，我们需要用_hole f x y = ??和<$>来定义<*>。liftA2本质上，我们需要从库中重新实现。您现在应该能够解决最后一部分。